Number Theory

Number theory is the study of properties of the integers. Because of the fundamental nature of the integers in mathematics, and the fundamental nature of mathematics in science, the famous mathematician and physicist Gauss wrote:

"Mathematics is the queen of the sciences, and number theory is the queen of mathematics."

There are an abundance of simply formulated questions about the integers that involve little more than the basics of addition and multiplication (the ring operations on the integers), but which are nevertheless unsolved or extremely difficult to solve. For example:

• Which integers can be written as the sum of four squares?

• If \(n\ge 3\) is a positive integer, can a positive \(n^\text{th}\) power ever be written as the sum of two positive \(n^\text{th}\) powers?

• Is there a rectangular box whose side lengths, face diagonal lengths, and body diagonal length are all integers?

The first question was solved long ago by Lagrange: every nonnegative integer can be written in this way.

The second question is due to the \(17^\text{th}\)-century mathematician Fermat, who famously claimed in 1637 to have discovered a proof that the answer is no. Though the answer is no, this was not rigorously established until 1995, when Andrew Wiles completed a difficult and sophisticated proof that built on the work of dozens of leading contemporary mathematicians. The result is popularly known as Fermat's last theorem.

The third question is one of many number-theoretic questions whose answer is currently unknown. It is possible to produce infinitely many boxes (sometimes called Euler bricks) for which all the sides and face diagonals are integers, but no one has been able to construct such a box with integer body diagonal length as well, or to prove that no such box exists.

The first nontrivial facts about the integers relate to the concept of divisibility: if \(a,b\) are two integers, then \(b|a\) (read "\(b\) divides \(a\)") if and only if there is an integer \(c\) such that \(bc=a.\)

The integers have a division algorithm, where two integers can be divided with remainder: for any \(a,b \in {\mathbb Z}\) with \(b \ne 0,\) there is a unique integer \(q\) and a unique integer \(r\) with \(0 \le r < |b|\) satisfying \(a=bq+r.\) Here \(q\) is the quotient and \(r\) is the remainder.

In the division algorithm, if \(d|a\) and \(d|b,\) then \(d|r.\) So iterating the division algorithm gives a way to compute the greatest common divisor of \(a\) and \(b,\) called the Euclidean algorithm. The greatest common divisor also satisfies Bezout's identity--the integers of the form \(ax+by\) are precisely the multiples of the greatest common divisor of \(a\) and \(b,\) and in particular, the \(\gcd\) itself can be written as \(ax+by\) for some integers \(x,y.\) In fact, possible values of \(x\) and \(y\) can be computed using the extended Euclidean algorithm.

These computations and algorithms are useful in various applications of elementary number theory; see below for examples.

Main article: Prime numbers

Let \(a\) be a positive integer. If \(b\) is a divisor of \(a\) that is not equal to \(1\) or \(a\) (i.e. \(b\) is a nontrivial proper divisor of \(a\)), then \(a\) can be factored as \(a=bc,\) where \(b\) and \(c\) are nontrivial proper divisors of \(a.\) Then we can break down \(b\) and \(c\) similarly to get an expression for \(a\) as a product of smaller divisors.

The process stops only when each of the divisors in the product cannot be broken down further; in other words, when the divisors in the product do not have any nontrivial proper divisors.

If \(a=12,\) then \(b=2\) is a nontrivial proper divisor. So \(12 = 2 \cdot 6.\) Now \(2\) has no nontrivial proper divisors, but \(6\) does: \(2|6,\) so \(6 = 2 \cdot 3\) and \(12 = 2 \cdot 2 \cdot 3.\)

Integers greater than \(1\) with no nontrivial proper divisors are called prime numbers.

The above discussion shows that every integer can be decomposed as a product of prime numbers. So the prime numbers are the multiplicative building blocks of the integers. This fact is so important that it is known as the fundamental theorem of arithmetic:

Every positive integer can be written as a product of prime numbers. The factorization is unique up to rearrangement of the factors.

The distribution of primes inside the integers is a difficult and rich topic of research. There are infinitely many primes, a fact which was known to Euclid. A much more sophisticated estimate is the prime number theorem, which says roughly that the probability of a random integer \( \le x\) being prime is about \(\frac1{\ln x}.\) Other, more precise estimates often involve the Riemann hypothesis, a deep and unsolved conjecture about the zeroes of a certain complex-valued function.

