Elementary number theory and
Terence Tao in 1985, when Erdős was 72 and Tao was 10 Elementary number theory deals with the topics in number theory by means of basic methods in arithmetic. Its primary subjects of study are
divisibility,
factorization, and
primality, as well as
congruences in
modular arithmetic. Arithmetic is the study of numerical operations and investigates how numbers are combined and transformed using the arithmetic operations of
addition,
subtraction,
multiplication,
division,
exponentiation, extraction of
roots, and
logarithms. Multiplication, for instance, is an operation that combines two numbers, referred to as factors, to form a single number, termed the
product, such as 2 \times 3 = 6. Divisibility is a property between two nonzero integers related to division. An integer a is said to be divisible by a nonzero integer b if a is a multiple of b; that is, if there exists an integer q such that a = bq. An equivalent formulation is that b divides a and is denoted by a vertical bar, which in this case is b | a. Conversely, if this were not the case, then a would not be divided evenly by b, resulting in a remainder.
Euclid's division lemma asserts that a and b can generally be written as a = bq + r, where the remainder r accounts for the smallest positive leftover quantity. Elementary number theory studies
divisibility rules in order to quickly identify if a given integer is divisible by a fixed divisor. For instance, it is known that any integer is divisible by 3 if its decimal
digit sum is divisible by 3. A common divisor of several nonzero integers is an integer that divides all of them. The
greatest common divisor (gcd) is the largest of such divisors. Two integers are said to be coprime or relatively prime to one another if their greatest common divisor, and simultaneously their only divisor, is 1. The
Euclidean algorithm computes the greatest common divisor of two integers a,b by means of repeatedly applying the division lemma and shifting the divisor and remainder after every step. The algorithm
can be extended to solve a special case of
linear Diophantine equations ax + by = 1. A Diophantine equation has several unknowns and integer coefficients. Another kind of Diophantine equation is described in the
Pythagorean theorem, x^2 + y^2 = z^2, whose solutions are called Pythagorean triples if they are all integers. Elementary number theory studies the divisibility properties of integers such as
parity (even and odd numbers),
prime numbers, and
perfect numbers. Important number-theoretic functions include the
divisor-counting function, the
divisor summatory function and its modifications, and
Euler's totient function. A
prime number is an integer greater than 1 whose only positive divisors are 1 and the prime itself. A positive integer greater than 1 that is not prime is called a composite number.
Euclid's theorem demonstrates that there are infinitely many prime numbers that comprise the set \{2,3,5,7,11,\cdots\}. The
sieve of Eratosthenes was devised as an efficient algorithm for identifying all primes up to a given natural number by eliminating all composite numbers.
Factorization is a method of expressing a number as a
product. Specifically in number theory,
integer factorization is the decomposition of an integer into a product of integers. The process of repeatedly applying this procedure until all factors are prime is known as
prime factorization. A fundamental property of primes is shown in
Euclid's lemma. It is a consequence of the lemma that if a prime divides a product of integers, then that prime divides at least one of the factors in the product. The
unique factorization theorem is the fundamental theorem of arithmetic that relates to prime factorization. The theorem states that every integer greater than 1 can be factorised into a product of prime numbers and that this factorisation is unique up to the order of the factors. For example, 120 is expressed uniquely as 2 \times 2 \times 2 \times 3 \times 5 or simply 2^3 \times 3 \times 5.
Analytic number theory ζ(
s) in the
complex plane. The color of a point
s gives the value of ζ(
s): dark colors denote values close to zero and hue gives the value's
argument. on the
upper half plane. The region in grey is the standard
fundamental domain. Analytic number theory, in contrast to elementary number theory, relies on
complex numbers and techniques from analysis and calculus. Analytic number theory may be defined • in terms of its tools, as the study of the integers by means of tools from
real and
complex analysis; or • in terms of its concerns, as the study within number theory of estimates on the size and density of certain numbers (e.g., primes), as opposed to identities. It studies the distribution of primes, behavior of number-theoretic functions, and irrational numbers. Number theory has the reputation of being a field many of whose results can be stated to the layperson. At the same time, many of the proofs of these results are not particularly accessible, in part because the range of tools they use is, if anything, unusually broad within mathematics. The following are examples of problems in analytic number theory: the
prime number theorem, the
Goldbach conjecture, the
twin prime conjecture, the
Hardy–Littlewood conjectures, the
Waring problem and the
Riemann hypothesis. Some of the most important tools of analytic number theory are the
circle method,
sieve methods and
L-functions (or, rather, the study of their properties). The theory of
modular forms (and, more generally,
automorphic forms) also occupies an increasingly central place in the toolbox of analytic number theory.
Analysis is the branch of mathematics that studies the
limit, defined as the value to which a sequence or function tends as the argument (or index) approaches a specific value. For example, the limit of the sequence 0.9, 0.99, 0.999, ... is 1. In the context of functions, the limit of \frac1x as x approaches infinity is 0. The complex numbers extend the real numbers with the imaginary unit i defined as the solution to i^2 = -1. Every complex number can be expressed as x + iy, where x is called the real part and y is called the imaginary part. The
distribution of primes, described by the function \pi that counts all primes up to a given real number, is unpredictable and is a major subject of study in number theory. Elementary formulas for a partial sequence of primes, including
Euler's prime-generating polynomials have been developed. However, these cease to function as the primes become too large. The prime number theorem in analytic number theory provides a formalisation of the notion that prime numbers appear less commonly as their numerical value increases. One distribution states, informally, that the function \frac{x}{\log(x)} approximates \pi(x). Another distribution involves an offset logarithmic integral which converges to \pi(x) more quickly. One may ask analytic questions about
algebraic numbers, and use analytic means to answer such questions; it is thus that algebraic and analytic number theory intersect. For example, one may define
prime ideals (generalizations of
prime numbers in the field of algebraic numbers) and ask how many prime ideals there are up to a certain size. This question
can be answered by means of an examination of
Dedekind zeta functions, which are generalizations of the
Riemann zeta function, a key analytic object at the roots of the subject. This is an example of a general procedure in analytic number theory: deriving information about the distribution of a
sequence (here, prime ideals or prime numbers) from the analytic behavior of an appropriately constructed complex-valued function. Elementary number theory works with
elementary proofs, a term that excludes the use of
complex numbers but may include basic analysis. Small sieves, for instance, use little analysis and yet still belong to analytic number theory.
Algebraic number theory An
algebraic number is any
complex number that is a solution to some polynomial equation f(x)=0 with rational coefficients; for example, every solution x of x^5 + (11/2) x^3 - 7 x^2 + 9 = 0 is an algebraic number. Fields of algebraic numbers are also called
algebraic number fields, or shortly
number fields. Algebraic number theory studies algebraic number fields. It could be argued that the simplest kind of number fields, namely
quadratic fields, were already studied by Gauss, as the discussion of quadratic forms in
Disquisitiones Arithmeticae can be restated in terms of
ideals and
norms in quadratic fields. (A
quadratic field consists of all numbers of the form a + b \sqrt{d}, where a and b are rational numbers and d is a fixed rational number whose square root is not rational.) For that matter, the eleventh-century
chakravala method amounts—in modern terms—to an algorithm for finding the units of a real quadratic number field. However, neither Bhāskara nor Gauss knew of number fields as such. The grounds of the subject were set in the late nineteenth century, when
ideal numbers, the
theory of ideals and
valuation theory were introduced; these are three complementary ways of dealing with the lack of unique factorization in algebraic number fields. (For example, in the field generated by the rationals and \sqrt{-5}, the number 6 can be factorised both as 6 = 2 \cdot 3 and 6 = (1 + \sqrt{-5}) ( 1 - \sqrt{-5}); all of 2, 3, 1 + \sqrt{-5} and 1 - \sqrt{-5} are irreducible, and thus, in a naïve sense, analogous to primes among the integers.) The initial impetus for the development of ideal numbers (by
Kummer) seems to have come from the study of higher reciprocity laws, that is, generalizations of
quadratic reciprocity. Number fields are often studied as extensions of smaller number fields: a field
L is said to be an
extension of a field
K if
L contains
K. (For example, the complex numbers
C are an extension of the reals
R, and the reals
R are an extension of the rationals
Q.) Classifying the possible extensions of a given number field is a difficult and partially open problem. Abelian extensions—that is, extensions
L of
K such that the
Galois group Gal(
L/
K) of
L over
K is an
abelian group—are relatively well understood. Their classification was the object of the programme of
class field theory, which was initiated in the late nineteenth century (partly by
Kronecker and
Eisenstein) and carried out largely in 1900–1950. An example of an active area of research in algebraic number theory is
Iwasawa theory. The
Langlands program, one of the main current large-scale research plans in mathematics, is sometimes described as an attempt to generalise class field theory to non-abelian extensions of number fields.
Diophantine geometry The central problem of Diophantine geometry is to determine when a
Diophantine equation has integer or rational solutions, and if it does, how many. The approach taken is to think of the solutions of an equation as a geometric object. For example, an equation in two variables defines a curve in the plane. More generally, an equation or system of equations in two or more variables defines a
curve, a
surface, or some other such object in -dimensional space. In Diophantine geometry, one asks whether there are any
rational points (points all of whose coordinates are rationals) or
integral points (points all of whose coordinates are integers) on the curve or surface. If there are any such points, the next step is to ask how many there are and how they are distributed. A basic question in this direction is whether there are finitely or infinitely many rational points on a given curve or surface. Consider, for instance, the
Pythagorean equation x^2+y^2 = 1. One would like to know its rational solutions, namely (x,y) such that
x and
y are both rational. This is the same as asking for all integer solutions to a^2 + b^2 = c^2; any solution to the latter equation gives us a solution x = a/c, y = b/c to the former. It is also the same as asking for all points with rational coordinates on the curve described by x^2 + y^2 = 1 (a circle of radius 1 centered on the origin). s, that is, curves of genus 1 having at least one rational point The rephrasing of questions on equations in terms of points on curves is felicitous. The finiteness or not of the number of rational or integer points on an algebraic curve (that is, rational or integer solutions to an equation f(x,y)=0, where f is a polynomial in two variables) depends crucially on the
genus of the curve. A major achievement of this approach is
Wiles's proof of Fermat's Last Theorem, for which other geometrical notions are just as crucial. There is also the closely linked area of
Diophantine approximations: given a number x, determine how well it can be approximated by rational numbers. One seeks approximations that are good relative to the amount of space required to write the rational number: call a/q (with \gcd(a,q)=1) a good approximation to x if |x-a/q|, where c is large. This question is of special interest if x is an algebraic number. If x cannot be approximated well, then some equations do not have integer or rational solutions. Moreover, several concepts (especially that of
height) are critical both in Diophantine geometry and in the study of Diophantine approximations. This question is also of special interest in
transcendental number theory: if a number can be approximated better than any algebraic number, then it is a
transcendental number. It is by this argument that Pi| and
e have been shown to be transcendental. Diophantine geometry should not be confused with the
geometry of numbers, which is a collection of graphical methods for answering certain questions in algebraic number theory.
Arithmetic geometry is a contemporary term for the same domain covered by Diophantine geometry, particularly when one wishes to emphasize the connections to modern algebraic geometry (for example, in
Faltings' theorem) rather than to techniques in Diophantine approximations.
Other subfields Probabilistic number theory starts with questions such as the following: Take an integer at random between one and a million. How likely is it to be prime? (this is just another way of asking how many primes there are between one and a million). How many prime divisors will have on average? What is the probability that it will have many more or many fewer divisors or prime divisors than the average? Combinatorics in number theory starts with questions like the following: Does a fairly "thick"
infinite set A contain many elements in arithmetic progression: a, a+b, a+2 b, a+3 b, \ldots, a+10b? Should it be possible to write large integers as sums of elements of A? , a primitive
digital computer used to find
primes and solve simple
Diophantine equationsThere are two main questions: "Can this be computed?" and "Can it be computed rapidly?" Anyone can test whether a number is prime or, if it is not, split it into prime factors; doing so rapidly is another matter. Fast algorithms for
testing primality are now known, but, in spite of much work (both theoretical and practical), no truly fast algorithm for factoring. == Applications ==