Number theory

Summary: Number theory has captured the imagination through numerous famous problems, many still unsolved.

The legendary mathematician Carl Friedrich Gauss (1777–1855) famously described number theory as “the queen of mathematics.” The core of number theory is the study of the integers, but number theory includes a much wider class of concepts and problems that arise in the study of the integers. Number theory is extremely popular as recreational mathematics and is explored in twenty-first-century high school classrooms. Early mathematicians in Greece, India, and the Islamic world investigated and developed number theory, making enormous and widely varied contributions. The field has continued to blossom through the twenty-first century. Some mathematicians view number theory as a branch of pure mathematics, but others view it as applied mathematics because of its utility to so many fields, such as physics, chemistry, biology, computing, engineering, coding, cryptography, random number generation, acoustics, communications, graphic design, music, and business.

Prime Numbers

A large portion of number theory is related directly or indirectly to the study of prime numbers and divisibility. An integer a is divisible by integer b if there is an integer c such that a=bc. A prime number is an integer p>1 that is divisible only by itself and 1, and a composite number is a positive integer with more than two factors. It is technically most convenient to consider 1 to be neither prime nor composite. The so-called Fundamental Theorem of Arithmetic, investigated by Carl Friedrich Gauss in the nineteenth century, states that every positive integer n>1 can be written as a product of prime numbers, and furthermore, that this prime factorization is unique (except for the order in which the factors are written). The theorem was partially proved by Euclid of Alexandria in ancient Greece. The recognition that the theorem does not hold in more general number systems by mathematicians such as Ernst Kummer led to the development of the field of algebraic number theory.

It is well known that there are infinitely many prime numbers, so it would not be possible to obtain a complete list of all prime numbers. The search for ever-larger prime numbers is ongoing, and testing numbers for primality is sometimes used as a test of the computational power of supercomputers.

Modular Arithmetic and Cryptography

An important component of elementary number theory is modular arithmetic. In modular arithmetic, two numbers are treated to be the same if they have the same remainder when divided by some given number, the “modulus.” One writes a≡b (mod m) if m divides the difference a-b. One reason why this concept is so useful is that it is compatible with the operations of addition, subtraction, and multiplication. If a≡b (mod m) and c≡d (mod m), then a+c≡b+d (mod m), a-c≡b-d (mod m), and ac≡bd (mod m). The situation is complicated for division, unless m is a prime. Modular arithmetic is sometimes called “clock arithmetic” because of the similarity between arithmetic mod 12 and the system for counting hours. One related theorem that is frequently studied in classrooms in the Chinese remainder theorem, named so because the theorem originates in Chinese texts by Sun Tzu and Qin Jiushao.

If there was ever a time when number theory was studied only for its elegance and beauty and not for any application, that time is past now. Modern cryptography, essential for the security of the Internet, is based heavily on number theory. The widely used RSA (Rivest, Shamir, and Adleman) encryption methods are based on modular arithmetic and rely for their security on number theorists’ understanding of how difficult it is to find large prime factors of a large number. Other encryption systems based on more exotic number theoretic objects, such as elliptic curves, are under active development by cryptographers and number theorists.

Algebraic and Analytic Number Theory

Number theorists study in a diverse range of fields related to number theory, including probabilistic number theory, diophantine approximations, the geometry of numbers, and combinatorial number theory. Number theorists do not exclusively study the integers, nor are the integers the only system that admits something like prime numbers. Number theorists also extensively study other systems of algebraic numbers. An algebraic number is a number that is the root of a polynomial with integer coefficients; the role of “integer” is played by numbers that are roots of polynomials with integer coefficients and leading coefficient 1. For example, the square root of 10 is an integer in this extended sense. Much of algebraic number theory concerns how the concepts of prime number and divisibility as applied to other number fields compare and contrast with the familiar situation for the standard integers.

For example, the Gaussian integers are those complex numbers a+bi with a and b both integers. The Gaussian integers form a number system in which the concepts of prime number and divisibility above apply almost exactly as described above. However, the set of prime numbers here is very different. The number 7, for example, is still prime in the Gaussian integers, but 13, which is prime in the integers, factors here as the product of the two primes, 3+2i and 3-2i.