Still other elementary questions about the prime numbers remain open. In particular, the twin prime conjecture that there are infinitely many prime numbers \(p\) such that \(p+2\) is also prime, and the Goldbach conjecture that any even integer \(\ge 4\) can be written as a sum of two primes, are still unsolved despite centuries of efforts by countless mathematicians.

Results involving divisibility are often most easily stated using modular arithmetic. If two integers \(a\) and \(b\) leave the same remainder when divided by an integer \(n,\) we write \(a \equiv b \pmod n,\) read "\(a\) is congruent to \(b\) mod \(n.\)" For example, \(64 \equiv 1 \pmod 7,\) or \(-1007 \equiv 3 \pmod{10}.\)

Basic rules of modular arithmetic help explain various divisibility tests learned in elementary school. For instance,

Every positive integer is congruent \(\pmod 3\) to the sum of its digits.

For example, \(268 = 100 \cdot 2 + 10 \cdot 6 + 1 \cdot 8\) is congruent to \(1 \cdot 2 + 1 \cdot 6 + 1 \cdot 8,\) because \(100,10,\) and \(1\) are all congruent to \(1\) mod \(3.\) This holds for any power of \(10:\) \(10^k \equiv 1^k \equiv 1 \pmod 3,\) so the statement is true no matter how many digits the integer has.

The operations of addition, subtraction, and multiplication work as expected, but there is also a form of division. In particular, the equation \(x \equiv 1/a \pmod n\) makes sense if \(ax \equiv 1 \pmod n.\) Such an \(x\) exists if and only if \(\text{gcd}(a,n) = 1,\) by Bezout's identity.

The set \(\{0,1,\ldots,n-1\}\) of representatives of integers mod \(n,\) with operations given by modular addition and modular multiplication, is often called \({\mathbb Z}_n.\) The subset of \({\mathbb Z}_n\) consisting of invertible elements is called \({\mathbb Z}_n^*\); it is closed under multiplication and has \(\varphi(n)\) elements, where \(\varphi\) is Euler's totient function. In particular, when \(p\) is prime, \({\mathbb Z}_p^*\) consists of all the elements of \({\mathbb Z}_p\) except \(0,\) so it has \(p-1\) elements.

This is the setup for one of the first nontrivial theorems of elementary number theory, known as Fermat's little theorem.

If \(p\) is prime and \(p \nmid a,\) then \(a^{p-1} \equiv 1 \pmod p.\)

This generalizes to any modulus \(n\):

Euler's theorem: If \(\text{gcd}(a,n)=1,\) then \(a^{\varphi(n)} \equiv 1 \pmod n.\)

These theorems have a myriad of diverse applications to, for instance, primality testing, periods of decimal expansions of fractions, and modern cryptography. Some examples of the latter will be outlined in the following section.

Some basic problems in elementary number theory are well-suited for use in modern cryptography. Many cryptosystems require a computationally difficult one-way process, which is quick to do but hard to reverse. The two most common such processes both come from number theory.

One such process is factoring: it is easy for a computer to multiply two large prime numbers together, but very difficult to recover the prime numbers given their product. If \(N = pq\) where \(p,q\) are large prime numbers, finding \(p\) and \(q\) is equivalent in difficulty to finding \(\varphi(N) = pq-p-q+1.\) This fact, coupled with Euler's theorem, is the foundation of the widely-used RSA cryptosystem.

Another such process is the so-called discrete log problem: given coprime integers \(a\) and \(n\) (where \(n\) is taken to be very large), and an integer \(k,\) it is easy to compute \(a^k \pmod n,\) but it is difficult to recover \(k\) given \(a,n,\) and \(a^k \pmod n.\) This idea is the foundation of the Diffie-Hellman protocol.

More recently, these ideas have been extended and enriched by replacing modular arithmetic by the more exotic operations on points on elliptic curves.

