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 is a positive integer, can a positive power ever be written as the sum of two positive 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 -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 are two integers, then (read " divides ") if and only if there is an integer such that
The integers have a division algorithm, where two integers can be divided with remainder: for any with there is a unique integer and a unique integer with satisfying Here is the quotient and is the remainder.
In the division algorithm, if and then So iterating the division algorithm gives a way to compute the greatest common divisor of and called the Euclidean algorithm. The greatest common divisor also satisfies Bezout's identity--the integers of the form are precisely the multiples of the greatest common divisor of and and in particular, the itself can be written as for some integers In fact, possible values of and 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 be a positive integer. If is a divisor of that is not equal to or (i.e. is a nontrivial proper divisor of ), then can be factored as where and are nontrivial proper divisors of Then we can break down and similarly to get an expression for 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 then is a nontrivial proper divisor. So Now has no nontrivial proper divisors, but does: so and
Integers greater than 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 being prime is about 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 such that is also prime, and the Goldbach conjecture that any even integer 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 and leave the same remainder when divided by an integer we write read " is congruent to mod " For example, or
Basic rules of modular arithmetic help explain various divisibility tests learned in elementary school. For instance,
Every positive integer is congruent to the sum of its digits.
For example, is congruent to because and are all congruent to mod This holds for any power of 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 makes sense if Such an exists if and only if by Bezout's identity.
The set of representatives of integers mod with operations given by modular addition and modular multiplication, is often called The subset of consisting of invertible elements is called ; it is closed under multiplication and has elements, where is Euler's totient function. In particular, when is prime, consists of all the elements of except so it has elements.
This is the setup for one of the first nontrivial theorems of elementary number theory, known as Fermat's little theorem.
If is prime and then
This generalizes to any modulus :
Euler's theorem: If then
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 where are large prime numbers, finding and is equivalent in difficulty to finding 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 and (where is taken to be very large), and an integer it is easy to compute but it is difficult to recover given and 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, 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 known as Pythagorean triples, were of interest more than 2500 years ago. Dividing through by gives so a Pythagorean triple corresponds to a point with rational coordinates on the circle One way to parameterize all such points is via the geometric trick of starting with a rational point on the circle (say ), drawing a line with rational slope through it, and looking for the other point of intersection, which is guaranteed to be rational.
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 has no solutions in positive integers for any integer value of
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
Here is a proof sketch.
First note that if is even, then which is impossible, so is odd and thus is even. Rewrite as and factor Any common factor of and must be a common factor of their difference It is not hard to check that is prime, in the following sense: its only divisors are the units (divisors of 1) and unit multiples of itself. But if divides say we get and which would imply that was odd, which is impossible.
So and are relatively prime. Two numbers that are relatively prime whose product is a cube must both be cubes themselves. But gives and This only works if and are both which is only possible if and This leads to 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 where 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 of Gaussian integers.
While the ring 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 factorization into irreducible elements is not necessarily unique. For example, and each of the four factors is irreducible (its only factors are 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
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 of primes 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 and there are infinitely many primes congruent to mod but his actual result was much stronger--of the possible congruence classes for a prime mod 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 where is a complex number whose real part is larger than Expressing 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
The relationship to the prime numbers comes via the Euler product representation Famously, facts about the values of for which correspond to deep facts about the distribution of prime numbers. There are "trivial" zeroes at but it is immediate from the form of the analytic continuation that the other zeroes must all lie in the strip 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
In fact, computational evidence suggests that all the zeroes lie in the center of the strip, 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.
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 be a positive integer. Every positive integer can be written as a sum of nonnegative th powers, where
See the article on Ramanujan for other examples.
- Davis, J. Stereoprojzero. Retrieved April 28, 2007, from https://commons.wikimedia.org/wiki/File:Stereoprojzero.svg