NUMBER THEORY

branch of mathematics concerned with the integers, or whole numbers, and generalizations of the integers. Number theory grew out of human curiosity concerning properties of the positive integers 1, 2, 3, 4, 5, . . . , also called whole numbers, natural numbers, or counting numbers. These numbers were the first mathematical creation of the human mind; interest in them is as old as civilization itself. Number theory has always fascinated amateurs as well as professional mathematicians. In contrast to other branches of mathematics, many of the problems and theorems of number theory can be understood by laymen, although solutions to the problems and proofs of the theorems often require sophisticated mathematical background. The intellectual challenge of number theory's unsolved problems has attracted noted mathematicians from the time of Pythagoras ( c. 540 #). Work on these problems has often led to the creation of new branches of mathematics. Until the mid-20th century, number theory was considered the purest branch of mathematics, with no direct applications to the real world. The advent of digital computers and digital communications revealed that number theory could provide unexpected answers to real-world problems. At the same time, improvements in computer technology enabled number theorists to make remarkable advances in factoring large numbers, determining primes, testing conjectures, and solving numerical problems once considered out of reach. Modern number theory is a broad subject that encompasses topics only indirectly connected with the integers. It is classified into subheadings such as elementary number theory, algebraic number theory, analytic number theory, geometric number theory, and probabilistic number theory. These categories reflect the methods used to shed light on problems concerning the integers. For example, algebraic number theory makes extensive use of abstract algebra, while analytic number theory employs calculus and complex function theory. Most of this article deals with elementary number theory and can be read with profit by anyone with a good background in high school algebra. More advanced topics, such as algebraic and analytic number theory, are discussed in later sections. branch of mathematics concerned with the integers (positive and negative natural numbers and zero), and generalizations of the integers. In ancient times, number theory was associated with numerology, the supposed mystical properties of numbers. Thus, some writers attached great significance in the coincidence that the biblical Creation took six days and that 6 is the smallest perfect numberthat is, one equal to the sum of its integral factors. Just as during the Renaissance astronomy gradually parted company with astrology and chemistry separated from alchemy, so did number theory throw off its association with numerology. The modern theory of numbers reaches into almost every branch of mathematics to borrow tools for the solution of problems. It is one of the most popular subjects of amateur mathematicians and students. This is largely explained by the wealth of easily explainable problems, some of them formulated by amateurs. Although it is not hard to ask a good question in number theory, it is quite another thing to find an answer. It has been said, and it is largely true, that any unsolved mathematical problem that is more than a century old and is still considered interesting belongs to number theory. One of the most famous problems of number theory is named after the 17th-century French mathematician Pierre de Fermat. Fermat was interested in the Diophantine equation xn + yn = zn (Diophantine equations are algebraic equations whose solutions are required to be integers or rational numbers). This equation has many integer solutions, such as 2-1 + 2-1 = 1-1, 61 + 71 = 131, 32 + 42 = 52, and 07 + 27 = 27, but if x and y stand for positive integers and n is an integer greater than 2, no solutions exist. Diophantine equations take their name from Diophantus of Alexandria (c. 250 AD); Fermat owned a copy of Diophantus' book Arithmetica and had the habit of making notes in the margin. Concerning the equation xn + yn = zn, Fermat wrote that he had a wonderful proof that it had no positive integer solutions with n at least 3, but the proof was too long for the margin. Although many mathematicians tried to find a proof for Fermat's statement, no one succeeded for 350 years, and it was long regarded as a conjecture. Attempts to prove Fermat's conjecture led to the development of another branch of number theory, the study of algebraic numbers. These are complex numbers that are roots of polynomial equations with integer coefficients. Any rational number is also an algebraic number; for example, 3/7 is a root of 7x - 3 = 0. Many irrational numbers are also algebraic; for example, (1 + )/2 and i (= ) are algebraic numbers, since the first is a root of x2 - x - 1 = 0 and the second is a root of x2 + 1 = 0. The connection with Fermat's conjecture is that if u is a root of xn + 1 = 0, but not a root of xm + 1 = 0 for any integer m 0 and d 2 or 3 (mod 4), the quadratic field Q() has a fundamental unit e = x + y where x and y are the least positive solutions of the Pell equation x2 - dy2 = -1, if positive solutions exist; otherwise x and y are the least positive solutions of x2 - dy2 = 1, which always exist. A fundamental unit is similarly obtained by solving one of the Pell equations x2 - dy2 = 4 if d > 1 and d 1 (mod 4). Algebraic number theory is often used to study Diophantine equations. For example, in the Diophantine equation y3 - x2 = 1, both x and y cannot be even and both cannot be odd because then the difference y3 - x2 would be even. Also, x cannot be odd when y is even because in that case y3 - x2 -1 (mod 4). Therefore, in any solution x must be even and y odd. One such solution is x = 0, y = 1, and this is the only solution with x = 0. A method to show that there are no further solutions is to enlarge the setting to the field Q(i) and write the equation in the form where x is assumed to be nonzero. Neither factor is a unit because x 0. If the Gaussian integers x + i and x - i had a common divisor p among the primes of Q(i), then p would divide their difference 2i, so p would be either 1 + i or 1 - i, the prime divisors of 2. In that case p2 = 2i, which is impossible because p2 divides y2 and y is odd. Unique factorization implies that both x + i and x - i are cubes of integers in Q(i). Hence x + i = (a + bi)3 for some choice of rational integers a and b, from which it follows, by equating real and imaginary parts, that x = a3 - 3ab2 and 1 = 3a2b - b3 = b(3a2 - b2). Thus, b = 1 and 3a2 - b2 = 1, from which it follows that b = -1, a = 0. Thus, x = 0, y = 1 is the only solution in integers of y3 - x2 = 1. A similar argument can be used to show that the Diophantine equation y3 = x2 + 2 has only two solutions in integers, x = 5, y = 3. The argument makes use of unique factorization of integers in the field Q(). There are only two units in this field, 1, which simplifies matters. Unique factorization of integers in the field Q() can be used to show that the Diophantine equation z3 = x3 + y3 has no solutions in positive integers. This field has six units, the three cube roots of 1 and their negatives. The roots are determined by solving the cubic equation The solutions are 1, w, and w2, where The number is a prime in this field. The Diophantine equation can now be written in the form from which it can be shown that each factor on the right is the cube of an integer in the field Q() multiplied by a unit of the field and some power of the prime . This information suffices to show that the equation z3 = x3 + y3 has no solutions in positive integers. The argument makes essential use of unique factorization in the field Q(). In the mid-19th century the German mathematician Ernst Eduard Kummer and others attempted to extend this argument to prove the Fermat conjecture that for any positive integer n > 2 there are no solutions of xn + yn = zn in positive integers. It suffices to consider only the case in which n is an odd prime p > 3. The idea was to factor xp + yp into linear factors and rewrite the equation in the form where The number z satisfies zp = 1, so z is a pth root of 1. The field Q(z) is called a cyclotomic field. Kummer realized that if the factor x + zy has the form eap for some algebraic integer a and some unit e in the cyclotomic field Q(z), he could settle the Fermat conjecture by an argument similar to that described above for the case p = 3. In fact, he showed that the equation x + zy = eap, with x and y not divisible by p, implies x y (mod p). A similar argument applied to the equation xp + (-z)p = (-y)p shows that x -z (mod p). Therefore so that 3xp 0 (mod p). But this is a contradiction because p > 3 and p does not divide x. The equation x + zy = eap, which is crucial to the foregoing argument, is valid if unique factorization holds for the integers in the cyclotomic field Q(z). The smallest prime p for which unique factorization fails in Q(z) is p = 23, but for values of p for which unique factorization holds, Kummer's argument shows that the Fermat equation xp + yp = zp has no positive solutions. Kummer was aware that the unique factorization property does not hold in every cyclotomic field, and he searched for another way to deduce the crucial equation x + zy = eap. He succeeded, in part, by introducing a new kind of complex number, which he called an ideal complex number and which permitted him to generalize the concept of unique factorization. He was then able to prove that the Fermat equation xp + yp = zp has no solutions for all primes p satisfying two special properties, but he was not able to determine whether all primes have these properties. The German mathematician Richard Dedekind rephrased Kummer's ideas and introduced the concept of an ideal. Elementary number theory Arithmetical functions Functions f(n) of the positive integer n that express some arithmetical property of n are called arithmetical functions. An important example is Euler's function f(n), which counts the number of integers in a reduced residue system mod n. Alternatively, f(n) is the number of positive integers less than n that are relatively prime to n, with the value f(1) = 1 defined separately. The following examples are concerned with divisors of n: The divisor function sk(n) can be expressed in summation notation as follows: where the sum is extended over all positive divisors of n. The functions d(n) and s(n) are, of course, special cases of sk(n) with k = 0 and k = 1, respectively. All these examples have the two special properties: Arithmetical functions with these properties are called multiplicative; they are completely determined by their values at the prime powers. Thus, if n is a product of powers of distinct primes, say n = pa qb , then f(n) = f(pa)f(qb) . For example, Because of the multiplicative property, this calculation is simpler than adding the squares of all the positive divisors of 24. The values of the foregoing functions at the prime powers are given by and Any arithmetical function f(n) can be used to generate another, by summing f(d) over all positive divisors d of n. This can also be written as Sd|nf(n/d), because as d runs through all positive divisors of n, from smallest to largest, n/d runs through the same divisors in opposite order, from largest to smallest. If the function f(n) is multiplicative, so is the divisor sum F(n), and conversely, if the divisor sum F(n) is multiplicative, so is f(n). Any arithmetical function f(n) can be determined from a knowledge of its divisor sum F(n) by the Mbius inversion formula, where m(n) is a multiplicative arithmetical function called the Mbius function, after the German mathematician August Ferdinand Mbius. Its values are 0, 1, and -1 and are obtained as follows: Because m(n) is multiplicative, m(n) = 0 if n is divisible by the square of any prime, and m(n) = (-1)r if n is the product of r distinct primes. The divisor sum is equal to 0 if n > 1 and is equal to 1 if n = 1. The Mbius inversion formula often reveals hidden properties of arithmetical functions. For example, it can be used to prove that the Euler function f(n) is multiplicative, a result that is not immediately evident. Each integer k from 1 to n has a GCD d = (k, n) with n; then k/d and n/d are relatively prime. Just as f(n) counts the number of integers from 1 to n that are relatively prime to n, so f(n/d) counts the number of integers q = k/d from 1 to n/d that are relatively prime to n/d. Therefore f(n/d) is also the number of k for which (k, n) = d. But there are n values of k altogether, so The Mbius inversion formula gives Thus f(n)/n is the divisor sum of the multiplicative function m(n)/n, so f(n)/n is also multiplicative, hence f(n) is multiplicative. Another arithmetical function of great interest is r2(n), the number of ways that n can be written as a sum of squares of two integers, positive, negative, or zero. In counting the number of ways, reversal of order is allowed. For example, there are four ways of writing 1 as a sum of two squares: 1 = 12 + 02 = (-1)2 + 02 = 02 + 12 = 02 + (-1)2, so that r2(1) = 4. Similarly, r2(2) = 4, r2(3) = 0, r2(4) = 4, r2(5) = 8, and r2(6) = 0. This function is not multiplicative because r2(1) 1. However, r2(n)/4 is multiplicative. Let p be a prime divisor of n with p 3 (mod 4), and let pk be the highest power of p that divides n. Euler proved that n is the sum of two squares if and only if k is even for every such prime divisor p. In other words, r2(n) = 0 if and only if n has at least one maximal prime power divisor pk with p 3 (mod 4) and k odd. There are infinitely many such n, the first few being n = 3, 6, 7, 11, 12, 14, 15, 19, 21, 22, 23, 24, 27, 28, 30. Some arithmetical functions are described by giving the first two function values f(1) and f(2) and then expressing f(n) for n 3 in terms of f(n - 1) and f(n - 2). For example, the Fibonacci numbers are defined by for n 3. In this particular case, the function values f(n) are often written as Fn. The first few terms are These numbers have many interesting properties. For example, and (for those familiar with matrix multiplication) the nth power of the matrix A = is for every n 2. The relation (-1)n = Fn + 1Fn - 1 - Fn2 is obtained by equating determinants in this matrix equation. Fibonacci numbers also have an interesting divisibility property: For example, F7|F14 because 7|14. This is easily verified because F7 = 13 and F14 = 377 = 13 29. Fibonacci numbers are just one example of a linear recurrence sequence, which is given by any two starting numbers x1 and x2 coupled with a recurrence relation of the form xn = Axn - 1 + Bxn - 2 for n 3, where A and B are given constants. This tells how to determine each term xn from the two earlier terms xn - 1 and xn - 2. Explicit formulas are available for expressing xn in terms of x1, x2, and the roots of the quadratic equation x2 = Ax + B. The formula for the Fibonacci numbers is where a and b are the roots of the quadratic equation x2 = x + 1, given by The number a, which also appears as a ratio in various geometric figures, is called the golden ratio. The ancient Greeks considered rectangles whose sides have ratio a to be the most pleasantly proportioned of all rectangles, aside from the square. They called them golden rectangles and believed that, for the ideal beauty of any figure (including the human form), the various parts should have the proportions of the golden ratio. Diophantine equations In elementary algebra the linear equation 6x - 9y = 29 with two unknowns x and y has infinitely many solutions. It can be satisfied by taking any value for x and letting y = (6x - 29)/9. But, if it is required that x and y be integers, there are no solutions because 6x - 9y is divisible by 3 for all integers x and y, whereas 29 is not. Equations involving one or more unknowns to be solved for integer or rational values of the unknowns are called Diophantine equations in honour of Diophantus of Alexandria, who dealt with such problems in his treatise Arithmetica (c. AD 250). Diophantine equations fall into three classes: those with no solutions, those with only finitely many solutions, and those with infinitely many solutions. The equation 6x - 9y = 29 has no solutions, but the equation 6x - 9y = 30, which upon division by 3 reduces to 2x - 3y = 10, has infinitely many. For example, x = 20, y = 10 is a solution, and so is x = 20 + 3t, y = 10 + 2t for every integer t, positive, negative, or zero. This is called a one-parameter family of solutions, with t being the arbitrary parameter.