Many of the oldest questions in number theory involve what are now known as Diophantine equations: polynomial equations in multiple variables with integer coefficients, where the unknowns are constrained to be integers as well. Indeed, the problem of finding the solutions to the simplest linear Diophantine equation, \(ax+by=c,\) is essentially the content of Bezout's identity.

Very simple Diophantine equations often have very difficult solutions. The techniques involved often come from other areas of mathematics, most notably algebraic geometry: the solutions to a Diophantine equation can be viewed as special points (points with integer coordinates) on a larger geometric object like a curve or surface, cut out by the real or complex solutions to the same equation.

For example, the positive integer solutions to Pythagoras's equation \(x^2+y^2=z^2,\) known as Pythagorean triples, were of interest more than 2500 years ago. Dividing through by \(z^2\) gives \((x/z)^2+(y/z)^2 = 1,\) so a Pythagorean triple corresponds to a point \((x/z,y/z)\) with rational coordinates on the circle \(X^2+Y^2=1.\) One way to parameterize all such points is via the geometric trick of starting with a rational point on the circle (say \((0,1)\)), drawing a line with rational slope through it, and looking for the other point of intersection, which is guaranteed to be rational. Parameterizing Pythagorean triples.^[1]

Generalizations of Pythagoras's equation abound, but the degree of difficulty rises quickly. In particular, increasing the exponent leads to a famously difficult theorem:

Fermat's last theorem: The equation \(x^n+y^n=z^n\) has no solutions in positive integers \(x,y,z\) for any integer value of \(n \ge 3.\)

Restricting attention to sums of squares leads to fundamental classical results about which integers can be expressed as sums of two, three, and four squares; in particular, every positive integer is the sum of four squares. Asking about sums of higher powers leads to an even deeper set of results known collectively as Waring's problem.

On the other hand, the Euler brick question in the introduction gives an example of a specific system of Diophantine equations whose solutions have not yet been determined. There is even a general negative result known as Hilbert's tenth problem that states that there can be no universal algorithm for determining whether any Diophantine equation has a solution. Current research in this area tends to center on specific types of Diophantine equations which are of particular interest to mathematicians for some reason (elliptic curves are an especially fertile subject), but there are still many unsolved problems along these lines.

Main article: Algebraic number theory

Here is a problem that can be solved using properties of rings other than the integers. (The preliminary analysis uses modular arithmetic in a common way as well.)

Find all integer solutions to \(y^2=x^3-1.\)

---

Here is a proof sketch.

First note that if \(x\) is even, then \(y^2 \equiv 3 \pmod 4,\) which is impossible, so \(x\) is odd and thus \(y\) is even. Rewrite as \(y^2+1=x^3\) and factor \[ (y+i)(y-i) = x^3. \] Any common factor of \(y+i\) and \(y-i\) must be a common factor of their difference \(2i = (1+i)^2.\) It is not hard to check that \(1+i\) is prime, in the following sense: its only divisors are the units (divisors of 1) \(\pm 1, \pm i\) and unit multiples of itself. But if \(1+i\) divides \(y+i,\) say \((1+i)(c+di) = y+i,\) we get \(y=c-d\) and \(1 = c+d,\) which would imply that \(y\) was odd, which is impossible.

So \(y+i\) and \(y-i\) are relatively prime. Two numbers that are relatively prime whose product is a cube must both be cubes themselves. But \(y+i = (a+bi)^3\) gives \(y=a^3-3ab^2\) and \(1=3a^2b-b^3 = b(3a^2-b^2).\) This only works if \(b\) and \(3a^2-b^2\) are both \(\pm 1,\) which is only possible if \(b=-1\) and \(a=0.\) This leads to \(y=0,x=1,\) which is the only solution.

The proof sketch above can be made rigorous, but there are some holes in the proof as written--in particular, the first two sentences of the last paragraph assume that the Gaussian integers, the complex numbers of the form \(a+bi\) where \(a,b\) are integers, have similar properties to the integers themselves. In particular, there needs to be a well-defined sense of "relatively prime" and an analogue of the fundamental theorem of arithmetic in the ring \({\mathbb Z}[i]\) of Gaussian integers.

While the ring \({\mathbb Z}[i]\) does have the properties required to make the above proof rigorous--most notably, a form of unique factorization into irreducible elements--other, similar rings do not have the same properties.