Though the arithmetic integer is apparently part of discrete mathematics, there is a large branch of number theory, called “analytic number theory,” which applies extremely sophisticated techniques from calculus and complex analysis to the problems of number theory.

A basic fact of analytic number theory is that the sum of the reciprocals of all primes,

Note that it can be recovered from this that the set of prime numbers must itself be infinite. With care, one can estimate the sum of the reciprocals of all primes up to some number x, which turns out to grow at the same rate as log(x). With more refinement along these lines, one obtains the celebrated Prime Number Theorem, which says that the number of prime numbers less than some large integer x is well-approximated by

Famous Problems in Number Theory

One feature of number theory is a large number of intriguing problems that are very simply stated but require unexpectedly advanced and specialized techniques to solve; many remain unsolved in the early twenty-first century. Indeed, many or most of the major problems in mathematics that are known to the general public have origins in number theory.

One major recent mathematical breakthrough, which received mainstream media coverage, was the proof of Fermat’s Last Theorem . Pierre de Fermat (c. 1601–1665) wrote a note in the margin of a book he was reading to the effect that there are no integral solutions to the equation xⁿ+yⁿ=zⁿ with n>2. There are infinitely many solutions with n=2, and these have been well studied; by the Pythagorean Theorem they correspond to right triangles with integer-length sides. Fermat never wrote down a proof, writing instead that the margin of his book was too small to contain it. In the intervening centuries, mathematicians tried to supply the missing proof. Much of algebraic and analytic number theory was developed as part of the effort to prove this theorem. The problem was finally solved in 1995 by Sir Andrew Wiles (1953–), using extremely sophisticated number-theoretic objects involving elliptic curves and modular form. It is not now generally believed that Fermat ever possessed a valid proof.

Because all primes other than 2 are odd, the smallest possible difference between consecutive primes (other than 2 and 3) is 2. Prime numbers that differ by 2 (those that are as close as possible) are called “twin primes.” The Twin Prime Conjecture asserts that there should be an infinite number of twin primes, but mathematicians are very far away from being able to prove this. In a triumph of analytic number theory, Viggo Brun (1885–1978) showed that the sum of the reciprocals of all twin primes is finite, though mathematicians still do not know whether there are finitely or infinitely many of them!

Another famous problem about the additive distribution of the set of prime numbers is Goldbach’s Conjecture, named for Prussian mathematician Christian Goldbach (1690–1764). The conjecture asserts that every even number larger than 2 can be written as the sum of two (not necessarily different) prime numbers. Computer searches have verified that there are no counterexamples smaller than one quintillion. This problem has occupied the attention of many recreational mathematicians and has been featured in several novels and television shows. Again, mathematicians are very far from proving such a theorem.

The Riemann Hypothesis is the most important open problem in number theory, and arguably in all of mathematics. Named for Bernhard Riemann (1826–1866), this conjecture concerns a particular function of the complex numbers called the zeta function. Let ζ(s) be the value of the infinite sum

This is apparently defined only for real numbers s>1, but it turns out that there is a uniquely meaningful way to extend this to allow any complex number as input. It is relatively easy to show that

and there are infinitely many other “nontrivial zeroes” s such ζ(s). The standing conjecture is that all the nontrivial zeroes of ζ lie on a particular line in the complex plane. Though a tremendous amount of effort has gone into trying to prove this and though mathematicians have much corroborating evidence, it is still open. The statement might seem esoteric and arcane; surprising as it may seem, this statement, if true, would have profound implications about the distribution of prime numbers, which would have ramifications throughout all mathematics. Mathematicians have found dozens of very different-looking statements that are known to be equivalent to the Riemann hypothesis, and there are hundreds of statements that have been proven contingent on a future proof of the Riemann hypothesis.

Bibliography

Derbyshire, John. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Washington, DC: Joseph Henry Press, 2003.

Matthews, Keith. “Number Theory Web: Biographies of Past Number Theorists and Various Items of Historical Interest.” http://www.numbertheory.org/ntw/N14.html.

Oystein, Ore. Number Theory and Its History. New York: Dover, 1988.

Pommersheim, James, Tim Marks, and Erica Flapan. Number Theory: A Lively Introduction with Proofs, Applications, and Stories. Hoboken, NJ: Wiley, 2010.

Yan, Song. Number Theory for Computing. Berlin: Springer, 2002.