In the ring \({\mathbb Z}[\sqrt{-5}],\) factorization into irreducible elements is not necessarily unique. For example, \[ 6 = 2\cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) \] and each of the four factors is irreducible (its only factors are \(\pm\) itself or 1).

Incorrect assumptions about rings of this type led to false starts at proofs of Fermat's last theorem in the 19th century. The theory of such rings is beautiful and interesting on its own, but it also has many applications to down-to-earth questions about the integers. Here are a few examples:

• as in the example above, for many specific Diophantine equations, finding solutions and showing that a given solution set is complete by using arithmetic in a ring larger than the integers

• proofs of Fermat's two-square theorem (using the Gaussian integers) and Lagrange's four-square theorem (using quaternions)

• a deeper understanding of quadratic reciprocity and generalizations of it to higher reciprocity laws

• primality testing (via e.g. the Lucas-Lehmer primality test) and factorization algorithms (via e.g. the number field sieve)

The use of complex analysis to solve difficult number-theoretic problems has a rich history, dating back nearly 200 years to the French mathematician Dirichlet. The original motivating problem was the prime number theorem, which gives an effective asymptotic estimate for the number \(\pi(x)\) of primes \( \le x.\) Dirichlet himself used complex-analytic tools to prove his famous theorem on the density of primes in arithmetic progressions: he showed that for coprime positive integers \(a\) and \(n,\) there are infinitely many primes congruent to \(a\) mod \(n,\) but his actual result was much stronger--of the \(\varphi(n)\) possible congruence classes for a prime mod \(n,\) Dirichlet showed that the primes were (asymptotically) distributed equally among those classes.

The techniques of analytic number theory can often be described in the following general way:

• Create a complex-valued function related to number-theoretic objects of interest, such as prime numbers or sums of powers;

• Use tools of complex analysis (e.g. line integration, the residue theorem, analytic/meromorphic continuation) to gain analytic information about the function;

• Develop correspondences between analytic properties of the function and the original number-theoretic objects;

• Translate the analytic information to results (often, asymptotic estimates) of the number-theoretic objects one wishes to study.

A classical example of this technique involves the Riemann zeta function \[ \zeta(s) = \sum_{n=1}^{\infty} \frac1{n^s}, \] where \(s\) is a complex number whose real part is larger than \(1.\) Expressing \(\zeta(s)\) as a certain integral allows it to be extended (or "continued") to a function defined everywhere on the complex plane with the exception of a simple pole at \(s=1.\)

The relationship to the prime numbers comes via the Euler product representation \[ \zeta(s) = \prod_{p \text{ prime}} \frac1{1-p^{-s}}. \] Famously, facts about the values of \(s\) for which \(\zeta(s) = 0\) correspond to deep facts about the distribution of prime numbers. There are "trivial" zeroes at \( s = -2, -4, \ldots,\) but it is immediate from the form of the analytic continuation that the other zeroes must all lie in the strip \( 0 \le \text{Re}(s) \le 1.\) The Prime Number Theorem turns out to be equivalent to the statement that there are no zeroes on the edge of the strip, the line \(\text{Re}(s) = 1.\)

In fact, computational evidence suggests that all the zeroes lie in the center of the strip, \(\text{Re}(s) = 1/2;\) and this is the famous Riemann hypothesis. It is still unsolved, and it is of great interest precisely because it implies many interesting facts about the distribution of primes, including an improvement on the accuracy of the estimate given in the Prime Number Theorem.

Generalizations of the zeta function called Dirichlet series can be used to study other arithmetic functions as well.

Another famous result proved using analytic techniques (due to Hardy and Littlewood) was an explicit estimate of the number of powers involved in Waring's problem:

(Vinogradov) Let \(k\) be a positive integer. Every positive integer can be written as a sum of \(G(k)\) nonnegative \(k\)th powers, where \(G(k) \le 3k \log(k) + 11k.\)

See the article on Ramanujan for other examples.

1. Davis, J. Stereoprojzero. Retrieved April 28, 2007, from https://commons.wikimedia.org/wiki/File:Stereoprojzero.svg