This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
4 2 n > 2n, 9
so Equation (1.14) becomes k(p) =
2n n −2 = 2 − 2 = 0. p p
We deduce that p 23 n for every prime factor p of N . It follows that
log p
p|N
p2n/3
log p
4 n log 2 3
(1.16)
by Lemma 1.8. Now if k(p) 2 then by the bound (1.15), 2 log p k(p) log p log 2n, √ √ so p 2n and thus there are at most 2n possible values of p. Hence √ k(p) log p 2n log 2n. k(p)2
Together with the inequality (1.16), this shows that
1.3 Listing the Primes
log N
log p +
k(p)=1
log p +
21
k(p) log p
k(p)2
√
2n log 2n
p|N
√ 4 log 2 + 2n log 2n. 3
(1.17)
Now N is the largest coefficient (namely the middle one) in the binomial expansion of 22n = (1 + 1)2n ,
so 22n = 2 +
2n 2n 2n + +· · · + 2nN. 1 2 2n − 1
Substituting this estimate into the inequality (1.17) gives 2n log 2
√ 4 n log 2 + log 2n + 2n log 2n. 3
(1.18)
It is clear that the inequality (1.18) cannot hold for large values of n; a simple calculation shows that (1.18) implies that n does not exceed 500. It follows that if n > 500, then there is a prime satisfying the inequality (1.13). A calculation confirms that (1.13) also holds for all n 500, completing the proof of the theorem. Notice that a consequence of Equation (1.13) is that if the primes are listed in order as p1 , p2 , . . . , then pn+1 < 2pn for all n 1.
(1.19)
It is clear that Theorem 1.9 gives another proof that there must be infinitely many primes. In each interval of the form (n, 2n] there is at least one. This gives us a bound for the prime counting function π(X) = |{p X | p ∈ P}. The proof of Euclid’s Theorem 1.2 already says a little more than the purely qualitative statement that π(X) → ∞ as X → ∞: from the proof of Theorem 1.2 we see that pn+1 p1 p2 · · · pn + 1. This tells us something about π(X). Define a sequence (un ) by setting u1 = 2 and un+1 = u1 · · · un + 1 for n 1. Then π(X) min{n | un X}. This is an extremely slowly growing sequence, and the bound obtained for π(X) is very far from the truth.
22
1 A Brief History of Prime
Theorem 1.9 says more: there are at least N primes in the interval (1, 2N ] = (1, 2] ∪ (2, 4] ∪ (4, 8] ∪ · · · ∪ (2N −1 , 2N ], so π(2N ) > N . It follows that π(X) is larger than C log(X) for some positive constant C, infinitely often. Something closer to the truth about the asymptotic behavior of π(X) is the Prime Number Theorem (Theorem 8.1). Finding more refined estimates for π(X) generally involves deep problems in analytic number theory. An exception is the result of Tchebychef, described in Exercise 8.7 on p. 162, which uses elementary methods to give better bounds for π(X). Bertrand’s Postulate is enough to exhibit a striking but impractical formula for the primes. More importantly, the bound (1.13) immediately motivates the question of whether the upper estimate 2n could be reduced, perhaps for all large n only, and this is the subject of ongoing research. Corollary 1.10. There exists a real number θ with the property that ·θ 22
· 2·
is a prime number for any number of iterations of the exponential. Proof. Let q1 be any prime, and choose a sequence of primes (qn ) with the property that 2qn < qn+1 < 2qn +1 . (1.20) This is possible by Bertrand’s Postulate. Now define functions f (1) , f (2) , . . . by f (1) (x) = log2 (x) and f (n+1) (x) = log2 (f (n) (x)) for n 1. Define sequences (un ) and (vn ) by un = f (n) (qn ) and vn = f (n) (qn + 1). By the inequality (1.20), qn < f (1) (qn+1 ) < f (1) (qn+1 + 1) < qn + 1, so by applying the increasing function f (n) we have un < un+1 < vn+1 < vn . It follows that the sequence (un ) is increasing and bounded above, so it converges. Let θ = lim un . n→∞
Define functions g Then
(n)
by g
(1)
(x) = 2x and g (n+1) (x) = 2g
g (n) (un ) < g (n) (θ) < g (n) (vn ),
(n)
(x)
for all n 1.
1.3 Listing the Primes
23
so qn < g (n) (θ) < qn + 1 for all n 1
as required.
Exercise 1.7. [Mills] A deep result of Ingham improves Equation (1.13) to say that there is a constant C such that pn+1 − pn < Cp5/8 n . Assuming this result, modify the proof of Corollary 1.10 to show that there n is a real number θ with the property that θ3 is a prime for all n 1. Exercise 1.8. [Richert] Use Theorem 1.9 to show that every integer greater than 6 is a sum of distinct primes. (Hint: Show this is true for the numbers 7 to 19, then use Theorem 1.9 to see that we can keep adding new primes to the set of sums obtained without missing out any integers). Exercise 1.9. [Dressler] (a) Modify the proof of Theorem 1.9 to show that pn+1 < 2pn − 10 for all n > 6. (Hint: Assume there is an integer n 1000 for which no prime p has the property n < p < 2n − 10, and consider the primes dividing N = 2n−10 n−10 .) (b)*Use your result to prove that every positive integer apart from 1, 2, 4, 6 and 9 can be written as a sum of distinct odd primes. 1.3.2 Mersenne Primes Mersenne3 noticed that 22 − 1 = 3, 23 − 1 = 7, 25 − 1 = 31, and 27 − 1 = 127 are all primes. He suggested on the basis of experiments that 2p − 1 would be a prime whenever p is a prime that exceeds by 3 or less an even power of 2. Lemma 1.11. If 2n − 1 is prime, then n is prime. Proof. We prove the contrapositive statement that n being composite forces 2n − 1 to be composite. If n = ab with a, b > 1, then 2n − 1 = (2a − 1)(2n−a + 2n−2a + · · · + 2a + 1), so 2n − 1 is composite.
The list of primes noticed by Mersenne does not continue uninterrupted because 211 −1 is composite. A prime of the form 2p −1 is known as a Mersenne 3
Marin Mersenne (1588–1648) was a French friar in the religious order of the Minims. He defended Descartes and Galileo against their theological critics and worked to undermine alchemy and astrology. He wrote on music as part of his studies in physics and mathematics.
24
1 A Brief History of Prime
prime. The next few Mersenne primes are 213 − 1, 217 − 1 and 219 − 1. It is not known if there are infinitely many Mersenne primes. That 219 − 1 is prime was known to Cataldi in 1588, and this was the largest known prime for 150 years. Fermat discovered that 223 − 1 is not prime in 1640; in 1732 Euler knew that 229 − 1 is not prime but that 231 − 1 is prime. It is worth pausing to say something about how this knowledge, which potentially requires the factorization of ten-digit numbers, accrued. Generally this involved a mixture of improving technique with congruences, some guile, and some heroic calculations. The first of several theoretical advances was discovered by Fermat and is now known as Fermat’s Little Theorem. Theorem 1.12. [Fermat’s Little Theorem] For any prime p and any integer a, ap ≡ a (mod p). In keeping with our philosophy about differing approaches, we present two proofs of Fermat’s Little Theorem. Combinatorial Proof. It is enough to prove the statement when a is a positive integer, so we use induction. The result is true for a = 1 because both sides are 1. Assume it is true for a = b. Now p p j p p p−1 (b + 1) = b + pb + · · · + pb + 1 = b j j=0
p! by the Binomial Theorem. For 0 < j < p, pj = j!(p−j)! has a numerator divisible by p and denominator not divisible by p; the Fundamental Theorem
of Arithmetic then shows that pj is divisible by p for j = 1, . . . , p − 1. So (b + 1)p ≡ bp + 1 ≡ b + 1
(mod p)
by the inductive hypothesis. Thus Fermat’s Little Theorem is proved.
Exercise 1.10. Prove that the product of any n successive integers is divisible by n!. A second, and often more useful, version of Fermat’s Little Theorem can be written as follows. Integers a and b are said to be coprime if gcd(a, b) = 1. For all a ∈ Z that are coprime to p, ap−1 ≡ 1 (mod p).
(1.21)
This form is easily seen to be equivalent to Theorem 1.12 as follows: ap − a = a(ap−1 − 1), so when p does not divide a the Fundamental Theorem of Arithmetic shows that p(ap−1 − 1) if and only if p(ap − a).
1.3 Listing the Primes
25
The second proof of Fermat’s Little Theorem proves the congruence (1.21) and uses slightly more sophisticated ideas from group theory. The virtue of this second proof is that it is quicker and (as we shall see) is better suited to generalization. It does require some properties of modular arithmetic (see Exercise 1.28 on p. 38). Proof Using Group Theory. Work in the group G = (Z/pZ)∗ of nonzero residues modulo p under multiplication. The residue of a generates a cyclic subgroup of G whose order must divide that of G by Lagrange’s Theorem. Since the order of G is (p − 1), we deduce Equation (1.21). This proof is something of an anachronism: Lagrange’s Theorem generalized Fermat’s Little Theorem. However, thinking of residues using group theory is a powerful tool and gives rise to many more results, so it is useful to begin thinking in those terms now. Exercise 3.6 on p. 62 gives a good example where a proof using group theory can be favourably compared with a proof that only uses congruences. Exercise 1.11. Fermat’s Little Theorem says that, for any prime p, 2p−1 − 1 is divisible by p. It sometimes happens that 2p−1 −1 is divisible by p2 . Find all the primes p with this property for p < 106 . Such primes are called Wieferich primes, and it is not known if there are infinitely many of them. Exercise 1.12. *A pair of congruences that arises in the Catalan problem (see p. 57) for odd primes p, q is pq−1 ≡ 1
(mod q 2 ) and q p−1 ≡ 1
(mod p2 ).
(1.22)
A pair of odd primes satisfying Equation (1.22) is called a Wieferich pair. Find all the Wieferich pairs with p, q < 104 . Exercise 1.13. An integer n is called a perfect number if it is equal to the sum of its proper divisors. Thus 6 = 1 + 2 + 3 is a perfect number. (a) If q = 2p − 1 is a Mersenne prime, prove that 2p−1 q is a perfect number. (b) Prove that if n is an even perfect number, then n has the form 2p−1 (2p −1) for some prime of the form 2p − 1. It is not known if there are any odd perfect numbers, but there are certainly no odd perfect numbers smaller than 10400 . Write Mn = 2n − 1 for the nth Mersenne number. The Mersenne numbers have special properties that make them particularly suitable for primality testing. The next result is the first of a series of results showing that divisors of Mn are quite prescribed when n is prime. Lemma 1.13. Suppose p is a prime and q is a nontrivial prime divisor of Mp . Then q ≡ 1 modulo p.
26
1 A Brief History of Prime
Again, we give two proofs. Proof Using the Euclidean Algorithm. The condition that q divides Mp amounts to 2p ≡ 1 (mod q). By Fermat’s Little Theorem, 2q−1 ≡ 1 modulo q. Let d = gcd(p, q − 1). If d = p, then p(q − 1) as required. The only other possibility is d = 1 since p is prime. By Theorem 1.23 (see p. 35), in this case there are integers a and b with 1 = pa + (q − 1)b. Notice that one of a and b must be negative. Now 2 ≡ 21 ≡ 2pa+(q−1)b ≡ (2p )a (2(q−1) )b ≡ 1a 1b ≡ 1
(mod q),
(1.23)
which is impossible as q > 1, so the result is proved.
In the preceding argument, we have made use of negative exponents of expressions modulo q, but only in the form 1−a ≡ 1 (mod q) for a > 0.
(1.24)
Proof Using Group Theory. Work in the group G of nonzero residues modulo q. In this group 2 generates a cyclic subgroup whose order divides p since 2p − 1 ≡ 0 modulo q. Since 2 is not the identity and p is prime, the order of 2 must be p. Again, by Lagrange’s Theorem, this order must divide the order of the group G, which is (q − 1). Example 1.14. Lemma 1.13 is a significant help in factorizing Mn . To see how this works, we present Fermat’s proof from 1640 that 223 − 1 is not prime. If q is a prime dividing 223 − 1, then q ≡ 1 modulo 23. Now 23n + 1 is a prime √ smaller than 223 − 1 only for n = 2, 12, 20, 26, 30, 36, 42, 44, 50, 56, 60, 62, 72, 84, 86, 102, 104, 110. Trial division shows that M23 is divisible by the first of the resulting numbers, 47. In general, there is no reason to expect the smallest possible candidate to be a divisor, but even if the largest were the first such divisor, only 18 trial divisions are involved. In 1876, Lucas discovered a test for proving the primality of Mersenne numbers. Using this test, he proved that 2127 − 1 = 170141183460469231731687303715884105727 is prime, but 267 − 1 is not. This disproved the suggestion of Mersenne. The latter number occupies a special place in the history (and folklore) of mathematics. First, Lucas showed it is not prime but was not able to exhibit a nontrivial factor, which might seem a remarkable idea. In fact, it is something we will encounter again in the computational number theory sections. Second,
1.3 Listing the Primes
27
this number was the subject of a famous talk given by Prof. F. N. Cole to the American Mathematical Society in 1903 entitled “On the Factorization of Large Numbers.” On one blackboard, he wrote out the decimal expansion of 267 − 1 and on another he proceeded to compute the product of 193707721 and 761838257287, thereby showing them to be equal. The legend goes that after this silent lecture he sat down to “prolonged applause.” The specific arithmetic properties of Mersenne numbers mean that results on the primality of later terms in the sequence sometimes predated results on earlier terms. For example, 2127 −1 was shown to be prime in 1876 while 289 −1 and 2107 − 1 were shown to be prime in 1914. Exercise 1.14. *[Lucas–Lehmer Test] Define an integer sequence by S1 = 4
and Sn+1 = Sn2 − 2
for n 2.
Let p be an odd prime. Prove that Mp = 2p − 1 is a prime if and only if Sp−1 ≡ 0 modulo Mp . 1.3.3 Zsigmondy’s Theorem Although the proof of the conjecture that there are infinitely many Mersenne primes seems a long way off, it is known that the sequence starts to produce new prime factors very quickly. A prime p is a primitive divisor of Mn if p divides Mn but does not divide Mm for any m < n. Table 1.2 shows the prime factorization of Mn for 2 n 24, with primitive divisors shown in bold. The pattern that seems to emerge from Table 1.2 turns out to reflect something genuine. Sequences such as the Mersenne sequence, after a few initial terms, always have primitive divisors. Theorem 1.15. [Zsigmondy] Let Mn = 2n −1. Then for every n = 6, n > 1, the term Mn has a primitive divisor. As seen in Table 1.2, M6 does not have a primitive divisor, so this result is optimal. The proof of Theorem 1.15 is presented in Section 8.3.1 on p. 167, after we have proved the M¨ obius inversion formula (Theorem 8.15). A basic result that will be needed for the proof can be proved now, using the Binomial Theorem. Notice that this result, proved as the next exercise, already shows that the divisors of the sequence (Mn ) have a special structure. Exercise 1.15. Let p denote a prime, and for any integer N , define ordp (N ) to be the exact power of p that divides N . Thus ordp (N ) = a means pa N but pa+1 N . (a) Prove that ordp behaves like a logarithm in the sense that ordp (xy) = ordp (x) + ordp (y) for all integers x, y. (b) Prove that if pMn then ordp (Mkn ) = ordp (Mn ) + ordp (k). (c) Deduce that gcd(Mn , Mm ) = Mgcd(n,m) for all m, n.
28
1 A Brief History of Prime Table 1.2. Primitive divisors of (Mn ). n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Mn Factorization 3 3 7 7 15 3·5 31 31 63 32 · 7 127 127 255 3 · 5 · 17 511 7 · 73 1023 3 · 11 · 31 2047 23 · 89 4095 3 · 5 · 7 · 13 8191 8191 16383 3 · 43 · 127 32767 7 · 31 · 151 65535 3 · 5 · 17 · 257 131071 131071 262143 33 · 7 · 19 · 73 524287 524287 1048575 3 · 52 · 11 · 31 · 41 2097151 7 · 127 · 337 4194303 3 · 23 · 89 · 683 8388607 47 · 178481 16777215 3 · 5 · 7 · 13 · 17 · 241
Exercise 1.16. (a) Show that if q is a prime then every prime divisor of Mq is a primitive divisor. (b) If Mn does not have a primitive divisor show that Mn divides the quantity Mn/p . n p|n, p
(c) Deduce that for n > 6, every term Mn has a primitive divisor if n has only two distinct prime divisors. (Hint: take logarithms of the quantities in (b) and compare the growth rates of both sides.) (d) What can you deduce if n has three distinct prime divisors? Zsigmondy’s Theorem holds in greater generality, though we will not prove the following result here. Theorem 1.16. [Zsigmondy] Let an = cn − dn , where c > d are positive coprime integers. Then an always has a primitive divisor unless (1) c = 2, d = 1 and n = 6; or (2) c + d = 2k and n = 2.
1.4 Fermat Numbers
29
Exercise 1.17. Find some nontrivial examples of case (2) of the theorem. A more general result is considered in Exercise 8.19 on p. 169. Exercise 1.18. Prove that the sequence (un ) does not satisfy a Zsigmondy Theorem in each of the following cases. This means that for every N there is a term un , n > N , which does not have a primitive divisor. (a) un = an + b for integers a and b; (b) un = n2 + an + b for integers a and b with the property that the zeros of x2 + ax + b are integers; (c)*un = n2 + an + b for integers a and b. Exercise 1.19. *Can any polynomial un = nd + ad−1 nd−1 + · · · + a0 for integers a0 , . . . , ad−1 have the property that the sequence (un ) satisfies a Zsigmondy Theorem? 1.3.4 Mersenne Primes in the Computer Age The arrival of electronic computers extended the limits of large Mersenne prime-hunting dramatically. Table 1.3 is a short list showing how the size of the largest known Mersenne prime has grown over recent years; #Mp denotes the number of decimal digits in Mp . In 1978, Nickol and Noll were 18-year-old students. We do not distinguish here between a Mersenne prime that is the largest known at the time from a Mersenne prime for which all smaller Mersenne primes are known; see the references for a more detailed discussion. In Table 1.3, (G) denotes GIMPS and (P) denotes PrimeNet; these are distributed computer searches using idle time on many thousands of computers all over the world. Because of the special properties of Mersenne numbers (and related numbers of special shape), it has usually been the case that the largest explicitly known prime number is a Mersenne prime.
1.4 Fermat Numbers n
Fermat noticed that the expression Fn = 22 + 1 takes prime values for the first few values of n: F0 = 3,
F1 = 5,
F2 = 17,
F3 = 257,
and
F4 = 65537.
He believed the sequence might always take prime values. Euler in 1732 gave the first counterexample, when he showed that 641F5 . Euler, in common with Fermat and many others, was able to perform these impressive calculations through a good use of technique to minimize the amount of calculation required. Since Euler’s time, many other Fermat numbers have been investigated and shown to be composite. No prime values
30
1 A Brief History of Prime
Table 1.3. Largest known prime values of Mp (from Caldwell’s Prime Pages [25]). p 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 110503 132049 216091 756839 859433 1257787 1398269 2976221 3021377 6972593 13466917 20996011 24036583
#Mp 6 6 10 19 27 33 39 157 183 386 664 687 969 1281 1332 2917 2993 3376 6002 6533 6987 13395 25962 33265 39751 65050 227832 258716 378632 420921 895932 909526 2098960 4053946 6320430 7235733
Date 1588 1588 1772 1883 1911 1914 1876 1952 1952 1952 1952 1952 1957 1961 1961 1963 1963 1963 1971 1978 1979 1979 1982 1988 1983 1985 1992 1994 1996 1996 1997 1998 1999 2001 2003 2004
Discoverer Cataldi Cataldi Euler Pervushin Powers Powers Lucas Robinson Robinson Robinson Robinson Robinson Riesel Hurwitz Hurwitz Gillies Gillies Gillies Tuckerman Nickol and Noll Noll Nelson and Slowinski Slowinski Colquitt and Welsh Slowinski Slowinski Slowinski and Gage Slowinski and Gage Slowinski and Gage Armengaud, Woltman et al. (G) Spence, Woltman et al. (G) Clarkson, Woltman, Kurowski et al. (G, P) Hajratwala, Woltman, Kurowski et al. (G, P) Cameron, Woltman, Kurowski et al. (G, P) Shafer, Woltman, Kurowski et al. (G, P) Findley, Woltman, Kurowski et al. (G)
of Fn with n > 4 have been discovered, and it is generally expected that only finitely many terms of the sequence (Fn ) are prime. To begin, we return to Euler’s result that 641 divides F5 . First, notice that 640 = 5 · 27 ≡ −1 modulo 641 so working modulo 641, 1 = (−1)4 ≡ (5 · 27 )4 = 54 · 228 . Now 54 = 625 ≡ −16 modulo 641 and 16 = 24 . Hence
1.5 Primality Testing
1 ≡ −232 ≡ −22
5
31
(mod 641).
Of course, this elegant argument is useful only once we suspect that 641 is a factor of F5 . Euler also used some cunning to reach that point. Lemma 1.17. Suppose p is a prime with pFn . Then p = 2n+1 k + 1 for some k ∈ N. Example 1.18. When n = 5, Lemma 1.17 shows that if p is a prime dividing F5 , then p = 26 k + 1 = 64k + 1 for some k. Thus the list of possible divisors is greatly reduced. We only have to test F5 for divisibility by 65, 129, 193, 257, 321, 385, 449, 513, 577, 641, . . . , of which 65, 129, 321, 385, 513, . . . are not primes. Therefore we only have to test 193, 257, 449, 577, 641, . . . and so on. At the fifth attempt, we find that 641F5 . n Proof of Lemma 1.17. Suppose p is a prime with pFn , so 22 ≡ −1 modulo p and p is odd. Hence 22
n+1
n
= (22 )2 ≡ (−1)2 ≡ 1
(mod p).
Let d = gcd(2n+1 , p − 1), and write d = 2n+1 a + (p − 1)b for integers a and b using Theorem 1.23. Just as in Equation (1.23) one of a and b will be negative, so we again use Equation (1.24) to argue that 2d = 22
n+1
a+(p−1)b
≡ (22
n+1
)a (2p−1 )b ≡ 1
(mod p).
Since d2n+1 , d = 2c for some 0 c n + 1 so c
22 = 2d ≡ 1 (mod p). n
However, 22 ≡ −1 modulo p and −1 ≡ 1 modulo p, so the smallest possibility for c is (n + 1). Hence d = 2n+1 . On the other hand, d(p − 1) so p − 1 = k2n+1 as claimed. Exercise 1.20. Strengthen Lemma 1.17 by showing that any prime p dividing Fn must have the form 2n+2 k + 1 for some k ∈ N.
1.5 Primality Testing We have covered enough ground to take a first look at the challenges thrown up by primality testing. Given a small integer, one can determine if it is prime by testing for divisibility by known small primes. This method becomes totally unfeasible very quickly. We are really trying to factorize. The ability
32
1 A Brief History of Prime
to rapidly factorize large integers remains the Holy Grail of computational number theory. Later we will look at some more sophisticated techniques and estimate the range of integers for which they are applicable. For now, we concentrate on properties of primes that can be used to help determine primality. Fermat’s Little Theorem is an example, although it does not give a necessary and sufficient condition for primality, just a necessary one. The next result does give a necessary and sufficient condition; it is known as Wilson’s Theorem because of a remark to this effect allegedly made by John Wilson in 1770 to the mathematician Edward Waring. An early proof was published by Lagrange in 1772. The theorem first seems to have been noted by al-Haytham4 some 750 years before Wilson. Theorem 1.19. An integer n > 1 is prime if and only if (n − 1)! ≡ −1 (mod n). Proof of ‘only if’ direction. We prove that the congruence is satisfied when n is prime and leave the converse as an exercise. Assume that n = p is an odd prime. (The congruence is clear for n = 2.) Each of the integers 1 < a < p − 1 has a unique multiplicative inverse distinct from a modulo p (see Corollary 1.25). Uniqueness is obvious; for distinctness, note that a2 ≡ 1 modulo p implies p(a+1)(a−1), forcing a ≡ ±1 modulo p by primality. Thus in the product (p − 1)! = (p − 1)(p − 2) · · · 3 · 2 · 1, all the terms cancel out modulo p except the first and the last. Their product is clearly −1 modulo p. Exercise 1.21. Prove the converse: If n > 1 and (n − 1)! ≡ −1 modulo n, then n is prime. Exercise 1.22. [Gauss] Prove the following generalization of Theorem 1.19. Let Pn = m m
be the product of all positive integers less than n and coprime to n. Then Pn +1 is divisible by n if n is equal to 4, pk , or 2pk for some odd prime p, and Pn − 1 is divisible by n if n is not of that form. 4
Abu Ali al-Hasan ibn al-Haytham (964–1040) lived in Persia and Egypt. He is most famous for Alhazen’s Problem: Find the point on a spherical mirror where a light will be reflected to an observer. In number theory, in addition to proving what we often call Wilson’s Theorem, al-Haytham worked on perfect numbers (see Exercise 1.13).
1.5 Primality Testing
33
Exercise 1.23. [Clement] (a) Use al-Haytham’s Theorem (Theorem 1.19) to prove that, for n > 1, n and n + 2 are both prime if and only if
4 (n − 1)! + 1 + n ≡ 0 (mod n(n + 2)). (b) Prove that, for n > 13, the triple n, n + 2, and n + 6 are all prime if and only if
4320 4 (n − 1)! + 1 + n + 361n(n + 2) ≡ 0 mod n(n + 2)(n + 6) . (c) Find a similar characterization of prime triples of the form n, n + 4, and n + 6. Primes p for which p + 2 is also a prime are called twin primes, and it is a long-standing conjecture that there are infinitely many twin primes. A remarkable result of Brun from 1919 is that the reciprocals of the twin primes (whether there are infinitely many or not) are summable: p,p+2∈P
1 = B < ∞. p
(1.25)
Numerical estimation of Brun’s constant B is very difficult. Exercise 1.24. Theorem 1.19 gives another ‘formula’ for the primes. Show that (n − 2)! is congruent to 1 or 0 modulo n depending on whether n is prime or not, for n 3. (a) Deduce that the prime counting function π(X) = |{p ∈ P | p X}| may be written π(X) = 1 +
X j=3
(j − 2)! (j − 2)! − j j
, X 3,
with π(1) = 0, π(2) = 1. (b) Define a function f by f (x, x) = 0 and 1 x−y f (x, y) = 1+ for x = y. 2 |x − y| Use Theorem 1.9 to prove that n
pn = 1 +
2
f (n, π(j)).
j=1
In principle, Theorem 1.19 seems to offer a general primality test because the condition is necessary and sufficient. The problem is that in practice it is impossible to compute (n − 1)! modulo n in a reasonable amount of time
34
1 A Brief History of Prime
for any integer that is not quite small. In Chapter 12 we will seek to give a better understanding of what counts as “small” or “large” in terms of modern computing. Fermat’s Little Theorem offers another hope. Taking a = 2, Fermat’s Little Theorem implies that 2p−1 ≡ 1 (mod p) whenever p is prime.
(1.26)
At various times in history, it has been thought that a kind of converse might be true: If n is odd and 2n−1 ≡ 1 modulo n, might it follow that n is prime? Calculations tend to support this, and for n < 341 this does indeed successfully detect primality. Example 1.20. Testing the congruence 2n−1 ≡ 1 modulo n fails to detect the fact that n = 341 = 11 · 31 is composite. By Fermat’s Little Theorem, 210 ≡ 1 modulo 11 so 2340 ≡ 134 ≡ 1 modulo 11. Also 25 = 32 ≡ 1 modulo 31, so 2340 = (25 )68 ≡ 168 = 1 (mod 31). Thus 2340 − 1 is divisible by the coprime numbers 11 and 31, and hence by their product 341, so 2340 ≡ 1 modulo 341. However, Fermat’s Little Theorem says more than Equation (1.26): It gives the congruence ap−1 ≡ 1 (mod p) for any base a, not just a = 2. Taking a = 3 in Example 1.20, we quickly find 3340 ≡ 56 (mod 341), which contradicts Fermat’s Little Theorem with a = 3, showing that 341 cannot be prime. Notice the recurrence of a phenomenon encountered before: Using a = 3, we have shown that a number is not prime without exhibiting a nontrivial factor. This method suggests the following as a primality test. Given an integer n, choose numbers a at random with 1 < a < n and test to see if an−1 ≡ 1 modulo n. If not, then n is definitely composite. If the congruence is satisfied for several such a, we might view this as compelling evidence that n must be prime. Unfortunately, this also fails as a primality test. Exercise 1.25. Prove that n = 561 is a composite number that satisfies Fermat’s Little Theorem for every possible base by showing that a560 ≡ 1 modulo 561 for every a, 1 < a < n with gcd(a, 561) = 1. (Hint: Use Fermat’s Little Theorem on each of the factors 3, 11, and 17 of 561.) A composite integer that satisfies the congruence of Fermat’s Little Theorem for all bases coprime to itself is known as a Carmichael number ; these will be discussed in more detail in Section 12.5. It was not known whether there
1.6 Proving the Fundamental Theorem of Arithmetic
35
are infinitely many Carmichael numbers until 1994, when Alford, Granville, and Pomerance not only proved that there are infinitely many but gave some measure of how many there are asymptotically. The existence of infinitely many Carmichael numbers renders the test based on Fermat’s Little Theorem test too unreliable. Later, we will see however that a more sophisticated version is salvageable as a primality test.
1.6 Proving the Fundamental Theorem of Arithmetic We uncover Euclid’s real genius once we try to prove the Fundamental Theorem of Arithmetic. There are two parts to it: existence and uniqueness. The existence part is not difficult. Let n > 1 be an integer, and choose r with 2r > n. If n itself is not divisible by any a with 1 < a < n, then nothing else needs to be said. Otherwise, we can write n = ab with 1 < a, b < n. Again, if a and b cannot be factorized, further then we are done. If this is not the case then at least one of them can be factorized. Once we have done this r times, we have n = a1 · · · ar with each 1 < ai < n. This implies n 2r , giving a contradiction. Thus n must be a product of no more than r prime factors. It is when we come to the uniqueness part of the proof that we uncover a subtlety – namely, that the definition of prime as an irreducible element is not really adequate to prove the Fundamental Theorem of Arithmetic. Suppose we try to argue as follows: Consider two factorizations for n into primes, say p1 · · · p r = n = q 1 · · · q s . We would like to say that because p1 divides the right-hand side, it must divide one of the qi . However, if we are working with the definition of prime as irreducible, then we need a result that tells us that being irreducible forces this divisibility property. Such a result may be found using the Euclidean Algorithm. Later, we will see examples in rings that are closely related to Z whose elements have genuinely different factorizations into irreducibles. Exercise 1.26. Let A = {n ∈ N | n ≡ 1 (mod 4)}, and call n = 1 an A-prime if the only divisors of n in A are 1 and n. (a) Show that every element of A except 1 factorizes as a finite product of Aprimes. (b) Show that this factorization into A-primes is not unique. 1.6.1 The Euclidean Algorithm Given a, b > 0 in Z, we can always find q and r with a = bq + r and 0 r < b. Indeed, for q we can simply take the integer part a/b of a/b and then show that by defining r = a − bq we must have 0 r < b.
36
1 A Brief History of Prime
Something very interesting happens when we iterate this process. It will help to define q = q1 and r = r1 and continue to find quotients and remainders as follows: a = bq1 + r1 , 0 r1 < b b = r1 q 2 + r 2 , 0 r2 < r1 .. .. . . rn−3 = rn−2 qn−1 + rn−1 , rn−2 = rn−1 qn + rn , rn−1 = rn qn+1 + 0.
0 rn−1 < rn−2 0 rn < rn−1
The sequence of remainders is decreasing and each term is nonnegative, so the sequence must terminate. We have written rn for the last nonzero remainder, so rn rn−1 . We claim that rn is the greatest common divisor of a and b. Example 1.21. Let a = 17 and b = 11. Then the Euclidean Algorithm gives the equations 17 = 11 · 1 + 6, 11 = 6 · 1 + 5, 6 = 5 · 1 + 1, 5 = 1 · 5 + 0. The last nonzero remainder is the greatest common divisor of 17 and 11, which is clearly 1. To prove that rn = gcd(a, b), we need a better notion of greatest common divisor than the intuitive one. Definition 1.22. If a and b in Z are not both zero, d is said to be a greatest common divisor of a and b if (1) da and db; and (2) if d is any number with d a and d b, then d d. The first condition says d is a common divisor of a and b, while the second says it is the greatest such divisor. Note that we say “a” greatest common divisor rather than “the” greatest common divisor because if d satisfies this condition then −d will also satisfy the definition. If we work in N, then the greatest common divisor will be unique. The notation gcd(a, b) denotes the unique nonnegative greatest common divisor of a and b. If gcd(a, b) = 1, then we will call a and b coprime. Exercise 1.27. Using Definition 1.22, show that rn = gcd(a, b). (Hint: Work your way up and then down the chain of equations to verify the two properties.)
1.6 Proving the Fundamental Theorem of Arithmetic
37
The next result is fundamental to the structure of the integers; it is an easy consequence of the Euclidean Algorithm and is sometimes referred to as Bezout’s Lemma. Theorem 1.23. If d = gcd(a, b) with a, b ∈ Z not both zero, then there are numbers x, y ∈ Z with d = ax + by. (1.27) Proof. The idea is to work your way up the chain of equations in the Euclidean Algorithm, always expressing the remainder in terms of the previous two remainders. Writing ∗ for an integer, we get gcd(a, b) = rn = rn−2 − rn−1 qn = rn−2 (1 + qn qn−1 ) − rn−3 qn = rn−3 · ∗ + rn−4 · ∗ .. . = b · ∗ + r1 · ∗ = a · ∗ + b · ∗. Example 1.24. Using the equations from Example 1.21 we find that 1 = 6−5 = 6 − (11 − 6) = 2 · 6 − 11 = 2(17 − 11) − 11 = 2 · 17 − 3 · 11. Corollary 1.25. Let n > 1 and a denote elements of Z. Then a and n are coprime if and only if there exists x with ax ≡ 1 (mod n). That is, gcd(a, n) = 1 if and only if a is invertible modulo n. Proof. The congruence is equivalent to the existence of an integer y with ax + ny = 1. If a and n have a factor in common then that factor will also divide 1, so the congruence implies a and n are coprime. Conversely, if a and n are coprime then 1 is a greatest common divisor of a and n so we can use Theorem 1.23 to see that there are integers x and y with ax + ny = 1, which translates into the congruence.
38
1 A Brief History of Prime ∗
Exercise 1.28. Let p be a prime. Prove that the set (Z/pZ) of nonzero elements in Z/pZ forms a group under multiplication modulo p. One of the remarkable things about the Euclidean Algorithm is that it finds the greatest common divisor of two integers without factorizing either of them. We will see later how this has been exploited in powerful ways by computational number theory in recent years. Exercise 1.29. Prove the Fundamental Theorem of Arithmetic using Theorem 1.23. (Hint: This is done in greater generality on p. 47.) 1.6.2 An Inductive Proof of Theorem 1.1 We wish to prove that any natural number n has a decomposition n = p1 · · · pr into primes uniquely up to rearrangement of the prime factors. For n = 2, the theorem is clearly true. We proceed by induction. Suppose that the Fundamental Theorem of Arithmetic holds for all natural numbers strictly less than some a > 1. We want to deduce the Fundamental Theorem of Arithmetic for a. Let D = {d | d > 1, da} denote the set of non-identity divisors of a. The set D is nonempty since it contains a, so it has a smallest element, which we denote p. This smallest element must be a prime because if it had a nontrivial divisor that would be a smaller element of D. Thus we have a decomposition a = pb, p prime, b < a. Since b < a, by the inductive hypothesis, the Fundamental Theorem of Arithmetic holds for b, so there is a prime decomposition b = p 1 · · · ps into primes uniquely up to rearrangement. It follows that a = p · p1 · · · ps is a prime decomposition of a, and a has no other prime decomposition involving the prime p. Suppose that a has another prime decomposition, a = q1 · · · qr , in which the prime p does not appear. In particular, q1 = p. Moreover, by the definition of p, q1 > p since q1 ∈ D, 1 q1 − p < q1 . Let c = q2 · · · qr , and define a0 = a − pc = p(b − c) = (q1 − p)c. (1.28)
1.7 Euclid’s Theorem Revisited
39
Now 1 a0 < a and the divisors (b − c), (q1 − p), and c are all less than a. By the inductive hypothesis, the numbers a0 , (b − c), (q1 − p), and c all have unique prime decompositions. By Equation (1.28), the prime p must appear in any prime decomposition of a0 and therefore (by uniqueness) must also appear in the decomposition of (q1 − p) or that of c. Now p cannot appear in a prime decomposition of (q1 − p) because that would require pq1 , which is impossible, as p and q1 are distinct primes. Nor can p appear in a prime decomposition of c = q2 · · · qr by assumption. Thus the assumption of a second prime decomposition for a leads to a contradiction, completing the proof of the Fundamental Theorem of Arithmetic.
1.7 Euclid’s Theorem Revisited In this section, three further proofs of Theorem 1.2 are given, each interesting and suggestive in its own right. 1.7.1 What Did Euclid Really Prove? First, we return to the master’s proof. The following is a translation of Euclid’s proof taken from Joyce’s Web translation of Euclid’s Elements. In Euclid’s time, numbers were thought of as relatively concrete lengths of line segments. Thus, for example, a number A measures a number B if a stick of length A could be used to fit into a stick of length B a whole number of times. In modern terminology, A divides B. We start with Euclid’s Theorem in (an approximation of) Euclid’s language: OÉ prÀtoi ĆrijmoÈ pleÐouc eÊsÈ pantäc toÜ protejèntoc plăjouc prÿtwn ĆrijmÀn. A translation of this is the following theorem, which is Proposition 20 of Book IX in Euclid’s Elements. Theorem 1.26. The prime numbers are more than any assigned multitude of prime numbers. Proof. Let A, B, and C be the assigned prime numbers. I say that there are more prime numbers than A, B, and C. Take the least number DE measured by A, B, and C. Add the unit DF to DE. Then EF is either prime or not. First, let it be prime. Then the prime numbers A, B, C, and EF have been found, which are more than A, B, and C. Next, let EF not be prime. Therefore, it is measured by some prime number. Let it be measured by the prime number G. I say that G is not the same as any of the numbers A, B, and C.
40
1 A Brief History of Prime
If possible, let it be so. Now A, B, and C measure DE, and therefore G also measures DE. But it also measures EF . Therefore G, being a number, measures the remainder, the unit DF , which is absurd. Therefore G is not the same as any one of the numbers A, B, and C, and by hypothesis it is prime. Therefore, the prime numbers A, B, C, and G have been found, which are more than the assigned multitude of A, B, and C. Therefore, prime numbers are more than any assigned multitude of prime numbers. There is little between this argument and Euclid’s proof in modern form on p. 8. Euclid did not have our modern notion of infinity, so he proved that there are more primes than any prescribed number. He also often stated proofs using examples (in this case, what he really proves is that there are more than three primes), but it is clear he understood the general case. It is possible that part of the reason for this is the notational difficulties involved in dealing with arbitrarily large finite lists of objects. 1.7.2 A Topological Proof of Theorem 1.2 In 1955, Furstenberg gave a completely different type of proof of the infinitude of the primes using ideas from topology. Furstenberg’s Topological Proof of Theorem 1.2. Define a topology on the integers Z by taking as a basis the arithmetic progressions. For each prime p, let Sp denote the arithmetic progression pZ. Since
Sp = Z\ (pZ + 1) ∪ · · · ∪ (pZ + (p − 1)) , the set Sp is the complement of an open set, and thus is closed. Let S = p Sp be the union of all the sets Sp as p varies over the primes. If there are only finitely many primes, then S is a finite union of closed sets, and thus is closed. However, every integer except ±1 is in some Sp , so the complement of S is {1, −1}, which is clearly not open. It follows that S cannot be closed and therefore cannot be a finite union, so there must be infinitely many primes. In contrast with the other proofs of Theorem 1.2, this is qualitative – all it tells us about the prime counting function is that π(X) → ∞ as X → ∞. 1.7.3 Goldbach’s Proof Goldbach showed how one may use a sequence of integers with the property that an infinite subsequence are pairwise coprime to give a different proof. Goldbach’s Proof of Theorem 1.2. We claim that the Fermat numn bers Fn = 22 + 1 are pairwise coprime:. m = n =⇒ gcd (Fm , Fn ) = 1.
(1.29)
1.7 Euclid’s Theorem Revisited
41
The first step is to show by induction that Fm − 2 = F0 F1 · · · Fm−1 for all m 1.
(1.30)
To see why this is true, first note that F1 − 2 = F0 and assume that Equation (1.30) holds for m k. Then F0 F1 · · · Fk−1 Fk = (Fk − 2)Fk k k = 22 − 1 2 2 + 1 = 22
k+1
− 1 = Fk+1 − 2,
showing Equation (1.30) by induction. Thus for m > n, dFm , dFn =⇒ dFm − 2 =⇒ d2, which forces d to be 1 since all the Fn are odd numbers. This proves Equation (1.29). This in turn means there must be infinitely many primes. By Theorem 1.1, each Fn has a prime factor pn , say, and by Equation (1.29) these are all distinct. The proof using Fermat numbers actually does a little more than prove there are infinitely many primes. It also gives some insight into how many primes there are that are smaller than a given number. By the time we reach the number Fn , we must have seen at least n different primes, so log(X − 1) 1 log π(X) , log 2 log 2 which is approximately proportional to log log X. This is far weaker than the remark on p. 21. Notes to Chapter 1: The exact history of Theorem 1.1 is not clear, and it is likely that it was known and used long before it was explicitly stated. The earliest precise formulation and proof seems to be due to Gauss [67], but it could be argued that Euclid certainly knew that if a prime p divides a product ab, then p must divide a or b, and that his geometrical formalism and approach to exposition did not require him to consider products of more than three terms (see Section 1.7.1). Many of the proofs of Euclid’s Theorem are featured in the Prime Pages Web site [25]; Ribenboim’s book [125] describes no fewer than 11 proofs. Example 1.7 is related to subtle problems in algebraic number theory; see Ribenboim’s book [125] for a discussion and detailed references. That the positive values of a polynomial in several variables could coincide with the primes is essentially a by-product of Matijaseviˇc’s solution to one of Hilbert’s famous problems. Some of the history and references and two explicit polynomials are given in accessible form in the paper [85] of Jones, Sato, Wada and Wiens. The proofs of Lemma 1.8 and Theorem 1.9 are those of
42
1 A Brief History of Prime
Erd¨ os [51] and Kalmar, and may be found in Hardy and Wright [75]; that of Corollary 1.10 follows a survey paper of Dudley [46]. Bertrand’s Postulate (Theorem 1.9) was first proved by Tchebychef [151, Tome I, pp. 49–70, 63]. He also proved that for any e > 15 , there is a prime between x and (1 + e)x for x sufficiently large. The deep result of Ingham [80] has been improved a great deal — for example, Baker, Harman and Pintz [8] have shown that there is a prime in the interval [x − x0.525 , x] for x sufficiently large. Exercise 1.7 is due to Mills [107]. Exercise 1.8 comes from a paper of Richert [127]; Exercise 1.9 from a paper of Dressler [45]. Further material on Mersenne primes – and on large primes in general – may be found on Caldwell’s Prime Pages Web site [25]; Table 1.3 is taken from his Web site. A recent account of the GIMPS record-breaking prime is in Ziegler’s short article [167]. Zsigmondy’s Theorems 1.15 and 1.16 appeared first in his paper [168]; a more accessible proof may be found in a short paper by Roitman [132]. Deep recent work has extended this to a larger class of sequences: Bilu, Hanrot and Voutier have shown that for n > 30 the nth term of any Lucas or Lehmer sequence has a primitive divisor in their paper [15]. The current status of Fermat numbers and their factorization may be found on Keller’s Web site [88]. Parts of the intricate connection between group theory and the origins of modern number theory, and in particular a discussion of how Gauss used group-theoretic concepts long before they were formalized, are in a paper of Wußing [164]. For more on the very special numbers found in Exercise 1.11 see Ribenboim’s popular article [123]. The inductive proof of Theorem 1.1 in Section 1.6.2 is taken from Hasse’s classic text [76] and is attributed there to Zermelo. Hasse’s text is also the source of the statement of Euclid’s Theorem in Greek in Section 1.7.1. We thank David Joyce for permission to use the translation in Section 1.7 from his Web site [86]; this Web site is based on several translations of Euclid’s work, but the primary and most accessible source remains the translation by Heath [53]. Exercise 1.24 is taken from Hardy and Wright [75]. Furstenberg’s proof of Euclid’s Theorem appeared in [63]. Exercise 1.23 is taken from Clement’s paper [31]. Brun’s result in Equation (1.25) appeared originally in his paper [24]; a modern proof may be found in the book of LeVeque [100]. Finally, we make some remarks concerning Section 1.7.2. Using topology in this setting might seem odd, but perhaps Euler’s proof using the harmonic series seemed odd when it first appeared. We don’t wish to stretch the point, but it could just be that Furstenburg’s proof points forward to new ways of looking at arithmetic in just the same way as Euler’s did. Profound structures in the integers have certainly been uncovered using methods from ergodic theory, combinatorics, functional analysis, and Fourier analysis; see a survey paper of Bergelson [11], the book by Furstenberg [64], and a new approach in a paper of Gowers [72] for some of these startling results. In a similar vein, Green and Tao [73] have recently proved the deep result that the primes contain arbitrarily long arithmetic progressions.
2 Diophantine Equations
Diophantine equations are equations (very often involving polynomials with integer coefficients) in which the solutions are required to be integers. They have been studied since antiquity and are mathematically both challenging and attractive because of the great diversity of methods that are needed to understand them.
2.1 Pythagoras In this chapter, we are going to explore the relationship between the Fundamental Theorem of Arithmetic and the study of polynomial Diophantine problems. We begin with an equation handed down from antiquity, x2 + y 2 = z 2 .
(2.1)
We know that an equation of this kind is related to a right-angled triangle with side lengths x, y, and z. Right-angled triangles have been studied and used for four thousand years (at least). Equation (2.1) is called the Pythagorean equation to honor Pythagoras for his result connecting Equation (2.1) to rightangled triangles. We seek to identify all the integral solutions; that is, to find all triples of integers (x, y, z) that satisfy Equation (2.1). The main point in the first three sections of this chapter is to emphasize the symbiosis between properties of numbers and solutions of equations. To motivate what follows, rearrange the equation to read x2 = z 2 − y 2 = (z + y)(z − y).
(2.2)
If we knew that gcd(z + y, z − y) = 1, then we could apply the Fundamental Theorem of Arithmetic to argue that both (z + y) and (z − y) must themselves be squares and use the resulting equations to parametrize all triples of solutions.
44
2 Diophantine Equations
To refine the proof, we resort to a congruence argument. First, we may assume that the triple (x, y, z) contains no common prime factor – otherwise we may divide through by the square of that factor. A triple (x, y, z) is called a primitive solution of Equation (2.1) if x, y, and z have no common factor. Second, we may assume that only one of the three is even because if two are then the third must be, contrary to the primitive condition. Now the even one out (so to speak) cannot be z because x2 + y 2 ≡ 0 (mod 4) is impossible with x and y being odd. Thus we may suppose one of x or y is even. Without loss of generality, suppose it is x that is even. Write x = 2x and substitute into Equation (2.2) to give z−y z+y . x2 = 2 2 Notice that each of (z ±y)/2 must be an integer because z and y are both odd. More than that, they must be coprime because any common factor of any two of x, y, and z must divide the third. Hence, any common divisor of (z ± y)/2 will also divide their sum and their difference, z and y, and we are assuming the triple (x, y, z) is primitive. Thus at last we may apply the Fundamental Theorem of Arithmetic to deduce that (z ± y)/2 are both squares, say z + y = 2m2 , z − y = 2n2 , m > n.
(2.3)
We are assuming z and y are positive so z + y > z − y, giving the inequality between m and n. Solving Equation (2.3) for z and y and then using Equation (2.1) to find x gives the following characterization of primitive Pythagorean triples. Theorem 2.1. The primitive integral solutions of the Pythagorean equation x2 + y 2 = z 2 with even x are given by x = 2mn, y = m2 − n2 , z = m2 + n2 with m > n coprime integers, not both odd. The integers m > n are said to parametrize the solutions of the equation. Exercise 2.1. For any primitive solution of Equation (2.1) show that one of x, y, or z is divisible by 3, one by 4, and one by 5.
2.2 The Fundamental Theorem of Arithmetic in Other Contexts
45
Exercise 2.2. Finding integral solutions to Equation (2.1) is equivalent to finding rational solutions to x2 + y 2 = 1. Find the second point of intersection with the circle x2 + y 2 = 1 of the line with slope t through the point (1, 0), and show that letting t run through all rationals gives all rational solutions to x2 + y 2 = 1. Using geometry to construct new rational solutions of Diophantine equations from old ones is a powerful idea that will be taken up again in Section 5.1.
2.2 The Fundamental Theorem of Arithmetic in Other Contexts In the integers, the Fundamental Theorem of Arithmetic is a direct consequence of the existence of the Euclidean Algorithm. In certain rings, the two properties are not equivalent. For example, the Fundamental Theorem of Arithmetic holds in the ring of integer polynomials Z[x], even though this ring does not have a Euclidean Algorithm. Nonetheless, in many arithmetic contexts, the Fundamental Theorem of Arithmetic can be proven easily because one has a Euclidean Algorithm. We will consider only commutative rings with a multiplicative identity, written 1. Definition 2.2. A commutative ring R is Euclidean if there is a function N : R\{0} → N with the following properties: (1) N (ab) = N (a)N (b) for all a, b ∈ R, and (2) for all a, b ∈ R, if b = 0, then there exist q, r ∈ R such that a = bq + r and r = 0 or N (r) < N (b). Such a function is called a norm on R. Much of what follows can be done with weaker conditions. In particular, one does not need such a strong property as (1). However, in many cases, the norm does have this property, so we assume it to allow a speedier and more natural development of the argument. Example 2.3. The following are examples of Euclidean rings. (1) Let R = Z[i] denote the Gaussian integers, so R = {x + iy | x, y ∈ Z}, where i2 = −1. Setting N (x + iy) = x2 + y 2 shows that R is a Euclidean ring.
46
2 Diophantine Equations
(2) Let F denote any field and let R = F[x] be the ring of polynomials with coefficients in F. Define N (f ) = 2deg(f ) , where deg(f ) is the degree of f in F[x], which is defined for all nonzero elements of R. We prove the first of these; the second is an exercise. Proof that Z[i] Is Euclidean. Condition (1) of Definition 2.2 is easily verified by direct computation. For property (2), let a, b = 0 ∈ R and write ab−1 = p + iq with p, q ∈ Q. Now define m, n ∈ Z by m ∈ [p − 1/2, p + 1/2), n ∈ [q − 1/2, q + 1/2). Let q = m + in ∈ R and r = a − b(m + in). For r = 0, N (r) = N ((ab−1 − m − in)b) = N (p + iq − m − in)N (b) = N (p − m + i(q − n))N (b)
1 4
+
1 4
N (b) < N (b),
showing property (2).
Exercise 2.3. When R = Z, for any fixed a and b, the values of q and r in Definition 2.2(2) are uniquely determined. Is the same true when R = Z[i]? In any ring, we define greatest common divisors in exactly the same way as before. A greatest common divisor is defined up to multiplication by units (invertible elements). In any Euclidean ring, the function N can be used to define a Euclidean Algorithm, which can be used to find the greatest common divisor just as for the integers. Definition 2.4. In a ring R, (1) α divides β, written αβ, if there is an element γ ∈ R with β = αγ; (2) u is a unit if u divides 1; (3) π (not equal to zero nor to a unit) is prime if for all α, β ∈ R, π αβ =⇒ π α or π β; (4) a non-unit µ is irreducible if µ = αβ =⇒ α or β is a unit. Notice that u ∈ R is a unit if and only if there is some µ with uµ = 1. We write U (R) or R∗ for the units in the commutative ring R; this is an Abelian group under multiplication. If the recent clutch of definitions are new to you, we recommend the following exercise.
2.2 The Fundamental Theorem of Arithmetic in Other Contexts
47
Exercise 2.4. (a) Show that, in any commutative ring, every prime element is irreducible. (b) Show that, in a Euclidean ring, u is a unit if and √ only if N (u) = 1. (c) Show that there√are infinitely many units in Z[ 3].√ (d) Show that 3√+ −2 is an irreducible element of Z[ −2]. (e) Let ξ = −1+2 −3 and R = Z[ξ]. Prove that R is a Euclidean domain with ¯ and find all respect to the norm N (a + bξ) = a2 − ab + b2 = (a + bξ)(a + bξ) the units in R. Exercise 2.5. Prove the Remainder Theorem: For a polynomial f ∈ F[x], F a field, f (a) = 0 if and only if (x − a)f (x). Exercise 2.6. Give a different proof of Lemma 1.17 on p. 31 using group theory by considering the multiplicative group of units U (Z/Fn Z) = (Z/Fn Z)∗ . Exercise 2.7. Prove that Z[x] does not have a Euclidean Algorithm by showing that the equation 2f (x) + xg(x) = 1 has no solution for f, g ∈ Z[x], but 2 and x have no common divisor in Z[x]. Despite the conclusion of Exercise 2.7, the ring Z[x] does have unique factorization into irreducibles. We will say that a ring has the Fundamental Theorem of Arithmetic if either of the following properties hold. (FTA1) Every irreducible element is prime. (FTA2) Every nonzero non-unit can be factorized uniquely up to order and multiplication by units. Theorem 2.5. Every Euclidean ring has the Fundamental Theorem of Arithmetic. Proof. Clearly, every irreducible µ has N (µ) 2. Arguing as we did in Z shows we cannot keep factorizing into irreducibles forever, so the existence part is easy. To complete the argument, we just need to show that every irreducible is prime. This follows easily from Theorem 1.23. Let µ be an irreducible and suppose that µ divides αβ but µ does not divide α. Clearly, the greatest common divisor of µ and α is 1 because µ admits only itself and units as divisors and µ does not divide α, so we can write µx + αy = 1 for some x, y ∈ R by Theorem 1.23. Multiply through by β to obtain µxβ + αβy = β. Since µ divides both terms on the left-hand side, it must divide the right-hand side, and this completes the proof.
48
2 Diophantine Equations
2.3 Sums of Squares The resolution of the Pythagorean equation ( Equation (2.1)) is an elementary and well-known result. We are now going to show how the Fundamental Theorem of Arithmetic in other contexts can yield solutions to less tractable Diophantine equations. Consider the following problem: Which integers can be represented as the sum of two squares? That is, what are the solutions to the Diophantine problem n = x2 + y 2 ? When n is a prime, experimenting with a few small values suggests the following. Theorem 2.6. The prime p can be written as the sum of two squares if and only if p = 2 or p is congruent to 1 modulo 4. To prove this, we are going to use the Fundamental Theorem of Arithmetic in the ring of Gaussian integers R = Z[i] with norm function N : R → N defined by N (x + iy) = x2 + y 2 as in Example 2.3(1). Lemma 2.7. If p is 2 or a prime congruent to 1 modulo 4, then the congruence T 2 + 1 ≡ 0 (mod p) is solvable in integers. Proof. This is clear for p = 2 so suppose p = 4n + 1 for some integer n > 0. Using al-Haytham’s Theorem (Theorem 1.19), (p − 1)! = (p − 1)(p − 2) · · · 3 · 2 · 1 ≡ −1
(mod p).
Now 4n = p − 1 ≡ −1 (mod p), 4n − 1 = p − 2 ≡ −2 (mod p), .. . 2n + 1 = p − 2n ≡ −2n
(mod p).
It follows that (−1)(−2) · · · (−2n)(2n)(2n − 1) · · · 3 · 2 · 1 = (2n)!(−1)2n ≡ −1 Thus T = (2n)! has T 2 + 1 ≡ 0 modulo p, proving the lemma.
(mod p).
Proof of Theorem 2.6. The case p = 2 is trivial. The case when p is congruent to 3 modulo 4 is also dealt with easily; no integer that is congruent
2.3 Sums of Squares
49
to 3 modulo 4 can be the sum of two squares because squares are 0 or 1 modulo 4. Assume that p is a prime congruent to 1 modulo 4. By Lemma 2.7, we can write cp = T 2 + 1 = (T + i)(T − i) in R = Z[i] for some integers T and c. Suppose (for a contradiction) that p is irreducible in R. Then since Z[i] has the Fundamental Theorem of Arithmetic, p is prime. Hence p must divide one of T ± i in R since it divides their product, and this is impossible because p does not divide the coefficient of i. It follows that p cannot be irreducible in R, so p = µν is a product of two non-units in R. Taking the norm of both sides shows that p2 = N (µν) = N (µ)N (ν). This is an equation in Z, so by the Fundamental Theorem of Arithmetic there are three possibilities. 1. N (µ) = 1 and N (ν) = p2 , which is impossible since µ is not a unit; 2. N (ν) = 1 and N (µ) = p2 , which is impossible since ν is not a unit; 3. N (µ) = N (ν) = p, which must be the case, and this means there is a nontrivial solution to the equation x2 + y 2 = p. What is being witnessed here is a symbiotic relationship between certain Diophantine equations and the structure of an associated ring. To illustrate this, we now give a theorem that characterizes the primes of Z[i]. Theorem 2.8. The primes of R = Z[i] are of three types, (1) 1 + i, (2) integer primes p ≡ 3 modulo 4, (3) factors x ± iy of the integer primes p ≡ 1 modulo 4, together with all multiples of these types by units. Exercise 2.8. Prove Theorem 2.8. (Hint: Show that any prime in Z[i] divides a prime in Z.) Exercise 2.9. Prove that if a prime p is a sum of two squares, p = a2 + b2 , then this representation is unique (apart from the obvious changes). Exercise 2.10. Prove that the positive integer n is a sum of two squares if and only if every prime p with p ≡ 3 modulo 4 that divides n does so to an even exponent.
50
2 Diophantine Equations
2.3.1 Lagrange’s Four Squares Theorem One of the many classical results of elementary number theory extends Theorem 2.6 to all integers – at the expense of allowing more squares to be added together. Bachet conjectured the result, and Diophantus stated it; Fermat may have had a proof. The first published proof was that of Lagrange in 1770, which we now present. Lemma 2.9. Let p be an odd prime. Then there are integers a and b with a2 + b2 + 1 ≡ 0 (mod p). Proof. Define the sets
A=
and
a2 | 0 a
p−1 2
p−1 2 B = −b − 1 | 0 b . 2
No two elements of A are congruent modulo p, and no two elements of B are congruent modulo p. It follows that each of the sets A and B contains p+1 2 elements modulo p, so by the pigeonhole principle1 there must be an element of A that is equal to an element of B modulo p since there are only p distinct integers modulo p. Thus there are integers a and b with a2 + b2 + 1 ≡ 0 (mod p)
as required.
Theorem 2.10. [Lagrange] Every positive integer is a sum of four integer squares. Proof. The first step is to note the Euler four-square identity, (a2 + b2 + c2 + d2 )(w2 + x2 + y 2 + z 2 ) = (aw + bx + cy + dz)2 +(ax − bw − cz + dy)2 +(ay + bz − cw − dx)2 +(az − by + cx − dw)2 , which may be proved simply by expanding the right-hand side. This identity means that the property of being written as a sum of four squares is preserved under products. By the Fundamental Theorem of Arithmetic, it is therefore 1
The ‘pigeonhole’ principle states that if (Q + 1) letters are placed in Q pigeonholes, one pigeonhole must contain more than one letter. It is readily proved by contradiction.
2.3 Sums of Squares
51
sufficient to prove that any prime is a sum of four integer squares. It is clear that 2 = 12 + 12 + 02 + 02 is a sum of four integer squares, so it is enough to prove that any odd prime is a sum of four integer squares. Let p be an odd prime. By Lemma 2.9, there are integers a, b, c, d and m with mp = a2 + b2 + c2 + d2 . (2.4) If m = 1 then we are done, so assume that m > 1. The proof proceeds by finding an expression for m p as a sum of four squares, with 0 < m < m. This can be repeated, reducing the size of m each time, until we eventually must find an expression for the prime p itself as a sum of four squares. Now notice that if an even integer 2n is a sum of two squares, 2n = x2 +y 2 , then the integers x and y are either both even or both odd. It follows that the identity 2 2 x+y x−y n= + (2.5) 2 2 expresses n as a sum of two integer squares. Returning to Equation (2.4), if m is even, then either none, two, or four of the numbers a, b, c, d are even. Thus we can use Equation (2.5) twice to deduce that ( m 2 )p is a sum of four squares. In this case we have halved the size of m. If m is odd, write w≡a x≡b y≡c z≡d with − m 2 < w, x, y, z <
m 2.
(mod (mod (mod (mod
m) m) m) m)
Then
w2 + x2 + y 2 + z 2 < m2 and w2 + x2 + y 2 + z 2 ≡ 0 (mod m). It follows that w2 + x2 + y 2 + z 2 = km for some k, 0 < k < m. Now in Euler’s four-square identity (a2 + b2 + c2 + d2 )(w2 + x2 + y 2 + z 2 ) = (aw + bx + cy + dz)2 +(ax − bw − cz + dy)2 +(ay + bz − cw − dx)2 +(az − by + cx − dw)2 (2.6) the left-hand side is km2 p. By our choice of w, x, y, z we see that ax ≡ bw and dy ≡ cz modulo m, so (ax − bw − cz + dy)2 is divisible by m2 . A similar argument shows that
52
2 Diophantine Equations
(ay + bz − cw − dx)2 and (az − by + cx − dw)2 are also divisible by m2 . For the first term, aw + bx + cy + dz ≡ w2 + x2 + y 2 + z 2 ≡ 0
(mod m),
so the right-hand side of Equation (2.6) is divisible by m2 . It follows that the identity (2.6) can be divided through by m2 , resulting in an expression for kp as a sum of four squares, with 0 < k < m. Repeating this reduction a finite number of times will reduce m to 1, resulting in an expression for the odd prime p as a sum of four squares, completing the proof. Exercise 2.11. *[Legendre] Show that every integer not of the form 4n (8k + 7) is a sum of three integer squares. Exercise 2.12. Suppose a prime p is a sum of four squares. Is it true that the representation is unique? What if p is a sum of three squares?
2.4 Siegel’s Theorem In this section, we show how a direct application of the Fundamental Theorem of Arithmetic in rings that are larger than the integers, for example the Gaussian integers Z[i], can yield all the integral solutions to certain cubic equations. In the first example, we use the Fundamental Theorem of Arithmetic only in Z. Theorem 2.11. The only integral solution of the equation y 2 = x3 + x
(2.7)
is x = 0, y = 0. Proof. Let x and y be integers with y 2 = x3 + x. Write the right-hand side of the equation as x3 + x = x(x2 + 1). Any factor of x will divide x2 , so any factor common to x and x2 + 1 will also divide 1. Thus x and x2 + 1 must be coprime and hence, by the Fundamental Theorem of Arithmetic, both must be squares (since their product is y 2 ). Writing z 2 = x2 + 1, we see that 1 = z 2 − x2 = (z + x)(z − x). By the Fundamental Theorem of Arithmetic in Z, (z + x) and (z − x) must both be 1 or both be −1. Solving for x and z shows that x = 0 in both cases.
2.4 Siegel’s Theorem
53
Theorem 2.12. The only integral solution of the equation y 2 = x3 − 1
(2.8)
is x = 1, y = 0. For this equation, it looks as if we should factorize the right-hand side over Z, but it does not seem easy to get to the proof that way. Instead we factorize over a bigger ring that is also known to satisfy the Fundamental Theorem of Arithmetic. Proof of Theorem 2.12. Rewrite the equation as y 2 + 1 = x3 and then factorize the left-hand side as (y + i)(y − i) in Z[i]. We claim that the two factors y ± i must be coprime. To see why, let δ = gcd(y + i, y − i); δ must divide the difference y + i − (y − i) = 2i. However, we claim that no factor of 2 can divide y ± i. This is because x must be odd; if x is even then x3 ≡ 0 modulo 8, which means that y 2 + 1 ≡ 0 modulo 8 and this congruence has no solutions. We deduce that δ must be a unit, and the two factors y ± i are coprime in Z[i]. Applying the Fundamental Theorem of Arithmetic in Z[i], we deduce that each factor y + i, y − i must be a unit multiple of a cube. Since all units are themselves cubes, we deduce that each of y ± i is a cube in Z[i], so assume y + i = (a + bi)3 , a, b ∈ Z. Equating imaginary parts gives 1 = 3a2 b − b3 = b(3a2 − b2 ). By the Fundamental Theorem of Arithmetic in Z, the solutions are greatly restricted: b = (3a2 − b2 ) = ±1. If b = 1, then 3a2 − 1 = 1, which is impossible as no integer a has 3a2 = 2. The only alternative is b = −1, in which case a = 0, yielding the unique solution y = 0 and x = 1. √ Exercise 2.13. Use the preceding method in the ring Z[ −2] to prove that the only integral solutions of y 2 = x3 − 2 are x = 3, y = ±5. Later we will be thinking of the set of solutions to equations such as these geometrically, so we will describe the solutions as points (x, y) in the plane. Now consider the example y 2 = x3 − 3.
(2.9)
54
2 Diophantine Equations
Experimentation with small integers suggests that there will be no integral solutions, but we encounter a difficulty when we try to prove this using the preceding methods. The reason is √ that the Fundamental Theorem of Arithmetic does not hold in the ring Z[ −3] (see Exercise 3.17 on p. 73.) On the other hand, the Fundamental Theorem of Arithmetic does hold in the bigger ring Z[ω], where ω = e2πi/3 is a nontrivial cube root of unity. This suggests that we might try to find all the solutions (x, y) over the ring Z[ω] as a precursor to finding all the solutions over the smaller ring Z. This might seem audacious but historically this is just what happened in the general case. Theorem 2.13. [Siegel’s Theorem] Suppose a, b, c ∈ Q. Then there are only finitely many integer pairs (x, y) with y 2 = x3 + ax2 + bx + c,
(2.10)
provided the cubic polynomial x3 + ax2 + bx + c has no repeated zeros. This theorem will not be proved here – see the notes at the end of the chapter for references where complete proofs may be found. The curve described by an equation of the shape Equation (2.10) is known as an elliptic curve provided the right-hand side has no repeated zeros. In order for Siegel’s Theorem to hold, some condition about the cubic polynomial is clearly needed because, for example, the equation y 2 = x3 has infinitely many integral solutions. We will devote considerable space to studying the remarkable properties of elliptic curves. Exercise 2.14. Prove that the polynomial x3 + ax + b has no repeated zero if and only if 4a3 + 27b2 = 0. The genius of people such as Siegel is that they are willing to take an imaginative step up from particular cases, and are in addition able to supply the guile needed to complete the proof. In fact, he gave two different proofs of Theorem 2.13. In his second proof Siegel showed that there are only finitely many solutions (x, y) with x and y lying inside a suitably large ring containing Z in which the Fundamental Theorem of Arithmetic holds. The rings in which Siegel proposed to work typically contain infinitely many units, in contrast with the integers Z. We can appreciate some of the technical difficulties he had to overcome by considering the techniques that went into his second proof in some special cases. His second proof turned out to be very important: He first reduced the given equation to a finite number of linear equations over a finitely generated group. Subsequently, methods were developed in Diophantine Approximation that applied to these linear equations and allowed, ultimately, a practical method for finding all the integral solutions of the equation in Theorem 2.13.
2.4 Siegel’s Theorem
55
√ Exercise 2.15. Fix a square-free integer d > 1, and assume that Z[ d] satisfies the Fundamental Theorem of Arithmetic. Show that the equation y 2 = x3 + d has only finitely many √ integral solutions. (Hint: You may assume that the units of the ring Z[ d] are all of the form ±un for some unit u > 1.) The rings Siegel worked with are obtained by inverting certain chosen primes. This technique provides us with a new class of rings to study. As a simple illustrative example, let S denote the set {2} and let ZS denote the ring Z[ 12 ] consisting of all rational numbers with a denominator consisting of a power of 2. Given any nonzero q ∈ Q, write q = 2r q , where r ∈ Z and the numerator and denominator of q are odd. Define the S-norm of q to be |q|S = |q |. The ring R has infinitely many units, consisting of the rational numbers ±2k for k ∈ Z. The ring R is sometimes called the ring of S-integers of Z, and its units are known as S-units. Exercise 2.16. Prove that the ring ZS is a Euclidean ring with respect to |.|S . The next exercise will provide a further illustration of some of the techniques needed to prove Siegel’s Theorem. We have already seen examples where the Fundamental Theorem √ of Arithmetic fails in some quadratic rings. We overcame that failure in Z[ −3] by working in the bigger ring R = Z[ω], where ω is a nontrivial cube root of unity. √ Letting S = {2} as before, R is a subring of an even bigger ring RS = Z[ −3, 12 ]. √ Exercise 2.17. Define a norm function on RS = Z[ −3, 12 ] with the property that RS is a Euclidean ring. Find all solutions to Equation (2.9) in the ring RS . Again, this exercise shows there are only finitely many solutions to a specific cubic equation in a ring with infinitely many units. Theorem 2.14 below is quite deep and we will not prove it. The proof requires Theorem 4.14 from Chapter 3. The notes at the end of the chapter reference a proof in√the literature. It shows that the Fundamental Theorem of Arithmetic in Z[ d] can be recovered by inverting a finite list of primes. Theorem 2.14. Let d be a nonsquare integer. There is a finite list of primes p1 , . . . , pr √ 1 with the property that Z[ d, p1 , . . . , p1r ] has the Fundamental Theorem of Arithmetic. Combining the techniques learned thus far allows a special case of Siegel’s Theorem to be proved. An integer is called square-free if it is not divisible by the square of any integer greater than 1.
56
2 Diophantine Equations
Exercise √ 2.18. Suppose d < 0 is a square-free integer with the property that Z[ d, p1 ] has the Fundamental Theorem of Arithmetic for some prime p. Show that the equation y 2 = x3 + d (2.11) has only finitely many integral solutions. When explicit approaches such as this succeed, they allow the determination of all the integral solutions. Determining all the integral solutions predicted by Siegel’s Theorem is generally quite a difficult problem and requires powerful methods from transcendence theory. It was not until late in the twentieth century that these methods were sufficiently well advanced to allow for a practical method of solving a given equation. An S-unit equation is one of the form a1 x1 + · · · + an xn = 1 with ai fixed constants in some field K, and the solutions xi are sought in a finitely generated subgroup of K∗ . For the cubic equations studied here, Siegel reduced the problem of finding all the integral solutions to finding the solutions of a finite number of S-unit equations all having n = 2. He then showed that such an equation has only finitely many solutions. In general Sunit equations turn out to lie behind many other Diophantine equations and they have come to be studied as important in their own right.
2.5 Fermat, Catalan, and Euler Finally we mention three famous Diophantine problems, all of which have recently been solved. There are detailed references in the notes at the end of the chapter. 2.5.1 Fermat Fermat’s Last Theorem, now proved by Wiles, states that the equation xn + y n = z n ,
n 3,
(2.12)
has no nontrivial solutions. (A solution is trivial if one of x, y or z is zero.) Clearly, it is only necessary to prove this in the case when n = p is a prime. A startling aspect of the solution is that it depends on deep results concerning the arithmetic of elliptic curves: If ap + bp + cp = 0 for a prime p and integers a, b, c, then the elliptic curve with equation y 2 = x(x − ap )(x + bp ) turns out to have properties that Wiles was able to show were impossible. We will be studying the arithmetic of elliptic curves in Chapters 5 and 6.
2.5 Fermat, Catalan, and Euler
57
Exercise 2.19. *Prove that Equation (2.12) has no nontrivial solutions with n equal to 3, 4, or 5. Exercise 2.20. *Prove that Equation (2.12) has no nontrivial solutions in Gaussian integers with n = 4. Exercise 2.21. *Prove that Equation (2.12) has no solutions x, y, z in positive integers with n a Gaussian integer. 2.5.2 Catalan The Catalan equation is ux − v y = 1,
u, v, x, y ∈ N,
u, v, x, y 2.
(2.13)
A solution is 32 − 23 = 1; the Catalan problem is to show that there are no others, and this has recently been proved. 2.5.3 Euler Euler conjectured that an nth power cannot be written as the sum of fewer than n nontrivial nth powers for n 3. Lander and Parkin made a computer search for nontrivial solutions to the Diophantine equation n
x5i = y 5 ,
n 6.
i=1
Among the solutions, they found a counterexample to Euler’s conjecture for n = 5. Their resulting announcement matches the famous seminar of Cole described on p. 27 for its brevity and drama: The entire text of their paper is as follows. “A direct search on the CDC 6600 yielded 275 + 845 + 1105 + 1335 = 1445 as the smallest instance in which four fifth powers sum to a fifth power. This is a counterexample to a conjecture by Euler [see L. E. Dickson, History of the theory of numbers, Vol. 1, p. 648, Chelsea, New York, 1952] that at least n nth powers are required to sum to an nth power, n > 2.” In addition, it was shown that the case n = 4, namely the Diophantine equation u4 + v 4 + w4 = x4 , (2.14) has no solutions in positive integers with x < 220000.
58
2 Diophantine Equations
In a dramatic development, Elkies used a mixture of sophisticated theory and a computer search to find a solution to Equation (2.14), 26824404 + 153656394 + 187967604 = 206156734 .
(2.15)
Following this, Roger Frye found that the minimal solution to Equation (2.14) is 958004 + 2175194 + 4145604 = 4224814 and showed that there are no other solutions with u v w < x < 1000000. Notes to Chapter 2: Much of the material in this chapter is part of algebraic number theory. Stewart’s book [147] is an accessible introduction at this level; for more advanced treatments, see the books of Hasse [76], Janusz [83] or Lang [96]. A sophisticated text on related topics is Serre’s classic book [137]. Barbeau’s book [10] discusses Pell’s equation in detail and requires very little background. A proof of Theorem 2.14 can be found in Lang [96, Chapter I, Proposition 17]. The seminal finiteness results on S-unit equations mentioned at the end of Section 2.4 may be found in the papers of Evertse [60], Schlickewei [134], and van der Poorten and Schlickewei [120]. These results have found wide application; a surprising connection to ergodic theory is shown in a paper of Schmidt and Ward [135]. For attractive accounts of Fermat’s Last Theorem, see the popular accounts of Ribenboim [126] and van der Poorten [119]; a serious introduction at a high level to the mathematics behind Wiles’ extraordinary proof [162] may be found in the proceedings [35] of an instructional conference edited by Cornell, Silverman and Stevens. Exercise 2.20 comes from a short note by Cross [38]; Exercise 2.21 comes from a paper of Zuehlke [169] and uses some transcendence theory. The Catalan problem Equation (2.13) was initially reduced to a finite calculation and then solved completely by Mih˘ ailescu; see the paper of Mets¨ ankyl¨ a [106] for an account and the monograph [58, p. 159] by Everest, van der Poorten, Shparlinski and Ward for an overview of related questions. An accessible account of the Catalan problem before its final solution may be found in the book of Ribenboim [124]. The results of Lander and Parkin appeared in their paper [92]; their dramatic announcement quoted in Section 2.5.3 is [91]. The state of Euler’s problem in 1967 is surveyed in a paper of Lander, Parkin and Selfridge [93]. Equation (2.15) of Elkies is in [49].
3 Quadratic Diophantine Equations
Attempts to go beyond the Pythagorean Diophantine equation quickly lead to general questions about quadratic Diophantine problems. Apparently simple questions seem to require an excursion into the theory of finite fields. For example, we prove that any finite field has a primitive root in order to develop the classical theory of the Legendre symbol and the Quadratic Reciprocity Law. Some general theory of quadratic rings and quadratic forms is established, up to the finiteness of the class number for quadratic forms.
3.1 Quadratic Congruences Suppose we now seek to generalize our earlier results and understand the Diophantine equation x2 + 2y 2 = p (3.1) when p is a prime √ and x and y are integers. We can do this by using properties of the ring Z[ −2], but we also need a better understanding of the arithmetic of the integers modulo p when p is a prime. √ Exercise 3.1. Let R = Z[ −2]. (a) Show that the function N : R → N defined by √ N (x + y −2) = x2 + 2y 2 satisfies N (αβ) = N (α)N (β) for all α, β ∈ R. (b) Determine all the units in R. (c) Show that R is Euclidean with respect to N . Following our earlier method, we now expect to use unique factorization in R together with some knowledge of congruences to understand Equation (3.1). The relevant congruence to study for this equation is T 2 + 2 ≡ 0 (mod p).
(3.2)
60
3 Quadratic Diophantine Equations
Exercise 3.2. Compute the list of primes p < 1000 for which the congruence (3.2) has a solution with T ∈ Z. It is becoming clear that we need some tool that will guarantee the existence of a solution for certain congruences and rule out a solution for others. For example, your computations in Exercise 3.2 should suggest that for primes p ≡ 1 or 3 modulo 8 there is a solution, while there is no solution for primes p ≡ 5 or 7 modulo 8. (The prime p = 2 does give a solution.) Our earlier approach suggests that the area we need to look at is the arithmetic of Z/pZ. Previously we used al-Haytham’s Theorem in a crucial way, and here we have no obvious analog. It turns out that the property we need is directly related to a natural concept in group theory. Definition 3.1. An element a of Z/pZ is a primitive root modulo p if the powers of a generate all the nonzero residues modulo p. Example 3.2. It is easy to prove that the powers of 2 yield all the nonzero residues modulo 5: 20 ≡ 1, 21 ≡ 2, 22 ≡ 4, 23 ≡ 3 modulo 5. Thus 2 is a primitive root modulo 5. Similarly, 3 is a primitive root modulo 7, but 2 is not since no power of 2 is congruent to 3 modulo 7. The set of residues modulo p forms a field: The existence of a primitive root a modulo p is the same as the statement that the multiplicative group (Z/pZ)∗ of the field Z/pZ is cyclic, generated by a. We will use freely other equivalent ways of saying this. If G denotes a finite Abelian group with n elements, written multiplicatively, then a generates G if and only if any of the following equivalent conditions hold: 1. am = 1, 1 < m n =⇒ m = n; 2. the order of a is n; 3. am = 1, 1 < m =⇒ nm. Theorem 3.3. The multiplicative group of any finite field is cyclic. This is an important result, and we will spend some time proving it. When we have done this, we can return to our equations. The proof of Theorem 3.3 involves an important example of an arithmetic function. Definition 3.4. An arithmetic function is any function f : N → C. An arithmetic function with f(1) = 0 and f(mn) = f(m)f(n) whenever m and n are coprime is called multiplicative. (Note that this implies f(1) = 1.) If f has this property not only for coprime m, n, but for all m, n ∈ N, then f is called completely multiplicative.
3.1 Quadratic Congruences
61
Multiplicative arithmetic functions will be discussed further in Section 8.2. One of the most important arithmetic functions is φ(n) = |{1 a n | gcd(a, n) = 1}| , called the Euler phi-function. Exercise 3.3. Let p be a prime. Show that φ(pe ) = pe−1 (p − 1) for any e 1. Lemma 3.5. The Euler phi-function is multiplicative. We will postpone the proof slightly to note an immediate corollary of Lemma 3.5 and Exercise 3.3. Corollary 3.6. If n is factorized into powers of distinct primes, n = p pep , then p−1 (p − 1)pep −1 = n . φ(n) = p p|n
p|n
Exercise 3.4. Give an example to show that φ is not completely multiplicative. Exercise 3.5. (a) Find all values of n ∈ N with φ(n) = 12 n. (b) Find all values of n ∈ N with φ(n) = φ(2n). (c) Find all six values of n ∈ N with φ(n) = 12. 1 (d) Find the smallest n ∈ N for which φ(n) n < 4. φ(n ) (e) Find a sequence of integers (nj ) for which njj → 0 as j → ∞. The proof of Lemma 3.5 depends on the following result. Theorem 3.7. [Chinese Remainder Theorem] Suppose m, n ∈ N are coprime. Then the simultaneous congruences x ≡ a (mod m), x ≡ b (mod n), have a solution x ∈ N for any a, b ∈ Z, and the solution is unique modulo mn. The Chinese Remainder Theorem was discovered by Chinese mathematicians in the fourth century A.D. The first appearance seems to have been in a work of Sun-Zi, and a general treatment was given by Qin1 Jiushao. Special 1
Also transliterated as Ch’in Chiu-Shao. Jiushao seems to have been both a rogue and a mathematical genius. His work Shushu Jiuzhang (Mathematical Treatise in Nine Sections) appeared in 1247 and contained many important and novel results and methods. The so-called Chinese Remainder Theorem is among these, attributed to experts in astronomy and calenders. It has been suggested that the theorem does not bear his name because in the form ‘Chin’ it was too easily confused with ‘Chinese’.
62
3 Quadratic Diophantine Equations
results of the same sort were used by Fibonacci in Italy and al-Haytham in Iraq. We will see it again in Chapter 12 (see p. 256) in greater generality. Proof of the Chinese Remainder Theorem. The coprimality condition guarantees that there exist m , n such that mm = 1 (mod n) and nn = 1
(mod m)
(3.3)
by Corollary 1.25. Then x = bmm + ann satisfies both the required congruences. If, on the other hand, x and y satisfy both congruences, then (x − y) is divisible by m and by n. Since m and n are coprime, (x − y) must be divisible by mn. Example 3.8. Solve the simultaneous congruences x ≡ 2 modulo 17 and x ≡ 8 modulo 11. We find m = 2 and n = 14 in the proof of the Chinese Remainder Theorem. Then x = 8 · (17 · 2) + 2 · (11 · 14) = 580 satisfies the two congruences. (The smallest solution is the remainder of 580 divided by 11 · 17, namely 19.) Proof of Lemma 3.5. Let m and n be coprime. Define a map Φ : Z/mnZ → Z/mZ × Z/nZ by x → (x (mod m), x (mod n)) , where we think of the elements of Z/mnZ as {0, 1, . . . , mn−1}. By the Chinese Remainder Theorem, Φ is a bijection. (In fact, Φ is an isomorphism of rings.) Now define ∗ (Z/nZ) = {1 a n : gcd(a, n) = 1} and likewise for n and mn. Since x is coprime to mn if and only if it is coprime both to m and n, Φ restricts to these subsets: ∗
∗
∗
Φ : (Z/mnZ) → (Z/mZ) × (Z/nZ) . Here Φ is still a bijection. (In fact, the set (Z/kZ)∗ is the set of units U (Z/kZ) of Z/kZ, and Φ is an isomorphism of (multiplicative) groups.) By definition, the cardinality of (Z/mZ)∗ is just φ(m) and likewise for n and mn, which completes the proof of Lemma 3.5. The next exercise is a generalization of Fermat’s Little Theorem (Theorem 1.12), called the Euler–Fermat Theorem. Exercise 3.6. Given n > 1 in N, show that for any a ∈ Z with gcd(a, n) = 1 aφ(n) ≡ 1 (mod n).
(3.4)
3.1 Quadratic Congruences
63
Exercise 3.6 is a pretty standard one found in most texts that deal with the φ-function. It is a good test case for our earlier remarks about how different approaches can yield different benefits. It is possible to prove Equation (3.4) using congruences modulo pr for each prime power pr dividing n, together with the Binomial Theorem. Another, slicker, proof simply uses Lagrange’s Theorem on the group U (Z/nZ) = (Z/nZ)∗ . Theorem 3.9. For any n ∈ N,
φ(d) = n.
(3.5)
d|n
Proof. First check the equality when n = pr is a prime power. The left-hand side is r 1+ (p − 1)pi−1 = 1 + (pr − 1) = n i=1
by summing the geometric progression or noticing that it is a telescoping sum. Next, observe that both sides of Equation (3.5) are multiplicative arithmetic functions. For the left-hand side, this follows from φ(d) = φ(d1 d2 ) = φ(d1 ) φ(d2 ) d|mn
d1 |m d2 |n
d1 |m
d2 |n
for any pair of coprime integers (m, n). Note that d divides mn if and only if there exist divisors d1 of m and d2 of n such that d = d1 d2 , so it is enough to check the prime power case. We can now prove Theorem 3.3. In the proof, we will be working with a general finite field. Such a field can always be explicitly presented using polynomials; however, nowhere will we need an explicit presentation. This suggests that more abstract methods might also be applicable to prove the theorem. Indeed, a proof can be given that only uses the theory of finite Abelian groups. Proof of Theorem 3.3. Let F be a finite field with q elements. We are going to prove that if g is any element of F∗ , then g j has the same order as g if and only if gcd(j, q − 1) = 1. This will allow us to find how many elements there are of each order, showing in particular that there are φ(q − 1) distinct generators in total. Example 3.10. The distinct powers of 3 in F∗7 are 30 ≡ 1, 31 ≡ 3, 32 ≡ 2, 33 ≡ 6, 34 ≡ 4, 35 ≡ 5. The only values of j, 1 j 6 with gcd(j, 6) = 1 are 1 and 5. Since 35 ≡ 5 modulo 7, 5 is another generator of F∗7 . Similarly, F∗11 = 2 (the multiplicative group generated by 2). The values of j between 1 and 10 for which gcd(j, 10) = 1 are j = 1, 3, 7, 9 so there are four possibilities for generators of F∗11 , namely 21 ≡ 2, 23 ≡ 8, 27 ≡ 7, 29 ≡ 6.
64
3 Quadratic Diophantine Equations
Exercise 3.7. Prove that in any field, a polynomial of degree d has no more than d zeros. (Hint: Use Exercise 2.5 on p. 47). Returning to the proof of Theorem 3.3, suppose d(q − 1) and a is an element of F∗ of order d (if one exists). Then ad = 1 in F and am = 1 with 0 m < d implies m = 0. The elements 1, a, a2 , · · · , ad−1 are all distinct, otherwise ai = aj would imply that ak = 1 with some 0 < k < d. We claim that if an element a of order d exists, then the other elements of order d in F∗ are precisely those powers aj with 1 j < d and gcd(j, d) = 1. Thus if there is an element of order d, then there will be precisely φ(d) of them. If a does have order d, then the only other elements of order d must lie among the powers aj above since any element of order d satisfies the equation xd − 1 = 0 in F, this equation has at most d roots by Exercise 3.7, and each of the powers aj , 0 j < d satisfies the equation. Thus all the elements of order d must lie among these powers. But which of the powers have order d? We now prove our claim that aj has order d, 1 j < d, if and only if gcd(j, d) = 1. If 1 < gcd(j, d) = d < d then 1 < d/d < d and
(aj )d/d = (ad )j/d = 1j/d = 1, so aj does not have order d (since d/d < d). Conversely, suppose that gcd(j, d) = 1 and aj has order d with 1 < d d.
Then ajd = 1, so djd since a has order d. However, gcd(d, j) = 1, which forces dd . On the other hand, d d, so we must have d = d . This completes the proof that aj has order d if and only if gcd(j, d) = 1. Each of the (q − 1) elements of F∗ has order dividing (q − 1), so by Theorem 3.9, φ(d) = q − 1. d|(q−1)
Thus, for every d dividing (q − 1), we must have φ(d) elements (not none) of order d. In particular, we have φ(q − 1) 1 elements of order (q − 1). Notice that we have proved a little more than Theorem 3.3. The proof shows how many elements of Fq there are of each possible order, finding in particular that there must be at least one element of order (q − 1), which is therefore a primitive root. Exercise 3.8. Verify that 2 is a primitive root for the prime p = 19. Find all the elements of order 6 under multiplication modulo 19, expressed as integers between 1 and 18.
3.2 Euler’s Criterion
65
Despite the seemingly complete knowledge provided by the proof of Theorem 3.3, several closely related questions turn out to be extremely difficult. The following is a famous conjecture of Artin which remains an open problem. Conjecture 3.11. [Artin] Any integer that is not a square or −1 is a primitive root modulo p for infinitely many primes p. An apparently less ambitious question is to ask, given an explicitly presented finite field, whether there is an algorithm for determining a primitive root. For example, if p is a given prime, can we determine a primitive root for p? The most obvious thing to try is checking the integers 2, 3, 5, 6 . . . (not 4 of course!) in the hope that a primitive root will soon be found. Thus one seeks an upper bound on the smallest primitive root, and this too is difficult. The smallest primitive root modulo p can be shown – conditionally – to be bounded by a constant multiple of (log p)6 , a result of Shoup from 1992. However this result relies upon a hard unproven hypothesis stated in Section 12.7.1. This might not sound very satisfactory, but it turns out to have great practical value.
3.2 Euler’s Criterion Many problems concerning quadratic congruences can be reduced to solving the simplest such congruence, namely x2 ≡ a modulo p for a prime p and given a. Definition 3.12. Let p be an odd prime and a an integer. The Legendre symbol is defined by ⎧ ⎨ 0 if pa, a = 1 if p a and x2 ≡ a (mod p) has a solution, ⎩ p −1 otherwise. If a = 0 and ( ap ) = −1 then a is a quadratic nonresidue modulo p; otherwise a is a quadratic residue modulo p. Some elementary properties of the Legendre symbol will be used without 2 comment. In particular, if a ≡ b modulo p, then ( ap ) = ( pb ) and ( ap ) = 1 for any a = 0. Theorem 3.13. [Euler’s Criterion] Let p be an odd prime. Then a ≡ a(p−1)/2 (mod p). p
(3.6)
66
3 Quadratic Diophantine Equations
Proof. The statement is obvious if a ≡ 0 modulo p, so assume that a is coprime to p. Notice that the only square roots of 1 modulo p are congruent to ±1 since x2 − 1 = (x − 1)(x + 1) in any field. Now (a(p−1)/2 )2 = ap−1 ≡ 1 (mod p), so a(p−1)/2 ≡ ±1 (mod p). Let g denote a generator of the cyclic group (Z/pZ)∗ . Then a ≡ g j modulo p for some j, and a is a quadratic residue if and only if j is even. Suppose a is a quadratic residue, so j = 2j for some integer j . It follows that a(p−1)/2 ≡ (g j )(p−1)/2 = g j
(p−1)
= (g p−1 )j ≡ 1
(mod p).
Thus ( ap ) = 1 implies that a(p−1)/2 ≡ 1 modulo p. Conversely, if a(p−1)/2 ≡ 1 modulo p, then g j(p−1)/2 ≡ 1 modulo p. However, g has order (p − 1) modulo p, so (p − 1)j(p − 1)/2, which implies 2(p − 1)j(p − 1). Canceling (p − 1) from both sides shows that j is even. Thus a(p−1)/2 ≡ 1 modulo p implies that ( ap ) = 1. Corollary 3.14. The Legendre symbol satisfies ab a b = . p p p That is, the Legendre symbol viewed as an arithmetic function · : Z → {0, ±1} p is completely multiplicative. The proof follows immediately from Theorem 3.13 because the right-hand side of Equation (3.6) is completely multiplicative. Exercise 3.9. Suppose that p, q > 0 are odd primes with q = 4p + 1. Prove that 2 is a primitive root modulo q. It follows that Artin’s conjecture (on p. 65) for a = 2 would be proved if we knew there are infinitely many primes q of the form 4p + 1 where p is a prime. Exercise 3.10. Prove Corollary 3.14 using concepts from group theory. (Hint: The set of squares in the group G = (Z/pZ)∗ forms a subgroup. The index of this subgroup in G is of order 2 if p is odd; see Exercise 3.12 below.)
3.3 The Quadratic Reciprocity Law
67
3.3 The Quadratic Reciprocity Law The main result on quadratic residues is a reciprocity law. Gauss did many calculations with quadratic residues and in particular studied whether there might be a relation between p being a quadratic residue modulo q and q being a quadratic residue modulo p when p and q are primes. Based on his extensive calculations, he conjectured and then proved (in several ways) the following: When one of p or q is congruent to 1 modulo 4, either both of the congruences x2 ≡ q
(mod p), y 2 ≡ p
(mod q),
are solvable or both are not. If both p and q are congruent to 3 modulo 4, then one is solvable if and only if the other is not. This surprising result is of great importance. Theorem 3.15. Let p and q denote odd primes. If p ≡ q ≡ 3 modulo 4, then q p =− . p q If at least one of p or q is 1 modulo 4, then the symbols are equal. Theorem 3.15 can be stated as a neater formula, and this is what we will prove. If p and q are odd primes, then q p (p−1)/2·(q−1)/2 = (−1) . (3.7) p q The even prime 2 has to be treated separately: The theorem below will be proved on p. 68. Theorem 3.16. If p is an odd prime, then 2 = 1 if and only if p ≡ ±1 p
(mod 8).
Exercise 3.11. (a) Show that Theorem 3.16 can be written in the form 2 2 = (−1)(p −1)/8 p for an odd prime p. (p−1)/2 (b) Prove that ( −1 . p ) = (−1) Exercise 3.12. A Diophantine equation with solutions in Z must have solutions modulo p (that is, in Z/pZ) for all primes p. (a) Show that the converse does not hold by proving that (x2 − 2)(x2 − 3)(x2 − 6) = 0 has a solution modulo p for every prime p but no integral solution. (b) Show that x8 − 16 = 0 has a solution modulo p for every prime p but no integral solution.
68
3 Quadratic Diophantine Equations
Exercise 3.13. (a) Show that Equation (3.7) is equivalent to Theorem 3.15. (b) Show that if p is an odd prime, then −2 = 1 if and only if p ≡ 1 or 3 (mod 8). p √ (c) Use the arithmetic of Z[ −2] to show that the prime p can be written p = x2 + 2y 2 , with x, y ∈ Z, if and only if p ≡ 1 or 3 modulo 8. Exercise 3.14. (a) Show that if p > 3 is a prime, then −3 = 1 if and only if p ≡ 1 (mod 3). p (b) Show that the map x → x3 + 2 is a bijection on Z/pZ for any odd prime p congruent to 2 modulo 3. Deduce that the equation(x2 + 3)(x3 + 2) = 0 has a solution modulo q for any prime q but has no integral solutions. Exercise 3.15. *Show that a monic polynomial f ∈ Z[x] of degree 4 or less that has a solution modulo q for every prime q has an integral solution. The proof of Theorem 3.16 acts as a dummy run for the proof of Theorem 3.15. The proofs given here are due to Serre. Proof of Theorem 3.16. The prime p is odd, so p2 −1 ≡ 0 modulo 8. Let F denote the field with p2 elements. Then F∗ is a cyclic group of order p2 − 1 by Theorem 3.3. Since p2 − 1 is divisible by 8, this implies that F∗ contains an element of order 8. Let ζ denote such an element. Let G = ζ − ζ 3 − ζ 5 + ζ 7.
(3.8)
Now (ζ 4 )2 = ζ 8 = 1, so ζ 4 = −1 (ζ has order 8, so we cannot have ζ 4 = 1) and therefore ζ 5 = −ζ and ζ 7 = −ζ 3 . Therefore G = 2(ζ − ζ 3 ), so G2 = 4(ζ − ζ 3 )2 = 4(ζ 2 + ζ 6 − 2ζ 4 ). But ζ 4 + 1 = 0 implies that ζ 6 + ζ 2 = 0. Therefore G2 = 8. Recall that we are working in the field F so that 8 denotes not only the integer 8 but also the sum 1F + · · · + 1F (seven additions), where 1F is the multiplicative identity in F∗ . The proof of the theorem depends on finding two distinct expressions for Gp .
3.3 The Quadratic Reciprocity Law
69
First expression for Gp : Gp = GGp−1 = G(G2 )(p−1)/2 2 = G8(p−1)/2 because G = 8 8 by Euler’s criterion =G p 2 =G by Corollary 3.14. p
Second expression for Gp : 2 Define a function f : Z → {0, ±1} to be 0 when j is even and (−1)(j −1)/8 when j is odd. Notice that f (j) = 1 if and only if j ≡ ±1
(mod 8).
The second expression for Gp is Gp = f (p)G.
(3.9)
Equate the two expressions for Gp to obtain 2 = f (p)G. G p Now G is not zero in F (because G2 = 8), so cancelling gives 2 = f (p) = 1 if and only if p ≡ ±1 (mod 8). p The field F has characteristic p, so (a + b)p = ap + bp in F because all binomial coefficients apart from the end ones are divisible by p. (A similar argument was used in the proof of Fermat’s Little Theorem on p. 24.) Similarly, by induction, (a1 + · · · + an )p = ap1 + · · · + apn . Using Equation (3.8) and the definition of f , G = f (1)ζ + f (3)ζ 3 + f (5)ζ 5 + f (7)ζ 7 = f (0) + f (1)ζ + f (2)ζ 2 + · · · + f (7)ζ 7 =
7
f (j)ζ j .
j=0
Thus Gp =
7 j=0
f (j)ζ j
p =
7
f (j)ζ jp .
(3.10)
j=0
Note that f (j) does not need to be raised to the power p because f (j)p = f (j).
70
3 Quadratic Diophantine Equations
Lemma 3.17. For all j ∈ Z, f (p)f (jp) = f (j). Assuming this lemma for the moment, Equation (3.10) gives Gp =
7
7
f (j)ζ jp =
j=0
f (p)f (jp)ζ jp = f (p)
7
j=0
f (jp)ζ jp .
j=0
Now, for fixed p, jp modulo 8 runs through 0, . . . , 7 as j does, so this shows that Gp = f (p)G, proving Equation (3.9). All we need to do now is prove Lemma 3.17, which states that f (p)f (pj) = f (j). Clearly, this is true if j is even, so suppose that j is odd. The statement is true for any odd pair j and p. This can be checked by examining all the possibilities for j and p modulo 16. Alternatively, notice that (−1)((jp)
2
−1)/8
= (−1)((jp) 2
2
−p2 +p2 −1)/8
= ((−1)p )(j = (−1)(j
2
2
−1)/8
−1)/8
(−1)(p
(−1)(p
2
2
−1)/8
−1)/8
.
This shows that f (jp) = f (j)f (p), and Lemma 3.17 follows by multiplying both sides by f (p) (whose square is 1). Finally, we come to the proof of the Quadratic Reciprocity Law (Theorem 3.15). Theorem 3.3 will again play a pivotal role. Proof of Theorem 3.15. Consider the field F with pq−1 elements. Then F∗ is a cyclic group with order pq−1 − 1 by Theorem 3.3. By Fermat’s Little Theorem, pq−1 ≡ 1 modulo q. Thus there is an element ζ in F∗ whose order is q. Define q−1 j ζj. (3.11) G= q j=1 The sum G is called a Gauss sum because Gauss seems to have been the first person to systematically study sums such as these. The proof works as before by finding two different expressions for Gp . We claim first that G2 = (−1)(q−1)/2 q. (3.12) Using this, we can derive our first expression for Gp . First expression for Gp : Gp = GGp−1 = G(G2 )(p−1)/2 = G((−1)(q−1)/2 q)(p−1)/2 q . = G(−1)(q−1)/2·(p−1)/2 q (p−1)/2 = G(−1)(q−1)/2·(p−1)/2 p
3.3 The Quadratic Reciprocity Law
Second expression for Gp : We claim that Gp =
p G. q
71
(3.13)
Equating the two expressions gives (q−1)/2·(p−1)/2
G(−1)
p q = G. p q
We can cancel G because it is not zero in F (since its square is (−1)(q−1)/2 q, which is not zero in F); the Quadratic Reciprocity Law follows at once. The next step is to show Equation (3.13). By the Binomial Theorem, q−1 p q−1 j j p ζj ζ jp G = = q q j=1 j=1 because ( qj )p = ( qj ). By the multiplicativity of the Legendre symbol (Corollary 3.14), the right-hand side is q−1 jp p ζ jp q j=1 q since pq is ±1. Now jp modulo q runs through 1, . . . , q − 1 as j does, so the second expression for Gp can be written as in Equation (3.13). The only tricky part of this proof is to evaluate G2 . Expanding the product for G2 gives q−1 q−1 j −k ζj ζ −k , G2 = q q j=1 k=1
noting that as k runs through 1, . . . , q − 1, so does −k modulo q. k = −1 By the multiplicativity of the Legendre symbol, −k q q q . −1 Pulling the factor q out to the front and replacing k by jk in the second sum gives q−1 q−1 jk j −1 ζ j(1−k) . G2 = q j=1 q q k=1 jk = kq , so By the multiplicativity of the Legendre symbol qj q G2 =
q−1 q−1 k −1 ζ j(1−k) . q j=1 q k=1
72
3 Quadratic Diophantine Equations
Next we add zero to both sides of this equation in a special form. On the right-hand side, add q−1 k ζ 0(1−k) . (3.14) 0= q k=1
This expression is zero because half of the nonzero residues modulo q are squares, so half of the values of the symbol are 1 and the other half are −1. Thus q−1 q−1 −1 k G2 = ζ j(1−k) . q j=0 q k=1
This double sum can be rearranged to give q−1 q−1 k −1 G = ζ j(1−k) . q q j=0 2
(3.15)
k=1
By Euler’s criterion (Theorem 3.13), the term with k = 1 contributes −1 q = (−1)(q−1)/2 q q to G2 . We claim that all the other terms (those with k = 1) in Equation (3.15) contribute nothing. Assume that k = 1, and write η = ζ 1−k . Then η is a nontrivial qth root of 1. We claim that S = 1 + η + · · · + η q−1 = 0. To see this, notice that ηS = η + η 2 + · · · + η q−1 + η q = 1 + η + · · · + η q−1 = S, which shows that S = 0 since η = 1.
Apart from being a very beautiful result, the Quadratic Reciprocity Law is important in that it allows the Legendre symbol to be rapidly computed. This is useful in many areas, including primality testing (see, for example, Section 12.6). 91
Example 3.18. Compute the Legendre symbol 167 using the Quadratic Reciprocity Law. First notice that 91 7 13 167 167 6 11 = =− =− . 167 167 167 7 13 7 13 The problem has become more manageable and is readily finished by noting that
3.4 Quadratic Rings
11 13
=
13 11
=
2 11
73
= −1
6 2 3 3 7 1 = = =− =− = −1. 7 7 7 7 3 3 91
It follows that 167 = −1.
and
19 1003 Exercise 3.16. Evaluate the Legendre symbols ( 11 37 ), ( 31 ), ( 111 ).
3.4 Quadratic Rings It is tempting to conclude that we are now in a position to characterize those primes p that can be written in the form p = x2 + dy 2 , with x, y ∈ Z for a given d ∈ Z. Unfortunately, this problem is a little more complicated than it√first appears. The methods of this chapter are applicable only if the ring√Z[ −d] is Euclidean, and this is not always the case. The structure of Z[ −d] is quite subtle, and some basic questions about these rings are still open. Exercise 3.17. Show √ that the Fundamental Theorem of Arithmetic does not hold in the ring Z[ −3] by considering the two factorizations √ √ 2 · 2 = 4 = (1 + −3)(1 − −3) of 4. (Hint: Show that 2 cannot be a prime in this ring.) Example 3.19. Consider the equation x2 + 5y 2 = p. In order to understand this, we expect to use the Quadratic Reciprocity Law to solve T 2 + 5 ≡ 0 (mod p) for T . Exercise 3.18. Show that ( −5 p ) = 1 if and only if p ≡ 1, 3, 7, or 9 modulo 20. In particular, the congruence T 2 + 5 ≡ 0 modulo 7 has a solution: it is easily found that T = 3 is a solution. However, the equation x2 + 5y 2 = 7 has no solution in integers.
74
3 Quadratic Diophantine Equations
Exercise 3.19. Show √ that the Fundamental Theorem of Arithmetic does not hold in the ring Z[ −5]. √ Exercise 3.20. Show that there are infinitely many rings Z[ −d], where d is a positive square-free integer, in which the Fundamental Theorem of Arithmetic does not hold. The Quadratic Reciprocity Law is a useful tool for understanding when quadratic congruences have no solutions. For example, Exercise 3.18 shows that we will never obtain a solution to the equation x2 + 5y 2 = p if p is any prime that is congruent to 11 modulo 20. More than that, it can predict the existence of solutions when the equation cannot be checked easily by hand. √ Exercise 3.21. (a) Show that Z[ 2] is Euclidean with respect to the norm √ N (x + y 2) = x2 − 2y 2 . (b) Show that if p is an odd prime, then the equation x2 − 2y 2 = p has a solution whenever p ≡ ±1 modulo 8 but has no solutions when p ≡ ±3 modulo 8. This is (by now) a routine use of √ the Quadratic Reciprocity Law together with the Euclidean property of Z[ 2]. √ Exercise 3.22. When d > 1 is square-free, the ring Z[ d] has infinitely many units. Deduce that if x2 − dy 2 = p has a solution in integers, then it has infinitely many solutions. (The first part of the exercise will be covered in the next section, but try to find a proof yourself.) The statement in the first part of the exercise is not easy. The equation x2 − dy 2 = 1 is often called Pell’s Equation after the seventeenth-century mathematician John Pell. This is now thought to be a misattribution. Brahmagupta seems to have known how to solve the equation long before Pell. In the twelfth century, Bhaskaracharya discovered the simplest of the infinitely many nontrivial solutions when d = 61, namely x = 1766319049,
y = 226153980.
√ 3.5 Units in Z[ d], d > 0
√ 3.5 Units in Z[ d], d > 0
75
√ For d < 0, the ring R = Z[ d] has only finitely many units, so we assume in this section that d > 0 is a fixed square-free integer. Write {t} for the fractional part of a real number t. Lemma 3.20. There are infinitely many coprime pairs of integers p and q > 0 with √ 1 |q d − p| < . q Proof. Let Q > 1 denote an integer. Divide the interval [0, 1) into Q subintervals [0, 1/Q), [1/Q, 2/Q), . . . and consider the (Q + 1) numbers √ √ √ 0, { d}, {2 d}, . . . , {Q d}. √ There are (Q + 1) of them since d is irrational, so at least two must lie in a single one of the Q intervals of the form [a/Q, (a + 1)/Q) by the pigeonhole principle Thus there must be integers q1 , q2 with 0 q1 < q2 Q such that √ √ {q2 d} − {q1 d} < 1/Q. Unwinding the definition of the fractional part, this means that there are integers p1 and p2 with √ √ √ q2 d − p2 − q1 d + p1 = (q2 − q1 ) d − (p2 − p1 ) < 1/Q. The proof is now finished by choosing Q q = q2 − q1 > 0 and p = p2 − p1 . This was originally proved by Dirichlet and is the starting point for a deep subject known as Diophantine approximation. This subject has to do with how well an irrational number can be approximated by rational numbers. Exercise 3.23. Show that there is a constant C > 0 such that √ C < |q d − p| q for all integers p and q > 0. Exercise 3.24. More generally, show that if α is algebraic of degree k > 1 (that is, α satisfies an irreducible polynomial of degree k with integer coefficients), then there is a constant C(α) > 0 such that C(α) < |qα − p| q k−1 for all integers p and q > 0.
76
3 Quadratic Diophantine Equations
Theorem 3.21. If d > 1 is a square-free integer, then x2 − dy 2 = 1 has infinitely many solutions√in integers (x, y). Moreover, each solution corresponds to a unit in R = Z[ d] with norm 1. Any unit with norm 1 has the form ±un for n ∈ Z, where u is a fixed unit with norm 1. Proof. Using Lemma 3.20, choose p, q > 0 with √ 1 |q d − p| < . q Then p− so
(3.16)
√ 1 1
√ √ 1 |q d + p| < 2q d + . q
(3.17)
Multiplying the inequalities (3.16) and (3.17) shows that √ |p2 − dq 2 | < 1 + 2 d. We would like to show that the left-hand side is 1 for infinitely many pairs (p, q). We cannot deduce this at once, but notice that the right-hand side is a uniform bound (independent of p and q), so there must be an integer e with √ 1e<1+2 d such that for infinitely many pairs p and q, p2 − dq 2 = e. There also must be infinitely many distinct pairs (p, q) and (p , q ) such that p ≡ p modulo e, q ≡ q modulo e, and pp − dqq ≡ p2 − dq 2 ≡ 0
(mod e).
Given such a distinct pair, write pp − dqq = xe and pq − q p = ye for integers x and y. Then 2 2 pp − dqq pq − qp −d x2 − dy 2 = e e
1 2 2 = 2 p (p − dq 2 ) − dq 2 (p2 − dq 2 ) e 1 = (p2 − dq 2 ) = 1, e
√ 3.5 Units in Z[ d], d > 0
77
so there are infinitely many solutions. To prove the claim about the structure of the unit group, consider the map L : U (R) → R2 defined by
√ √ √ L(x + y d) = (log(x + y d), log(x − y d)).
The image is a nontrivial discrete subgroup (see Exercise 3.25 below) of R2 , so it must have rank 1 or 2 by Exercise 3.26. On the other hand, x2 − dy 2 = 1 implies that √ √ log(x − y d) + log(x + y d) = 0, so the image of L lies in a one-dimensional subspace of R2 and therefore the rank must be 1. This is enough to prove the claim: The image set must be {n(v, −v) | n ∈ Z} for some nonzero v ∈ R and the claim follows with u satisfying L(u) = (v, −v). Exercise 3.25. Explain why the image of L is a discrete subgroup of R2 in the proof of Theorem 3.21. Exercise 3.26. Prove that a discrete subgroup of Rn has rank less than or equal to n. Finding u is in general a nontrivial problem. In some books you will see the method of continued fractions used, which does give an algorithm. The method used here, which is a first step into the subject called geometry of numbers, was chosen for two reasons. First, using a generalization of this argument, one can go on to analyze the units of the ring of algebraic integers (see p. 84) inside a number field. This always turns out to be finitely generated with a rank that is easily computed from basic data about the number field. The method using continued fractions does not generalize. Second, the geometry of numbers, when worked out fully, really represents an application of topological ideas. If you ask what kind of shapes in space must contain lattice points, you quickly find yourself resorting to ideas such as compactness and connectedness as well as convexity. A beautiful fact about the solutions of the equation in Theorem 3.21√is that they form a group. Moreover, the multiplication law on elements x + y d can be expressed in terms of polynomial functions on the coordinates x and y as follows: √ √ √ (x1 + y1 d)(x2 + y2 d) = (x1 x2 + dy1 y2 ) + (x1 y2 + x2 y1 ) d. In Chapter 5, we will encounter a whole family of Diophantine equations in two variables whose solutions form groups, and for which the multiplication law can be expressed in terms of rational functions on the coordinates.
78
3 Quadratic Diophantine Equations
3.6 Quadratic Forms The subject of quadratic forms is a large one, and we will merely introduce it here via a classical proof of a result due to Lagrange and some comment on Gauss’ Theorem. Consider the Diophantine equation ax2 + bxy + cy 2 = n
(3.18)
in which we seek an integral solution (x, y) for given a, b, c, n ∈ Z. The discriminant ∆ of the quadratic form ax2 + bxy + cy 2 is defined to be ∆ = b2 − 4ac. Just as with the Pythagorean equation, there are several elementary reductions to be made. First, if gcd(a, b, c) = d > 1, then d must also divide n, and Equation (3.18) becomes (a/d)x2 + (b/d)xy + (c/d)y 2 = (n/d), so without loss of generality we may assume that gcd(a, b, c) = 1. Second, if gcd(x, y) = e > 1, then a(x/e)2 + b(x/e)(y/e) + c(y/e)2 = (n/e2 ), so we may assume without loss of generality that x and y are coprime. As in the Pythagorean case, call solutions (x, y) with gcd(x, y) = 1 primitive. Third, if the discriminant ∆ is a square, then the equation at2 + bt + c = 0 has rational solutions that may be written u1 /v1 and u2 /v2 in lowest terms, with v1 and v2 positive, so Equation (3.18) may be written as a(v1 x − u1 y)(v2 x − u2 y) = nv1 v2 . This is not really a quadratic equation, but a pair of linear ones. For each integral pair (r, s) with ars = nv1 v2 , solve the equations v1 x − u1 y = r, v2 x − u2 y = s. Integral solutions to this pair of equations – if there are any – solve Equation (3.18). Exercise 3.27. Let ρ =
1 − (−1)b ∆−ρ . Show that is an integer. 2 4
3.6 Quadratic Forms
79
Theorem 3.22. [Lagrange] Let ∆ be a nonsquare integer. Then there is a quadratic form ax2 + bxy + cy 2 of discriminant ∆ with a primitive solution to ax2 + bxy + cy 2 = n if and only if the congruence ∆−ρ z + ρz − ≡0 4 2
(mod n)
(3.19)
has a solution z. Proof. Assume that (α, β) is a primitive integral solution to Equation (3.18). By Theorem 1.23, there are integers γ, δ with αγ + βδ = 1. x α −δ X = . y β γ Y
Let
Notice that det
α −δ = 1, so this matrix is an invertible transformation β γ
on Z2 . Let r = aαδ + cβδ +
b+ρ 2
and s = aδ 2 + bδγ + cγ 2 . Notice that by our choice of ρ, both r and s are integers. Now express Equation (3.18) in the variables X and Y to obtain a(αX − δY )2 + b(αX − δY )(βX − γY ) + c(βX + γY )2 = X 2 (aα2 + bαβ + cβ 2 ) + XY (2aαδ − b(αγ + βδ) + 2cβγ) + Y 2 (aδ 2 + bδγ + cγ 2 ) = nX 2 + (2r + ρ)XY + sY 2 = n. The equation nX 2 + (2r + ρ)XY + sY 2 = n
(3.20)
has the solution X = 1, Y = 0, corresponding to α α −δ 1 = . β β γ 0 The discriminant of Equation (3.20) is (2r + ρ)2 − 4sn = ∆,
(3.21)
80
3 Quadratic Diophantine Equations
so r2 + ρr −
∆−ρ = sn, 4
showing that r is a solution of the congruence (3.19). Conversely, assume that r is a solution to the congruence (3.19). Then solving Equation (3.21) gives an integer s and hence the integer solution X = 1, Y = 0 to Equation (3.20). Changing back to the variables x, y using X γ δ x = Y −β α y gives an integral solution to the equation nx2 + (2r + ρ)xy + s2 = n
that has discriminant ∆.
Example 3.23. Let a = 1, b = 0, c = 5, and n = 7, so ρ = 0 and ∆ = −20. Theorem 3.22 applies to say that there is a quadratic form representing 7 with discriminant −20 if and only if z 2 + 5 ≡ 0 (mod 7) has a solution. We know that −5 is a quadratic residue modulo 7, so there is such a form. The proof constructs the form 7x2 + 6xy + 2y 2 , and of course this represents 7 when x = 1 and y = 0. Exercise 3.28. Prove that any odd prime congruent to 1 modulo 4 is a sum of two integer squares using Theorem 3.22 (cf. Theorem 2.6 where this was proved using different methods). The next exercises explore the change of variables (X, Y ) to (x, y) used in the proof of Theorem 3.22. An integer n is said to be represented by an integral quadratic form Q if there are integers x and y with Q(x, y) = n. Exercise 3.29. Let P (x, y) = ax2 + bxy + cy 2 and Q(x, y) = AX 2 + BXY + CY 2 be binary quadratic forms with integer coefficients. Say that P and Q are equivalent, written P ∼ Q, if there is an integral change of variables x α −δ X = y β γ Y
3.6 Quadratic Forms
81
α −δ with det = 1 such that β γ P (x, y) = Q(X, Y ). (a) Show that ∼ is an equivalence relation. (b) Show that equivalent quadratic forms have the same discriminant. (c) Show that equivalent quadratic forms represent the same set of integers: If P ∼ Q, then {P (x, y) | x, y ∈ Z} = {Q(x, y) | x, y ∈ Z}. Exercise 3.30. Show that a prime number p is represented by a quadratic form P if and only if there is a quadratic form equivalent to P of the form px2 + dxy + ey 2 for integers d and e. Let P (x, y) = ax2 + bxy + cy 2 be a quadratic form. Then P is positivedefinite if P (x, y) 0 for all x and y and is reduced if either c > a and − a < b a or c = a and 0 b a. Exercise 3.31. Prove that a positive-definite binary quadratic form is equivalent to a unique reduced quadratic form. Exercise 3.32. The class number of d is the number of equivalence classes of positive-definite forms with discriminant d. Prove that the class number is finite for any d. Notes to Chapter 3: Artin’s conjecture from Section 3.1 is still open – see the monograph [58, Section 3.2, 3.3] by Everest, van der Poorten, Shparlinski and Ward for descriptions of what is known and references to the literature. Shoup’s result can be found in his paper [138]. There is a discussion of the history of the Chinese Remainder Theorem in many places; see the ‘History of Mathematics’ Web site [113] for references. Mahler’s paper [102] gives an account of the method actually used by the early Chinese mathematicians, as opposed to the modern approach which follows Gauss [67]. We thank Robin Chapman for Exercise 3.12(b). Gauss was justly proud of having proved the Quadratic Reciprocity Law and many mathematicians have seen it since as foundational in the modern theory of numbers. The history and mathematics of the Quadratic Reciprocity Law and the development of reciprocity laws for higher degrees are described in Lemmermeyer’s monograph [98].
4 Recovering the Fundamental Theorem of Arithmetic
This short chapter will explain how ideal theory was developed as a means of recovering from the failure of the Fundamental Theorem of Arithmetic witnessed in Chapter 3. We begin with a few historical remarks to set that development in context and go on to give a reasonably complete account of unique factorization of ideals in the ring of algebraic integers in a quadratic field. Finally we introduce the class number and the class group.
4.1 Crisis The attempt to understand fully the problem we set out to study in the last chapter exposed a phenomenon that represented something of a historical crisis. During the nineteenth century, mathematicians had to come to terms with the breakdown of the Fundamental Theorem of Arithmetic. In March 1847, Lam´e announced a proof of Fermat’s Last Theorem (described in Section 2.5.1) to the Paris Academy, assuming (wrongly) that the Fundamental Theorem of Arithmetic held in the ring Z[e2πi/n ] for every n 1. Lam´e acknowledged that Liouville originally suggested this approach to Fermat’s Last Theorem, but Liouville himself addressed the meeting and suggested that there might be a problem with the assumption of unique factorization into primes. The question raised was this: Does unique factorization into primes hold in the ring Z[e2πi/n ]? This problem became a focal point for rapid developments. On May 24th 1847, Liouville presented a letter from Kummer to the Academy that settled the arguments. Kummer had proved in 1844 that unique factorization failed in general but that his “ideal complex numbers” in a paper of 1846 allowed a form of unique factorization to be recovered. By September 1847, Kummer had presented a paper to the Berlin Academy in which he proved that for p a regular prime 1 Fermat’s Last Theorem holds for 1
A prime p is called regular if p does not divide the numerators of any of the Bernoulli numbers B2 , B4 , . . . , Bp−3 ; the Bernoulli numbers are defined on p. 203.
84
4 Recovering the Fundamental Theorem of Arithmetic
exponent n = p, essentially by Lam´e’s method. In this paper, Kummer also showed that 37 is not regular since 37 divides the numerator of B32 . Thus Kummer proved Fermat’s Last Theorem for many indices and showed that Lam´e’s approach failed for others. These dramatic developments did not lead to a proof of Fermat’s Last Theorem but contributed to algebraic number theory√in a profound way by eventually leading to the result that rings such as Z[ −5] do have a kind of Fundamental Theorem of Arithmetic – but at the level of ideals rather than elements.
4.2 An Ideal Solution Definition 4.1. An ideal in a commutative ring R is a subgroup of the additive group of R that is closed under multiplication by elements of R. It is easy to construct ideals in a commutative ring: Take all the multiples (a) = aR = {ar | r ∈ R} √ of a single element a. In rings such as Z and Z[ −2], all ideals are of this form, and this is true for any Euclidean ring. Exercise 4.1. (a) Using the Euclidean Algorithm, prove that any ideal in Z has the form (k) = kZ for some k ∈ Z. (b) More generally, prove that in a Euclidean ring R any ideal has the form (k) = kR, the multiples of a single element k. Such singly-generated ideals are called principal, and any ring in which all ideals are principal is called a principal ideal domain. The statement in Exercise 4.1(b) is not true in all commutative rings. It is difficult to envisage what ideals look like in general; however, a more sophisticated version of the Fundamental Theorem of Arithmetic makes them easier to understand. This is described in Section 4.3 for quadratic fields. Any field K containing the rationals contains a ring OK of algebraic integers; this ring is a generalization of the usual integers in the rationals, and is defined to be the set of all zeros in the field K of monic polynomials with coefficients in Z. √ √ Exercise 4.2. Show that the ring of√algebraic integers in Q( d) is Z[ d] if d ≡ 2 or 3 modulo 4 and is Z[(1 + d)/2]√if d ≡ 1 modulo 4. (Hint: Start by showing that any algebraic integer in Q( d) that is not in Z must satisfy a quadratic equation.) √ Exercise √ 4.3. By√the previous√exercise, the ring of algebraic integers in Q( 6) (or Q(√ 14)) that the ring of algebraic integers √ is Z[ 6] (resp. Z[ 14]). Prove √ √ in Q( 6, 14) is strictly larger than Z[ 6, 14].
4.3 Fundamental Theorem of Arithmetic for Ideals
85
Exercise 4.4. Adapt the methods of Theorem 3.21 to show that the group √ ∗ of units OK inside the ring of algebraic integers OK of the field K = Q( d) when d > 0 is square-free comprises {±un | n ∈ Z}, where u > 1 is some unit of OK . Such an element u is called a fundamental unit. Exercise 4.5. Find fundamental units for the real quadratic fields √ √ √ √ Q( 2), Q( 3), Q( 5), and Q( 7). √ Any element of Q( √ d) for a square-free integer d may be written √ uniquely in the form α = x + y d with x and y rational. This presents Q( d) as a √ two-dimensional vector space over Q with basis {1, d}. √ √ Definition 4.2. The norm of α = x + y d in Q( d) is defined to be N (α) = x2 − dy 2 and the trace T (α) = 2x. √ Exercise√4.6. The map β → αβ on Q( d) is a Q-linear map on the Q vector space Q( d). Find the 2 × 2 matrix determined by this map, and show that the absolute value of its determinant is |N (α)| and its trace is T (α). Unique factorization will be recovered in Section 4.3 by working with prime ideals in the algebraic integers. These matters represent the beginnings of an important subject called algebraic number theory. The recovery of the Fundamental Theorem of Arithmetic at the level of ideals represents a major achievement that continues to influence the development of number theory and geometry. Theorem 2.14 on p. 55 gives a different way to recover the Fundamental Theorem of Arithmetic, used to dramatic effect in Theorem 2.13, but the development of ideal theory proved to be of much greater importance.
4.3 Fundamental Theorem of Arithmetic for Ideals We begin with a natural definition of multiplication on ideals. Subsequently, we introduce a notion of prime ideal, then we go on to show that every nontrivial ideal factorizes as a product of prime ideals in a way that is unique. Definition 4.3. Let I and J denote ideals in a commutative ring. The sum and product of I and J are defined by I + J = {a + b | a ∈ I, b ∈ J}, while IJ is the additive subgroup generated by the set {ab | a ∈ I, b ∈ J}. Exercise 4.7. If I and J denote ideals in a commutative ring, prove that the sum and the product of I and J are also ideals.
86
4 Recovering the Fundamental Theorem of Arithmetic
Sums and products of more than two ideals are defined in an entirely analogous fashion and again turn out to be ideals. It might have seemed more natural to define IJ to be the set {ab | a ∈ I, b ∈ J} rather than the subgroup this set generates, however the set of products by itself is not always closed under addition. Exercise 4.8. Give an example of a commutative ring R together with two ideals I and J such that the set {ab | a ∈ I, b ∈ J} is not an ideal. √ √ √ If α = x + y d ∈ K = Q( d), write α∗ = x − y d for the conjugate of α. If d < 0, then this is the usual complex conjugate; for d > 0 this terminology comes from Galois theory. For an ideal I, write I ∗ for the set of conjugates of α ∈ I. Exercise 4.9. Let I and J denote ideals in OK . (a) Show that I ∗ is an ideal in OK . (b) Show that (I + J)∗ = I ∗ + J ∗ . (c) Show that (IJ)∗ = I ∗ J ∗ . If α1 , . . . , αk are elements of OK , write (α1 , . . . , αk ) for the ideal (α1 ) + · · · + (αk ) = α1 OK + · · · + αk OK generated by α1 , . . . , αk . Also define α1 , . . . , αk = α1 Z + · · · + αk Z for the additive subgroup of OK generated by α1 , . . . , αk . It is important to distinguish these different types of generation. In what follows, we are going to work with the full ring of algebraic integers √ in the field √ Q( d) for a square-free integer√d. Following Exercise 4.2, define δ to be (1 +√ d)/2 if d ≡ 1 modulo 4 and d if d ≡ 2 or 3 modulo 4. Thus, if K = Q( d), then OK = Z[δ]. Ideals in OK , although not always principal, can always be generated as ideals by two elements. Theorem 4.4. Let I denote an ideal in OK . Then there are elements α, β in I with I = (α, β). Proof. Since OK as an additive group is a subgroup of Q2 , it follows that I can be generated as an additive group by two elements. We will first show that one of these elements can be chosen to lie in Z. Let B = {b ∈ Z | a + bδ ∈ I for some a ∈ Z};
4.3 Fundamental Theorem of Arithmetic for Ideals
87
then B is an ideal of Z. Hence B = gZ for some g ∈ Z and similarly I ∩Z = hZ for some h ∈ Z. Since g ∈ B, there must be c ∈ Z with c + gδ ∈ I. We claim that I = c + gδ, h. (4.1) Clearly c + gδ, h ⊆ I. Now assume that a + bδ ∈ I with a, b ∈ Z. Since b ∈ B, b = eg for some e ∈ Z. Therefore a − ec = a + bδ − e(c + gδ). This is an element of I ∩ Z, so it can be written as f h for some f ∈ Z. Then a + bδ = a − ec + e(c + gδ) = f h + e(c + gδ) ∈ c + gδ, h, showing Equation (4.1). To finish the proof of the theorem, use Equation (4.1) to write α = c + hδ and β = g. Then α, β ∈ I, so (α, β) ⊆ I. Conversely, if γ ∈ I, then for integers m and n, γ = mα + nβ, so I ⊆ (α, β), which concludes the proof.
As a final step toward proving the Fundamental Theorem of Arithmetic for ideals in OK , we note the following lemma. Lemma 4.5. [Hurwitz’s Lemma] If α, β are elements of OK and k ∈ Z divides N (α), N (β), and T (αβ ∗ ), then k divides αβ ∗ and α∗ β in OK . Exercise 4.10. Prove Hurwitz’s Lemma. (Hint: This only uses simple properties of the norm and trace functions.) Corollary 4.6. Let I denote any ideal of OK . Then II ∗ is a principal ideal kZ of Z. Proof. We know that I = (α, β) for some α, β, so II ∗ = (α, β)(α∗ , β ∗ ) = (αα∗ , αβ ∗ , βα∗ , ββ ∗ ). This means that II ∗ contains the integers N (α) = αα∗ and N (β), as well as T (αβ ∗ ) = αβ ∗ + α∗ β. If k denotes the greatest common divisor of these integers then k ∈ II ∗ , so (k) ⊆ II ∗ . Now k N (α), k N (β), and k T (αβ ∗ ) and hence, by Hurwitz’s Lemma, k αβ ∗ and k βα∗ , so II ∗ ⊆ (k) as claimed. The integer k appearing in Corollary 4.6 may be taken as positive without loss of generality since kZ = −kZ. Definition 4.7. If I denotes any ideal of OK , then the unique integer k > 0 with II ∗ = kZ is called the norm of I, written N (I).
88
4 Recovering the Fundamental Theorem of Arithmetic
Corollary 4.8. (1) For I = (α, β), N (I) = gcd(N (α), N (β), T (αβ ∗ )). (2) If I = (α) is a principal ideal, then N (I) = N (α). (3) The norm is multiplicative: N (IJ) = N (I)N (J) for all ideals I and J. (4) N (I) = [OK : I], the group-theoretic index of I as a subgroup of OK . Proof.(1) This appeared in the proof of Corollary 4.6. (2) This follows because (α)(α∗ ) = (αα∗ ). (3) (N (IJ)) = IJI ∗ J ∗ = (II ∗ )(JJ ∗ ) = (N (I))(N (J)) = (N (I)N (J)).
Exercise 4.11. Prove Corollary 4.8(4). (Hint: if (h, c + gδ) is a nonzero ideal of OK , then N (I) = gh.) Corollary 4.9. If I, J and K are ideals of OK with I = {0} and IJ = IK, then J = K. Proof. This is obvious if I = (α) is principal because in that case IJ = αJ so J = α−1 (IJ). Similarly, K = α−1 (IK) = α−1 (IJ) = J. In general, the identity IJ = IK implies that (II ∗ )J = (IJ)I ∗ = (IK)I ∗ = (II ∗ )K, and the result follows as before.
This important ‘cancellation’ property of ideals in OK will play a key role in the proof of the Fundamental Theorem of Arithmetic for ideals. Definition 4.10. If I and J are ideals in OK , we write I J (I divides J) if there is an ideal K in OK with J = IK. Notice that IK ⊆ I, so if I J then J ⊆ I. Lemma 4.11. Given two ideals I and J in OK , I J if and only if J ⊆ I. Proof. One direction is already proved, so assume that J ⊆ I. Then JI ∗ ⊆ II ∗ = (N (I)), so
1 JI ∗ N (I) is an ideal contained in OK . It follows that K=
IK =
1 1 1 I(JI ∗ ) = J(II ∗ ) = J(N (I)) = J, N (I) N (I) N (I)
and hence I J as claimed.
In what follows, we see a real duplication of ideas from Chapter 1, worked out in the context of ideals. The interchangeability of inclusion and divisibility for ideals will be used repeatedly.
4.4 The Ideal Class Group
89
Definition 4.12. A nonzero ideal I = R in a commutative ring R is called maximal if for any ideal J, J I implies that J = I. An ideal P is prime if P IJ implies that P I or P J. Exercise 4.12. In a commutative ring R, let M and P denote ideals. (a) Show that M is maximal if and only if the quotient ring R/M is a field. (b) Show that P is prime if and only if R/P is an integral domain (that is, in R/P the equation ab = 0 forces either a or b to be 0). (c) Deduce that every maximal ideal is prime. Theorem 4.13. [Fundamental Theorem of Arithmetic for Ideals] Any nonzero proper ideal in OK can be written as a product of prime ideals, and that factorization is unique up to order. Proof. If I is not maximal, it can be written as a product of two nontrivial ideals. Comparing norms shows these ideals must have norms smaller than I. Keep going: The sequence of norms is descending, so it must terminate, resulting in a finite factorization of I. By Exercise 4.12, every maximal ideal is prime, so all that remains is to demonstrate that the resulting factorization is unique. This uniqueness follows from Corollary 4.9, which allows cancellation of nonzero ideals common to two products.
4.4 The Ideal Class Group In this section, we are going to see how the nineteenth-century mathematicians interpreted Exercise 3.32 on p. 81 in terms of quadratic fields. The major result we will present is that ideals in OK , for a quadratic field K, can be described using a finite list of representatives I1 , . . . , Ih ; any nontrivial ideal I can be written Ii P , where 1 i h and P is a principal ideal. Thus h, known as the class number, measures the extent to which OK fails to be a principal ideal domain. This statement was proved for arbitrary algebraic number fields and proved to be influential in the way number theory developed in the twentieth century. Given two ideals I and J in OK , define a relation ∼ by I ∼ J if and only if I = λJ for some λ ∈ K∗ . Exercise 4.13. Show that ∼ is an equivalence relation. We are going to outline a proof of the following important theorem. Theorem 4.14. There are only finitely many equivalence classes of ideals in OK under ∼.
90
4 Recovering the Fundamental Theorem of Arithmetic
One class is easy to spot – namely the one consisting of all principal ideals. Of course, OK is a principal ideal domain if and only if there is only one class under the relation. One can define a multiplication on classes: If [I] denotes the class containing I, then one can show that the multiplication defined by [I][J] = [IJ]
(4.2)
is independent of the representatives chosen. Corollary 4.15. The set of classes under ∼ forms a finite Abelian group. The group in Corollary 4.15 is known as the ideal class group of K (or just the class group). Proof of Corollary 4.15. In the class group, associativity of multiplication is inherited from OK . The element [OK ] acts as the identity. Finally, given any nonzero ideal I, the relation II ∗ = (N (I)) shows that the inverse of the class [I] is [I ∗ ]. Lemma 4.16. Given a square-free integer d = 1, there is a constant Cd √that depends upon d only such that for any nonzero ideal I of OK , K = Q( d), there is a nonzero element α ∈ I with |N (α)| Cd N (I). Exercise 4.14. *Prove Lemma 4.16. The basic idea is a technique similar to that used in the proof of Theorem 3.21 showing that a lattice point must exist in a region constrained by various inequalities. Since the original proof, considerable efforts have gone into decreasing the constant Cd for practical application. The best techniques use the geometry of numbers, a theory initiated by Minkowski. Proof of Theorem 4.14. First show that every class contains an ideal whose norm is bounded by Cd . Given a class [I], apply Lemma 4.16 with I ∗ replacing I. Now (α) ⊆ I ∗ , so we can write (α) = I ∗ J for some ideal J. However, this gives a relation [I ∗ ][J] = [(α)] in the class group. This means that [J] is the inverse of [I ∗ ]. However, we remarked earlier that [I] and [I ∗ ] are mutual inverses in the class group. Hence [I] = [J]. Now |N (α)| = N ((α)) = N (I ∗ )N (J). Since the left-hand side is bounded by Cd N (I ∗ ), we can cancel N (I ∗ ) to obtain N (J) Cd . Now the theorem follows easily: For any given integer k 0, there are only finitely many ideals of norm k; this is because any ideal must be a product of prime ideals of norm p or p2 , where p runs through the prime factors of k. There are only finitely many such prime ideals and hence there are only finitely many ideals of norm k. Now apply this to the integers k Cd to deduce that there are only finitely many ideals of norm bounded by Cd . Since each class contains an ideal whose norm is thus bounded, by the first part of the proof, it follows that there are only finitely many classes.
4.4 The Ideal Class Group
91
Exercise 4.15. Investigate the relationship between quadratic forms and ideals in quadratic fields. In particular, show that Exercise 3.32 on p. 81 is equivalent to Theorem 4.14. (Hint: If I denotes an ideal with basis {α, β}, show that for x, y ∈ Z, N (xα +yβ)/N (I) is a (binary) integral quadratic form. How does a change of basis for I relate to the form? What effect does multiplying I by a principal ideal have on the form?) 4.4.1 Prime Ideals To better understand prime ideals, we close with an exercise that links up the various trains of thought in this chapter and shows that ideal theory better explains the various phenomena encountered in Chapter 3. √ Exercise 4.16. Factorize the ideal (6) √ into prime ideals in Z[ −5], expressing each prime factor in the form (a, b + c −5). Exercise 4.17. √ Let OK denote the ring of algebraic integers in the quadratic field K = Q( d) for a square-free integer d. (a) If P is a prime ideal in OK , show that P (p) for some integer prime p ∈ Z. (b) Show that there are only three possibilities for the factorization of the ideal (p) in OK : (p) = P1 P2 where P1 and P2 are prime ideals in OK (p splits); (p) = P , where P is a prime ideal in OK (p is inert); (p) = P 2 , where P is a prime ideal in OK (p is ramified ). This should be compared with the possible primes in Z[i] described in Theorem 2.8(3). The following exercise gives a complete description of splitting types in terms of the Legendre symbol. Exercise 4.18. √ Let OK denote the ring of algebraic integers in the quadratic field K = Q( d) for a square-free integer d. Let D = d if d ≡ 1 modulo 4 and let D = 4d otherwise. Show that an odd prime p is inert, ramified, or is −1, 0, or +1, respectively. What are the split as the Legendre symbol D p possibilities when p = 2? We should say something about the terminology. Splitting and inertia are fairly obvious, the latter signifying that the prime p remains prime in this bigger ring, just as primes p ≡ 3 modulo 4 remain primes in Z[i]. The term “ramify” means literally to branch, and we see here something of an overlap √ with the theory of functions. A function such as y = x really consists of two possible branches. This notion was borrowed deliberately to name the phenomenon seen in number theory, where a prime in Z becomes a power of a prime in a larger ring. We end this chapter with a definition because it is going to appear again in Chapter 11.
92
4 Recovering the Fundamental Theorem of Arithmetic
√ Definition 4.17. Let K = Q( d) denote a quadratic field, where d is a square-free integer. Define D by d if d ≡ 1 modulo 4 and D= (4.3) 4d otherwise. √ Then D is called the discriminant of the quadratic field K = Q( d). Notes to Chapter 4: Much of this chapter was based on Robin Chapman’s excellent expository notes. To see the details worked out economically in the general case, consult Lang’s book [96]. Lemma 4.16 is proved as Theorem 4 on p.119 of that book; Chapter V is an excellent introduction to Minkowski’s geometry of numbers.
5 Elliptic Curves
One of the many powerful ideas that have been brought to bear on problems in number theory is a connection between Diophantine problems and geometry. Exercise 2.2 on p. 45 gave a hint of this phenomenon; the geometric structure in that case was a unit circle, an object with algebraic structure in that the points of the unit circle form a group. In this chapter, we introduce a family of curves with a group structure. The main aim is to develop a working understanding of the group operation and to illustrate this with many examples. In subsequent chapters we will make these ideas more rigorous.
5.1 Rational Points Having studied the Pythagorean equation, which has infinitely many integral solutions, perhaps the existence of so few integral solutions to the equation1 y 2 = x3 − 2 seems a little disappointing. However, the solution (3, 5) has an amazing property. We can use this one integral solution to generate other exotic rational solutions to the equation. It may seem
obvious, but we can use this so not383 lution to generate the solution 129 , 100 1000 . Moreover, in a precise sense, this rational solution is the next simplest solution to the equation. 1
The equation y 2 = x3 + C is sometimes called Bachet’s equation after Claude Bachet (1581–1638). Bachet is most famous for translating the Arithmetica of Diophantus from Greek into Latin. This is the book in which Fermat wrote his famous marginal note asserting what is now called Fermat’s Last Theorem. In addition, Bachet discovered the duplication formula for this curve, showing that if (x, y) is a solution, then ((x4 − 8Cx)/(2y)2 , (−x6 − 20Cx3 + 8C 2 )/(2y)3 ) is also a – potentially different – solution.
94
5 Elliptic Curves
To see how this is done, first construct the tangent to the curve at the point P = (3, 5). This has equation y=
27 31 x− . 10 10
If we substitute the equation for this line into the equation of the curve, then (we claim) the line will meet the curve at another point, and this point will have rational coordinates.2 To see this more explicitly, note that when we substitute, we get a cubic equation for x,
31 27 x− 10 10
2 = x3 − 2.
We claim that x = 3 is a double root of this equation. Clearly, it is a single root by substituting in and getting 25 on both sides of the equation; differentiating and substituting shows it is a double root because you get 27 on both sides. To find the third point of intersection, use the sum of roots formula. For a cubic, this says that if x1 , x2 , and x3 are the three zeros of the cubic x3 + ax2 + bx + c, then x1 + x2 + x3 = −a (see Exercise 5.11 on p. 105). Applying this, and letting x denote the third root, we see that 3+3+x=
27 10
2 .
Solving this for x gives x = 129 100 . To find y, use the equation of the tangent to 383 see that y = 1000 . It is tempting to try this again. We cannot expect anything by joining our new point back to P . However, we could join the other integral solution (3, −5) to the new point to see where the line meets the curve again. Technically, it is better to reflect the new point in the x-axis and try to join that to our first point (for reasons that will
become apparent later). Thus we define P1 = (3, 5) 383 and P2 to be 129 100 , − 1000 . Recursively define Pn to be the reflection in the xaxis of the third point of intersection of the line joining P to Pn−1 . The next point is 164323 66234835 , ,− P3 = 29241 5000211 from which we obtain P4 = 2
2340922881 113259286337279 . , 58675600 449455096000
If you are comfortable with geometrical notions, then you will accept that since P is already a double point, the third point must be rational.
5.1 Rational Points
95
It is an amazing fact that there are infinitely many rational points on this curve and (up to reflection in the x-axis) they can all be constructed in this way, starting with P . This example already exhibits some typical behavior; for example, the denominator of the x-coordinate of P3 is a square while the denominator of the y-coordinate is the cube of the same number: 66234835 164323 . , − P3 = 1712 1713 Exercise 5.1. Prove that any rational point on the curve y 2 = x3 − 2 must have the shape P = (A/B 2 , C/B 3 ) for coprime integers A, B, C. Example 5.1. To start to understand what is going on in the geometrical iteration that produces the points Pn , consider the sequence (Bn ), where Bn is the square root of the denominator of the x-coordinate of Pn . The first few values are shown in Table 5.1. Table 5.1. Growth in the values of Bn . n Bn 1 1 2 10 3 171 4 7660 5 12660211 6 22652313570 7 58809175344521 8 1735132266687114280 9 357172782187144055262201 10 115455343251682907198856192050 11 30298854203539385536028167296302051 12 689991490842950483313935163766440646064580 13 22743339816243727151383520741637996456735801712571 14 1301982234059157037070228212465238100265563723924858470330 15 45687890972429224342713610900040552323182688307706080693278173039
The lengths of the numbers Bn written out in decimal digits seem to grow quadratically in n. The number of digits in Bn is approximately log10 Bn , so this suggests a relationship between log Bn and n2 . The following beautiful result makes this precise. Theorem 5.2. There is a constant h > 0 for which 1 log Bn → h as n → ∞ n2 where (Bn ) is the sequence in Table 5.1.
96
5 Elliptic Curves
We are not going to prove this result. An easy consequence of Theorem 5.2 is the finiteness of the number of integral points in the sequence (Pn ). Later, we will prove that the maximum of log |An | and 2 log |Bn | also grows as in the statement of Theorem 5.2 (see the comments after Theorem 7.13 on p. 147.) In Section 7.4.1, Theorem 7.15, we will relate the growth rates of log |An | and 2 log |Bn | to each other. The geometrical operation taking Pn to Pn+1 described above is a special case of a more general one: There is a binary operation on the set of points (x, y) satisfying the equation y 2 = x3 − 2 that behaves like a group law. (At this point there is no indication of an identity.) Indeed, we can define such an operation on the set of points satisfying any equation of the form y 2 = x3 + ax2 + bx + c under the nondegeneracy condition of no repeated zeros used in Siegel’s Theorem (Theorem 2.13 on p. 54). Let E denote the set of points (x, y) with y 2 = x3 + ax2 + bx + c, assume that the cubic has no repeated zeros, and define a binary operation + on the curve E as follows. If P and Q are points on E, then the line through P and Q meets E in exactly one further point, say (x, y). The reflection R = (x, −y) of (x, y) in the x-axis is then defined to be P + Q (see Figure 5.1). The case P = Q requires a notion of tangency (which can be defined for curves over any field, using order of vanishing), and then 2P is obtained by reflecting the unique other point of intersection of the line tangent to the curve at P in the x-axis. The tangent is well-defined by the nondegeneracy condition. Exercise 5.2. Draw the curve y 2 = x2 (x + 1). Show that the tangent at (1, 0) is not well-defined. Theorem 5.3. The set E with binary operation + forms an Abelian group after adding one point “at infinity.” A natural question is to ask what the identity of the group is, and this will be fully resolved – and the theorem proved – in the next chapter. At this stage, we have to confess that the identity element does not appear to exist – it is the point ‘at infinity’. For now, we can think of this as a formal single point added to the plane with the property that it lies on any vertical line of the form x = constant. We will give more justification for this claim and will return to the question when we have described a fascinating class of functions that lie behind the theory of elliptic curves – see Chapter 6. The identity element is the point at infinity, which in Figure 5.1 may be thought of as being reached by moving infinitely far up (or down) the y-axis. Additive inverses are given by reflection in the x-axis, so if P = (x, y) then −P = (x, −y). In Figure 5.2, the point P = (0, 1) on the curve y 2 = x3 − 3x + 1 is shown, with a sequence of points approaching −P = (0, −1) shown being added to P ; the third point of intersection is approaching 0, the point at infinity. Take care not to confuse 0, the point at infinity, with the origin (0, 0). Exercise 5.3. Draw a picture of the (x, y) plane with a unit sphere whose South pole is tangent to the plane at (0, 0). Define a map from the plane
5.1 Rational Points
97
4
2
−2
1
2
3
−2
−4
Figure 5.1. The binary operation on y 2 = x3 +1, showing (2, 3)+(0, 1)+(−1, 0) = 0.
to the sphere by sending a point P on the plane to the unique point on the sphere that is collinear with P and the North pole. Show that the closure of the image of a curve y 2 = x3 + ax2 + bx + c in the sphere contains the North pole. This single point may be thought of as giving a single “point at infinity” on the curve. A more subtle question is how to verify the associative law for the binary operation. This is so familiar in ordinary addition that we are prone to overlook it. When it is encountered in matrix multiplication, it follows from the associative law in the underlying ring. Here a different principle is at work: Although it is still true that the law is inherited from the complex numbers, it is so via a bijection involving transcendental functions. In the twentieth century, algebraic geometers sought to understand this phenomenon in a more abstract way. The subject of Abelian varieties is a deep and powerful one
98
5 Elliptic Curves
4
2 P
−2
1
2
3
4
5
−P −2
−4
Figure 5.2. Points converging to −P = (0, −1) showing the point at infinity.
about geometric objects, defined over arbitrary fields, with an Abelian group structure. Exercise 5.4. Convince yourself that the associative law holds for an elliptic curve with the geometrical binary operation. In other words, choose a specific elliptic curve and plot it accurately. Choose three arbitrary points P , Q and R. Now demonstrate geometrically that the point you get by adding R to P + Q is the same as the one you get by adding P to Q + R.
5.2 The Congruent Number Problem In this section, we introduce a problem from antiquity that was recently reinterpreted using the theory of elliptic curves. A natural number-theoretic question arises with the familiar (3, 4, 5) triangle in Figure 5.3. This triangle
5.2 The Congruent Number Problem
99
– we may think of it as being defined by the triple of integers (3, 4, 5) – has integral sides and integral area: What other triples of integers, or rationals, have this property?
5
area=6
3
4 Figure 5.3. Six is a congruent number.
Example 5.4. There is a right-angled triangle with rational sides and area 5. The triple (1 12 , 6 32 , 6 56 ) is Pythagorean: Expressing these as fractions over 6 and checking that 92 + 402 = 412 confirms the triangle with the sides given is right-angled. The area of the triangle is easily computed to be 5. We will see later that there are arbitrarily complicated examples of this sort. Example 5.5. The triple 2017680 1437599 2094350404801 , , 1437599 168140 241717895860 gives a right-angled triangle with rational sides and area 6. Examples 5.4 and 5.5 give examples of integer right-angled triangles with integral area by clearing fractions, but it is simpler to allow the sides to be rational, giving Definition 5.6. Exercise 5.5. Find a rational right-angled triangle with area 7. Such a triangle was known to Arab mathematicians of the twelfth century and rediscovered by Euler in the eighteenth century. Definition 5.6. An integer that is the area of a right-angled triangle with rational sides is called a congruent number. If an integer n is a congruent number and it is divisible by a square then the sides of any triangle showing that n is congruent can be scaled accordingly. Therefore we will assume without comment that it is sufficient to assume n is square-free in any discussion about whether it is a congruent number or not.
100
5 Elliptic Curves
For millennia it has remained an unsolved problem to find an algorithm for checking whether a given integer is a congruent number. In recent times, Tunnell has shown how such an algorithm can be devised – see p. 243. What is remarkable about his work is the fact that although the proof uses a great deal of sophisticated twentieth-century mathematics, the way into the proof is a back-of-an-envelope piece of high-school algebra that goes as follows. If n is a congruent number, then there is a triple of rational numbers (X, Y, Z) with X 2 + Y 2 = Z 2 and 12 XY = n. These two equations give two further equations, (X ± Y )2 = X 2 ± 2XY + Y 2 = Z 2 ± 4n, which can be written
2 2 X ±Y Z = ± n. 2 2 Multiplying the two equations (given by the choice of sign) together gives 2 2 4 X −Y2 Z = − n2. 4 2
Writing v = (X 2 − Y 2 )/4 and u = Z/2, we obtain v 2 = u 4 − n2 . Now multiply by u2 to obtain (uv)2 = u6 − n2 u2 . Finally, writing x = u2 and y = uv, we obtain a rational point (x, y) on the elliptic curve y 2 = x3 − n2 x, so a congruent number n gives rise to a rational point on an elliptic curve associated with n. Example 5.7. If we start with the (3, 4, 5) triangle, then following the steps 35 2 3 just given, we obtain the rational point ( 25 4 , − 8 ) on the curve y = x − 36x (following the convention that X = 4 should be the even side). The curve y 2 = x3 − 36x has several integral points. In addition to (0, 0) and (±6, 0), there is another, namely (−3, 9). One might wonder if these also come from right-angled triangles. The answer is no, and Tunnell’s Theorem (Theorem 5.8) suggests why not. Notice that in the construction above, the x-coordinate we obtained turned out to be the square of a rational. Moreover, the denominator of x must be even. To see this, remember Theorem 2.1, which determines the Pythagorean triples. On clearing the denominators in the triple (X, Y, Z), one of X or Y must have an even numerator and Z cannot. Thus the denominator 2 in u = Z/2 cannot cancel.
5.2 The Congruent Number Problem
101
Theorem 5.8. Suppose n is a positive integer and (x, y) denotes a rational point on the elliptic curve y 2 = x3 − n2 x with x equal to the square of a rational with an even denominator. Then n is a congruent number. Proof. The proof uses the characterization of Pythagorean triples from Theorem 2.1. Initially we retrace some of the steps√used earlier, but there is an ingenious twist at the end of the proof. Let u = x > 0; by assumption u ∈ Q. Write v = y/u so v 2 = y 2 /u2 = x(x2 − n2 )/x = x2 − n2 . We therefore have a Pythagorean equation, v 2 + n2 = x2 .
(5.1)
Unfortunately, the resulting triangle does not have area n. Let t denote the denominator of v; then t is the denominator of x, by Equation (5.1). Now clear the denominators to obtain a Pythagorean triple (t2 v, t2 n, t2 x). Since t is even, we can write, for integers a > b > 0, t2 n = 2ab, t2 v = a2 − b2 , t2 x = a2 + b2 . We claim there is a right-angled triangle with sides 2a/t, 2b/t, and 2u. This is easy to see: 2 2 2a 2b + = 4(a2 + b2 )/t2 = 4t2 x/t2 = 4x = (2u)2. t t The area of this triangle is 1 2a 2b 2ab = 2 = n. 2 t t t Of course, this theorem does not solve the congruent number problem: What makes us think we know any more about the rational points on an elliptic curve than we do about congruent numbers? In fact, a great deal of research about rational points on elliptic curves took place in the twentieth century, so reducing a problem to finding rational points on elliptic curves allows many deep results to be applied. Even without invoking any of that, we already learn something quite surprising from Theorem 5.8. Exercise 5.6. Let P be a rational point on the elliptic curve y 2 = x3 − n2 x which is neither (0, 0) nor (±n, 0). Using the algebraic doubling formula we used before, show that the x-coordinate of the resulting point is the square of a rational with an even denominator. Thus, if we can keep doing this, we obtain (potentially) infinitely many different rational right-angled triangles with area n. This was certainly not obvious from the definition of a congruent number.
102
5 Elliptic Curves
The construction in Theorem 5.8 looked a little unwieldy. The next result is a neater formulation. Theorem 5.9. Suppose n is a positive integer and x ∈ Q has the property that x, x + n, x − n are all rational squares. Put √ √ √ √ √ X = x + n − x − n, Y = x + n + x − n, Z = 2 x. Then the triangle with sides X, Y , and Z is a rational right-angled triangle with area n. Exercise 5.7. Confirm the statements in Theorem 5.9. The shape of the equation defining the elliptic curve y 2 = x(x + n)(x − n) might lead you to think the conditions of Theorem 5.9 must always be satisfied for a rational point (x, y). The point (−3, 9) is a counterexample however. Subsequently (see Section 7.3) we will come to understand when the conditions hold in terms of the group-theoretic structure of the curve.
35 Exercise 5.8. Take n = 6 and P = 25 4 , 8 . Find the rational right-angled triangle of area 6 corresponding to 2P . Find the triangle corresponding to 4P . Exercise 5.9. Find a rational point P other than (0, 0) or (±5, 0) on the curve y 2 = x3 − 25x. Use P to find a rational right-angled triangle of area 5 different from Example 5.4. The hard part of all this is to understand when rational points of the right kind exist in the first place. It is somewhat easier to show that as long as a rational point is not (0, 0) or (±n, 0), then one can go on constructing others with the right properties to guarantee the existence of many rational rightangled triangles with area n. Thus the problem comes down to finding for which n are there any nontrivial rational points. A satisfactory resolution of this problem has recently been given – see p. 243, where Tunnell’s Theorem is stated. We will go on now to relate the geometric construction given before to the existence of a group structure on the curve. Exercise 5.10. The geometric addition on elliptic curves allows us to construct new rational right-angled triangles from existing ones. In this exercise, the same construction is carried out directly on the triangle. Let (x, y, z) be a Pythagorean triple with x < y < z. This construction will find another Pythagorean triple (X, Y, Z) with y 2 − x2 ; 2z 2xyz ; Y = 2 y − x2 x4 + y 4 + 6x2 y 2 Z= . 2z(y 2 − x2 )
X=
5.2 The Congruent Number Problem
103
Let Px , Py , Pz denote the vertices of the triangle, opposite the sides x, y and z respectively. Draw a circle with center Pz and radius x, and let Q be the point on this circle where a tangential line from Px meets the circle (see Figure 5.4). Extend the line Px Py to a point R at a distance 2z from Px . Now draw a circle with center Px through Q, and call S the point of intersection between the circle and the line Px Py . Finally, draw a line through S parallel to QR, and let T be the intersection of this line with Px Q.
R z Py S z
Px
x Pz
y X T Q
Figure 5.4. Constructing a new Pythagorean triple.
Prove that the distance from Px to T is X = continue the construction to find the length Y .
y 2 −x2 2z ,
and show how to
35 Example 5.10. Consider the curve y 2 = x3 − 36x and the point P = ( 25 4 , 8 ) on the curve. Then P is a rational point of infinite order, and we compute that
1726556399 2P = 1442401 19600 , − 2744000
and 4P =
4386303618090112563849601 233710164715943220558400
, − 870369109085580828275935650626254401 11298385812463619737216684496448000 .
104
5 Elliptic Curves
The elliptic curve y 2 = x3 − 36x allows other rational right triangles with area 6 to be computed: Using the points above, one finds the right-angled triangles with sides 120 7 1201 , , 7 10 70 and
2017680 1437599 2094350404801 , , , 1437599 168140 241717895860
each of which has area 6 (see Exercise 5.8 on p. 102). The arithmetic complexity of the rational points in Example 5.10 seems to grow enormously, just as we saw in Example 5.1 on p. 95, and we want to quantify this growth in complexity. As we saw stated in Theorem 5.2, there is a quadratic-exponential growth in the size of the denominators. To make this more precise, we will use a na¨ıve notion of “height” on elliptic curves over the rationals, which allows us to measure how rational points grow in complexity under maps such as P → 2P . This notion of height was introduced by Mordell with the specific aim of proving the following theorem, which was conjectured by Poincar´e. The proof will exercise us considerably in Chapter 7. For an elliptic curve E defined over the rationals, denote by E(Q) the set of points on E with rational coordinates, together with the point ‘at infinity’. The geometrical addition law makes E(Q) into a group, and Mordell’s Theorem says something about the structure of this group. Theorem 5.11. [Mordell’s Theorem] Let E denote an elliptic curve defined over Q. Then E(Q) is a finitely generated Abelian group. A complete proof of this theorem may be found in the references at the end of the chapter. In Section 7.2 we will show how it follows from the so-called weak Mordell Theorem, and then in Section 7.3 will prove the weak Mordell Theorem in a special case. Later developments have placed this result in a more general context. Algebraic curves have an integer parameter called the genus, which measures the topological complexity of the underlying complex space. For an elliptic curve, the fundamental domain (this will be defined in Chapter 6 on p. 122) can be wrapped up into a torus (or doughnut) that is topologically a sphere with one handle. Roughly speaking, the genus counts the complexity in this topological sense when the underlying field of definition is the complex numbers. One of the great challenges facing mathematicians during the last century was to give a properly precise definition of genus when the base field is arbitrary. Remarkably, the genus of a curve seems to govern how many rational points it will have. Elliptic curves have genus one, giving a finitely generated group of rational points. Curves of genus greater than one have only finitely many rational points by a deep result of Faltings. Theorem 5.11 means that E(Q) is isomorphic to Zr × F for some r ∈ N and finite group F . The number r is called the rank of the curve, and it is
5.3 Explicit Formulas
105
conjectured that for any r ∈ N there is a curve defined over the rationals with rank r. The possibilities for the finite group F are more constrained – we will describe some of this in Section 5.4.
5.3 Explicit Formulas In this section we will turn the geometric notion of addition on an elliptic curve into an algebraic formulation that allows computations to be made. We are going to work with a special form of cubic equation throughout this section. Subsequently, we will explain how the different forms of equation relate to each other. As a warm-up, we recommend the following exercise. Exercise 5.11. Let p(x) = x3 + ax2 + bx + c = (x − λ1 )(x − λ2 )(x − λ3 ). Find expressions in a, b and c for λ1 λ2 λ3 , λ1 λ2 + λ1 λ3 + λ2 λ3 , and λ1 + λ2 + λ3 . Given points P1 = (x1 , y1 ) and P2 = (x2 , y2 ) on the elliptic curve y 2 = x3 + ax + b, explicit formulas may be found for x3 and y3 , where P1 + P2 = (x3 , y3 ). Case I: If x1 = x2 , then the line joining P1 to P2 has equation y2 − y1 y − y1 = , x − x1 x2 − x1
so y=
y2 − y1 x2 y1 − x1 y2 x+ . x2 − x1 x2 − x1 !" # !" # α
β
Substituting this into the equation y 2 = x3 + ax + b for the curve gives (αx + β)2 = x3 + ax + b, whose roots are the x-coordinates x1 , x2 , x3 of the three points of intersection with the curve. By the sum of roots formula in Exercise 5.11, we must have x1 + x2 + x3 = α2 , so
x3 = α − x1 − x2 = 2
Reflecting in the x-axis gives P3 , so
y2 − y 1 x2 − x1
2 − x1 − x2 .
106
5 Elliptic Curves
y2 − y 1 x2 y1 − x1 y2 x3 − y3 = −αx3 − β = − x2 − x1 x2 − x1 or y3 = α(x1 − x3 ) − y1 . Case II: Assume that x1 = x2 and y1 = y2 . Let y = αx + β be the equation of the tangent to the curve at (x1 , y1 ). By implicit differentiation of the equation y 2 = x3 + ax + b, we obtain α= and hence 2 2 3x1 + a x3 = − 2x1 , 2y1
3x21 + a , 2y1
y3 =
3x21 + a 2y1
3x21 + a 2y1
2
− 3x1 + y1 ,
so y3 = α(x1 − x3 ) − y1 . Case III: If x1 = x2 and y1 = −y2 , then P1 = −P2 so P3 is the point at infinity. Notice that all the formulas are rational functions (quotients of polynomials) with coefficients in the same field as a and b. This suggests there is a closure property as follows. Let L denote any field over which the curve is defined, and write E(L) for the set of points with coefficients in L together with the point at infinity. Then P1 , P2 ∈ E(L) implies that P1 + P2 ∈ E(L). Thus the group operation is well-defined on E(L). Actually, some care needs to be taken if the characteristic of L is 2 or 3, starting with a different form of equation. We will discuss this further in Section 5.3.2. 5.3.1 Torsion Points Later, we will give a more precise explanation of the identity element for the group operation. For the moment, we continue to think of the identity as the point at infinity, so an equation such as 2P = 0 on the curve E means that a vertical line is a tangent to E at the point P . This allows us to speak of torsion points on an elliptic curve E: P is a point of order dividing n if nP = 0 in this geometrical sense. As we will see, the geometrical definition really gives a group structure to the points on the elliptic curve, and thus the usual terms from group theory such as “torsion” and “order” can be applied. Example 5.12. Consider the curve E : y 2 = x3 + 1, and let P = (2, 3). Using the formulas, we find 2P = (0, 1), 3P = 2P + P = (−1, 0), 4P = 3P + P = (0, −1) = −2P. It follows that 6P = 0 (so P is a torsion point with respect to the group structure on the curve), and since P, 2P, 3P = 0, the point P has order 6 (see Figure 5.5).
5.3 Explicit Formulas
4 P
2 2P 3P −2
1
2
3
4P −2
−4
Figure 5.5. The point P = (2, 3) has order 6 on y 2 = x3 + 1.
Exercise 5.12. Find the order of the point (3, 8) on the elliptic curve y 2 = x3 − 43x + 166. Exercise 5.13. Find the order of the point (0, 16) on the elliptic curve y 2 = x3 + 256. Exercise 5.14. Find the order of the point ( 12 , 12 ) on the elliptic curve y 2 = x3 + 14 x. Exercise 5.15. Find the order of the point (− 13 , 12 ) on the elliptic curve y 2 = x3 − 13 x +
19 108 .
107
108
5 Elliptic Curves
Exercise 5.16. Suppose that K denotes any field with characteristic not equal to 2 or 3, and E : y 2 = x3 + ax + b (a, b ∈ K). Assuming the binary operation defined before makes E(K) into a group, prove that P = (x, y) has order 2 if and only if y = 0. Exercise 5.17. Suppose 1 n ∈ N and consider the elliptic curve E : y 2 = x3 − n2 x. Prove that there are only two real points of order 3 in E(R). Mark these points on a graph of the curve. (They are points of inflexion.) It may be interesting to look at Example 7.2 on p. 134. Exercise 5.18. Use your graph from Exercise 5.17 to show that the subgroup of real points on y 2 = x3 − n2 x with order dividing 4 is isomorphic to C2 × C4 . Exercise 7.5 on p. 138 describes a useful result that allows all the rational torsion points on an integral elliptic curve to be effectively determined. When K = Q, there are not many possibilities for the orders of torsion points in E(Q). For example, in Section 5.4 we show that there are no points of order 11 on any elliptic curve defined over the rationals (assuming a difficult but, in principle, elementary result from Diophantine equations). On the other hand, the complex torsion points on an elliptic curve are easy to describe once we have the necessary function theory – see Section 6.3. 5.3.2 The Equation Defining an Elliptic Curve At several points we have used equations of differing shapes to define an elliptic curve. In the statement of Siegel’s Theorem (Theorem 2.13) we set y 2 equal to a cubic in x with no repeated zeros. The addition formulas in the last section were computed using a special type of cubic. It is fair to ask just what is the correct definition in general. In Chapter 6 we will see that a pair of complex functions parametrize a curve of the shape y 2 = x3 + ax + b in which the right-hand side has no repeated zeros. Because of his important work in the area, this equation became known as a Weierstrass equation or Weierstrass model. We will see that the geometric definition of addition does indeed impose a group structure on the complex solutions of that equation. However, the explicit formulas define a group structure over any field of characteristic other than 2 or 3 (as does the geometrical definition of the group operation when a suitable notion of tangency is developed). We will have to ask you to take this statement on trust, or apply the Lefschetz3 principle. 3
The Lefschetz principle says, in effect, that if an algebraic formula holds in C, then it will hold in any field where it makes sense. Although this is a valid principle, generally it is best used as a pointer toward phenomena that deserve to be better understood, rather in the way that algebraic geometers came to understand elliptic curves and their generalizations.
5.3 Explicit Formulas
109
Suppose then that F denotes any field. It is possible to develop a theory of elliptic curves from one equation, regardless of the characteristic. When using the Weierstrass equation in characteristic 2 or 3, one cannot define tangents adequately (look at what happens when you differentiate). Tate used a more general equation with the following shape: E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6
(5.2)
with a1 , a2 , a3 , a4 , a6 ∈ F satisfying the non-degeneracy condition that every point on the curve has a unique tangent. This condition is equivalent to the non-vanishing of a complicated polynomial expression. For the special case in which Equation (5.2) takes the form y 2 = x3 + ax + b, this non-degeneracy condition is equivalent to the cubic having no repeated zeros, and therefore to the condition that 4a3 + 27b2 = 0 (see Exercise 2.14). The addition formulas can all be worked out for this general equation, in any characteristic. However, the formulas are significantly more complicated and this can hinder the development of intuition about the group law. This is why we prefer to develop the theory for the Weierstrass equation. The Equation (5.2) became known as a generalized Weierstrass equation, although it is becoming usual to refer to this too as a Weierstrass equation. The reader should beware that the modern literature on elliptic curves tends to work with the generalized equation. The following exercise shows how gory the associative law can be when expressed in terms of the algebraic formula, even for the simplest form of equation. Exercise 5.19. Using just the Weierstrass equation y 2 = x3 +ax+b, verify the associative law for addition on an elliptic curve using the algebraic formulas from Section 5.3. Different formulas are required depending upon whether the x-coordinates are equal or not. Even doing one special case of P + (Q + R) = (P + Q) + R is tiresome and requires a great deal of both paper and patience. Although we do not have the space to develop the algebraic geometry needed to properly develop a theory of elliptic curves over arbitrary fields, we recommend doing the following exercise to get a feel for elliptic curves over a finite field. Exercise 5.20. Let E denote the elliptic curve y 2 = x3 − 2. Find the order of the point (3, 5) in the group E(F7 ). What is the order of E(F7 )? Do the same over other fields Fp for primes p. Can you detect any restrictions of the resulting group orders? For a precise result on this theme consult Hasse’s Theorem (Theorem 11.11 on p. 240). In several respects the group E(F), where F denotes a finite field, can be studied along the lines that we studied F∗ . The two groups will often exhibit
110
5 Elliptic Curves
properties that can be directly related – and this phenomenon is useful in cryptography and coding theory. Earlier we proved that F∗ is always a cyclic group. Therefore a natural question is to ask for the structure of E(F). Exercise 5.21. *Let F be a finite field. Prove that E(F) is always a cyclic group or a direct product of two cyclic groups. Find an example where the group has two nontrivial cyclic factors.
5.4 Points of Order Eleven The structure of the points of finite order in the group E(Q) for an elliptic curve defined over the rationals is very constrained: A deep result of Mazur says that the torsion subgroup of E(Q) must be isomorphic to Z/nZ for some n, 1 n 12, n = 11, or to Z/2Z ⊕ Z/nZ, 1 n 4. Proving this important result requires more material, but we can exhibit one nontrivial constraint (assuming a difficult Diophantine result and using some elementary properties of the geometry of the rational projective plane P2 (Q)). If you have not encountered projective space, postpone this section until you have read Section 6.2. In what follows, we use little more than the geometric definition of addition on an elliptic curve to paint a putative rational point of order 11 into a corner where it cannot exist. Theorem 5.13. If E is an elliptic curve defined over Q, then E(Q) has no point of order 11. Proof. Assume that P is a point in E(Q) with order 11. Then no three points of S = {0, P, 3P, 4P } could lie on a straight line because if A, B, C are collinear then A + B + C = 0 by the geometric definition of group addition. Since P has order 11, this last equation is impossible for three distinct points from S. It follows that there is a nonsingular linear map on P2 (Q) sending 0 → [0, 1, 0], P → [1, 0, 0], 3P → [0, 0, 1], and 4P → [1, 1, 1]. To see this, notice first that of the four points [0, 1, 0], [1, 0, 0], [0, 0, 1], [1, 1, 1], no three are collinear, by checking the various determinants. Given any four points with homogenous coordinates v1 , v2 , v3 , v4 , the matrix M = [av1t |bv2t |cv3t ] will, for any a, b, c = 0, send
5.4 Points of Order Eleven
111
[1, 0, 0] → v1 , [0, 1, 0] → v2 , [0, 0, 1] → v3 , and [1, 1, 1] → av1 + bv2 + cv3 . The equation av1 + bv2 + cv3 = v4 has a unique solution with a, b, c all nonzero by the non-collinearity assumption. Thus, by applying a change of variables in P2 (Q), we may assume that 0 = [0, 1, 0], P = [1, 0, 0], 3P = [0, 0, 1], and 4P = [1, 1, 1]. Now let 5P = [x1 , x2 , x3 ]. Then, if 1 is the line through 5P and 0, and 2 is the line through 4P and P , −5P ∈ 1 ∩ 2 . Thus r[0, 1, 0] + s[x1 , x2 , x3 ] = t[1, 0, 0] + w[1, 1, 1], for some r, s, t, w ∈ Q. Comparing coefficients shows that sx1 = t + w; sx2 + r = w; sx3 = w. If s = 0, then P = 0, which is impossible, so without loss of generality we may put s = 1. Then r = x3 − x2 , and so −5P = r[0, 1, 0] + s[x1 , x2 , x3 ] = [x1 , x3 , x3 ]. Similar arguments show that −4P = [1, 0, 1], −P = [x1 − x3 , x2 , 0], −3P = [0, x3 − x1 + x2 , x3 − x1 ], and 2P = [x1 x3 − x21 + x1 x2 , x23 − x1 x3 + x2 x3 , x23 − x1 x3 ]. Since 11P = 0, the points 5P, 4P, 2P are collinear. Taking the determinant of the matrix whose rows are the coefficients of these points, it follows that x33 − x21 x2 + x21 x3 + x1 x22 − 2x1 x23 = 0.
(5.3)
We claim that the only rational solutions to Equation (5.3) are [0, 1, 0], [1, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]. The notes at the end of the chapter provide references where this difficult result is proved. The point 5P must correspond to one of these possibilities. It cannot be [0, 1, 0] because this is 0 and 5P = 0. It cannot be [1, 1, 1] because this is 4P and 5P = 4P implies P = 0. Similarly, it cannot be [1, 0, 0] because this is P and 5P = P implies 4P = 0. It cannot be [1, 0, 1] because this is −4P and 9P = 0. It cannot be [1, 1, 0] because this is −P and 6P = 0. The contradiction proves that there can be no such point P .
112
5 Elliptic Curves
5.5 Prime Values of Elliptic Divisibility Sequences Elliptic curves generate a family of integer sequences that relate to several interesting parts of mathematics, including graph theory and cryptography. Suppose the elliptic curve E has a nontorsion point P ∈ E(Q). Write x(nP ) =
An , Bn2
(5.4)
in lowest terms, with An and Bn in Z. An elliptic analog of the question about Mersenne primes asks how often Bn is prime as n varies. Because Bn grows so rapidly, this is potentially a method to find very large prime numbers. Example 5.14. Let E : y 2 = x3 + 26,
P = (−1, 5).
The term B29 is a prime with 286 decimal digits. Example 5.15. Let E : y 2 = x3 + 15,
P = (1, 4).
The term B41 is a prime with 510 decimal digits. In some respects, this method for producing primes mirrors the situation with sequences such as the Mersenne and Fibonacci sequences, which are expected to produce large primes. For many years, the largest known primes have come from the Mersenne sequence. However, numerical investigation suggests that, for fixed E and P , the sequence (Bn ) should only contain finitely many primes, and a non-rigorous probabilistic argument4 suggests the number of prime terms should be uniformly bounded. Just like the Mersenne and Fibonacci sequences, the sequence (Bn ) is a divisibility sequence, meaning that Bm |Bn whenever m|n. A consequence of this property, together with the rapid growth rate, is that there can only be finitely many primes in the sequence (Bn ) if P is the multiple of another point, or if P is a non-integral point; moreover the terms Bn for large n cannot be prime if the index n is not itself prime. We say that a rational point is a generator if it is not the multiple of any other rational point. Let E and E be two elliptic curves defined over Q. An isogeny is a nonzero homomorphism defined by rational functions on the coordinates of the points: 4
Crudely, the Prime Number Theorem (Theorem 8.1) implies that the probability that a large integer N is prime is approximately 1/ log N . The expected number of prime terms Bn with n < x is (speculatively) approximately n<x 1/ log Bn . By Theorem 5.2 this sum converges as x → ∞. It is known that the quantity h appearing in Theorem 5.2 is uniformly bounded below by some positive constant independent of the initial nontorsion rational point P and curve defined over the rationals E, provided the starting equation has minimal ∆.
5.5 Prime Values of Elliptic Divisibility Sequences
113
φ : E → E. Taking E = E , the multiplication-by-n map P → nP for n ∈ Z is an example of an isogeny. The isogeny has an integral degree m 1, which is the degree of the underlying rational functions that define it. Exercise 5.22. *Prove that the degree of the isogeny P → nP is n2 . The curves E and E are said to be m-isogenous if there is an isogeny of degree m between them. It can be proved that the multiplication-by-n map can be factorized as a composition of two isogenies, each of degree n. Definition 5.16. We say the point P ∈ E(Q) is magnified if it is the image of a rational point under an isogeny of degree m > 1. The term was chosen because the height of a point increases under such a map – see Chapter 7 for more details about heights. The following result of Everest, Miller and Stephens will not be proved here. Theorem 5.17. If P ∈ E(Q) is a magnified point, then Bn is a prime power for only finitely many n. Example 5.18. (1) The curve y 2 = x3 + x2 − 4x is 2-isogenous to the curve in Weierstrass form, E : y 2 = x3 + x2 + 16x + 16. The generator (−2, 2) maps to the generator P = (0, 4) on E. Thus the sequence of denominators for P on E contains only a finite number of prime powers. (2) The curve y 2 = x3 − 9x + 9 is 3-isogenous to the curve in Weierstrass form, E : y 2 = x3 − 189x − 999. The generator (1, 1) maps to the generator P = (−8, 1) on E. Thus the sequence of denominators for P on E contains only a finite number of prime powers. Call the number of distinct prime divisors of an integer its length. The following conjecture has arisen from work of Everest and King. Conjecture 5.19. Given a fixed bound on the length, there are only finitely many terms Bn with length below that bound.
114
5 Elliptic Curves
5.5.1 The curve u3 + v 3 = D This section shows that the primality question can be answered in complete generality for curves in homogenous form. Theorem 5.20. Suppose E denotes a curve defined by an equation u3 + v 3 = D
(5.5)
for some nonzero D ∈ Q. Let P denote a nontorsion Q-rational point. Write, in lowest terms, AP CP P = . , BP BP Then the integers BP are prime powers for only finitely many Q-points P . Note that the shape of the rational points is slightly different; the denominators of the x and y coordinates are not compelled to be powers. These curves, although not in the form to which we are accustomed, are still elliptic curves. The geometric addition used before works here and defines a group. As we shall see, a simple transformation puts them into the more usual form. Example 5.21. As Ramanujan famously pointed out, the taxicab equation5 x3 + y 3 = 1729,
(5.6)
has two distinct integral solutions. These give rise to points P = (1, 12) and Q = (9, 10) on the elliptic curve defined by Equation (5.6). The only rational points on Equation (5.6) that seem to yield prime denominators are 2Q and P + Q (and their inverses). Proof of Theorem 5.20. There is a transformation between the homogenous model given by Equation (5.5) and the Weierstrass model, y 2 = x3 − 24 33 D2 . The transformations are given by 22 3D 22 32 D(u − v) , y= , u+v u+v 2 2 32 D − y 22 32 D + y , v= . u= 6x 6x x=
5
Srinivasa Ramanujan was a largely self-taught mathematical genius. According to C. P. Snow, on one of G. H. Hardy’s visits to Ramanujan in the hospital in Putney, Hardy said “I thought the number of my taxicab was 1729. It seemed to me rather a dull number.” To which Ramanujan replied, “No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways.”
5.5 Prime Values of Elliptic Divisibility Sequences
115
Writing x = X/Z 2 and y = Y /Z 3 , where gcd(X, Z) = gcd(Y, Z) = 1, it follows that 22 32 DZ 3 + Y u= . 6XZ If X divides the numerator of u, then X divides 26 33 D2 . By Siegel’s Theorem (Theorem 2.13), this can only happen finitely often. Since Z is coprime to the numerator, apart from a finite number of points, the denominator of u always has two nontrivial coprime factors. Exercise 5.23. Prove$ that any integer solutions to the equation u3 + v 3 = D have max{|u|, |v|} 2
|D| 3 .
5.5.2 Higher Rank Considerations Let E denote an elliptic curve, defined over Q. We say rational points P and Q are independent if no integer linear combination mP + nQ can represent the point at infinity unless m = n = 0. Theorem 5.22. Let E denote an elliptic curve, defined over Q, and suppose that P and Q denote independent rational points both of which are magnified under the same isogeny. Write x(nP + mQ) =
An,m . 2 Bn,m
(5.7)
Then there are only finitely many pairs (m, n) for which Bn,m is prime. This theorem will not be proved here. Examples of the phenomenon of simultaneous magnification under the same isogeny are not easy to find: The following example uses the generalized Weierstrass form (5.2). Example 5.23. The elliptic curve y 2 + xy = x3 + x2 − 156x + 2070 has independent generators P = (3, 39) and Q = (13, 43) that are magnified under the same 2-isogeny. Remark 5.24. Probabilistic arguments together with results from some numerical experiments suggest that, for certain curves in Weierstrass form (5.2), if P and Q denote independent nontorsion rational points, then the denominator of nP + mQ can be the square of a prime infinitely often. Indeed, there seem to be asymptotically c log X such primes with |m|, |n| < X. Of course, none of the numerical examples that are considered in these arguments use magnified points.
116
5 Elliptic Curves
5.5.3 Elliptic Analogs of Zsigmondy’s Theorem Zsigmondy’s Theorem (Theorem 1.16 on p. 28) has an elliptic analog. Theorem 5.25. [Silverman] Let E denote an elliptic curve defined over Q, in generalized Weierstrass form, and let P = (x(P ), y(P )) denote a nontorAn sion rational point on E. Let x(nP ) = B 2 in lowest terms. Then the elliptic n divisibility sequence (Bn ) satisfies a Zsigmondy theorem: For all sufficiently large n, Bn has a primitive divisor. In view of the fact that sequences such as (Bn ) seem likely to contain only finitely many prime terms, Theorem 5.25 takes on a more interesting status, as a means of producing large primes from elliptic divisibility sequences. Analogs of the precise bound in Theorem 1.15 hold for certain elliptic divisibility sequences. The next result is an explicit bound for the first appearance of a primitive divisor in a congruent number curve. Example 5.26. Let E denote the curve E : y 2 = x3 − 25x and let P = (−4, 6). Then Bn has a primitive divisor for every n > 1. The factorizations of Bn for this example, 2 n 8, with the primitive divisors in bold, are shown in Table 5.2. Table 5.2. Primitive divisors of (Bn ). n Bn Factorization 2 12 22 ·3 3 2257 37·61 4 1494696 23 ·3·72 ·31·41 5 8914433905 5·13·17·761·10601 6 178761481355556 22 ·32 ·11·37·61·71·587·4799 7 62419747600438859233 197·421·215153·3498052153 8 5354229862821602092291248 24 ·3·72 ·31·41·113279·3344161·4728001
There is a difference in the proof for the odd and even terms. For a sequence (Bn ), define the even Zsigmondy bound of (Bn ) to be the greatest even integer n for which Bn does not have a primitive divisor, and similarly define the odd Zsigmondy bound of (Bn ) to be the greatest odd integer for which Bn does not have a primitive divisor. Theorem 5.27. Let E denote the elliptic curve E : y 2 = x3 − T 2 x,
5.6 Ramanujan Numbers and the Taxicab Problem
117
where T 1 is a square-free integer. Let P ∈ E(Q) denote a nontorsion point and write Bn2 for the denominator of x(nP ). Then the even Zsigmondy bound of the sequence (Bn ) is not greater than 18. If x(P ) < 0, then the odd Zsigmondy bound of (Bn ) is not greater than 3. If x(P ) is a square, then the odd Zsigmondy bound is not greater than 21. In specific cases, the terms not covered by Theorem 5.27 can be checked on a computer; this is how Example 5.26 was computed. Theorem 5.27 will not be proved here, but the main idea is contained in the following exercise. The condition stated there for the absence of a primitive divisor is very similar to that found for the Mersenne numbers in Exercise 1.16(b) on p. 28. Exercise 5.24. It can be shown that if Bn does not have a primitive divisor then Bn n Bn/p . p|n
Assuming this, use Theorem 5.2 to deduce that n must be bounded.
5.6 Ramanujan Numbers and the Taxicab Problem In view of Example 5.21 and the story concerning Ramanujan, integers N for which the Diophantine equation N = x3 + y 3 has two nontrivially distinct solutions are sometimes called Ramanujan numbers. Table 5.3 shows the first few of these; there are infinitely many such numbers. In the table u3 + v 3 = x3 + y 3 . Table 5.3. The first few Ramanujan numbers. N 1729 4104 13832 20683 32832
u 1 2 18 10 18
v 12 16 20 27 30
x 9 9 2 19 4
y 10 15 24 24 32
Indeed, it turns out that for any k there are infinitely many numbers N with the property that N can be expressed as a nontrivial sum of two cubes in k essentially different ways. The smallest number T (k) with this property is called the kth taxicab number or Hardy–Ramanujan number. Table 5.4 shows the known taxicab numbers with the pairs whose cubes sum to the number, and the discoverer.
118
5 Elliptic Curves Table 5.4. The first few taxicab numbers. k 1 2 3
4
5
T (k) 2
Pairs 1, 1 1, 12 1729 9, 10 167, 436 228, 423 87539319 255, 414 2421, 19083 5436, 18948 6963472309248 10200, 18072 13322, 16630 38787, 365757 107839, 362753 48988659276962496 205292, 342952 221424, 336588 231518, 331954
Discoverer de Bessy (1657) Leech (1957)
Rosenstiel et al. (1991)
Wilson (1997)
It is suspected that T (6) = 24153319581254312065344. Notes to Chapter 5: The footnote about Bachet’s equation on p. 93 is taken from the book of Silverman and Tate [143]. A very thorough treatment of all aspects of elliptic curves is given in Silverman’s books [139], [142], and aspects of elliptic curves close to the topics in number theory we study are in Koblitz’s book [89]. These books are highly recommended to any reader interested in learning more about elliptic curves. The construction in Exercise 5.10 on p. 102 was shown to us by Bartholdi, and we thank him for permission to include it here. The congruent number problem and its connection to elliptic curves are described in detail in Koblitz’s book [89]. Mordell’s Theorem appears first in his paper [110]; the paper of Poincar´e mentioned is [116]. An attractive historical account of Mordell’s theorem may be found in the paper of Cassells [26]. Faltings’ Theorem on higher-genus curves appears in his papers [61] and [62]. An account of some of the background needed for this proof appears in the conference proceedings [34] edited by Cornell and Silverman. There are expositions of Faltings’ proof by Deligne [41] and Szpiro [149]. The claim about the integral solutions to Equation (5.3) may be found in several places, including a paper [14] by Billing and Mahler; the presentation in Section 5.4 comes from a course taught by Silverberg at Ohio State University. Mazur’s Theorem appeared first in his paper [105]; a treatment may also be found in Silverman’s book [139]. Elliptic divisibility sequences are discussed in the monograph [58, Chapter 10] by Everest, van der Poorten, Shparlinski and Ward. The incidence of primes in these sequences has been studied by Chudnovsky and Chudnovsky [30] (Example 5.14 is taken from that paper), Einsiedler, Everest and Ward [48] and Rogers [131]. Theorem 5.17 appears in the paper [56] of Everest, Miller and Stephens; Example 5.18
5.6 Ramanujan Numbers and the Taxicab Problem
119
comes from Cremona’s Web site [37]. More on Conjecture 5.19 may be found in a paper of Everest and King [54]. More on Remark 5.24 may be found in a paper of Everest, Rogers and Ward [57] or Rogers’ thesis [131]. Exercise 5.23 is taken from the book [143, p. 149] by Silverman and Tate. Theorem 5.25 is proved in Silverman’s paper [140]; Example 5.26 and Theorem 5.27 are taken from a paper of Everest, McLaren and Ward [55]. References for the taxicab numbers in Table 5.4 may be found in Sloane’s on-line encyclopedia of integer sequences [144]; there is an elementary account of the connection between T (2) and elliptic curves in an accessible paper by Silverman [141], and the calculation of T (5) is described in an article by Wilson [163].
6 Elliptic Functions
Elliptic curves can be viewed from many different mathematical perspectives. In the last chapter, they were seen as primarily geometrical objects; in this chapter, we start by emphasizing their relationship with some classical transcendental functions from complex analysis. To motivate the material in this chapter, recall that the trigonometric functions sine and cosine parametrize the points on the circle S1 . The rational points on the circle in turn parametrize Pythagorean triples. This gives a triangle of ideas involving the circle: in one corner are the classical transcendental functions, in another a compact group, and in the third a connection to a Diophantine problem. In the last chapter, we saw two corners of an analogous triangle involving elliptic curves. Rational points on elliptic curves give solutions to various Diophantine problems. Our next goal is to fill out the third corner of the elliptic triangle by finding transcendental functions that parametrize the points on elliptic curves. An important by-product of our work will be the justification that the operation defined by geometry in Chapter 5 really satisfies the axioms for a group. (See Theorem 6.5 and the comments just after.)
6.1 Elliptic Functions Let L ⊆ C denote a lattice in the complex plane. This means L is the set of integer linear combinations of two complex numbers w1 and w2 that are linearly independent over R. Write ω1 , ω2 for the lattice ω1 Z + ω2 Z ⊆ C. More generally, a lattice in Rn is any subgroup isomorphic to Zn ; a lattice in C coincides with this definition by viewing C as R2 . One of the ways lattices of different dimensions arise naturally is in the study of periodic functions. The best-known example is the exponential function e : R → S1 = {z ∈ C | |z| = 1} x → eix
122
6 Elliptic Functions
This is a periodic function because it satisfies e(x + 2π) = e(x) for all x ∈ R, so e is periodic with respect to the one-dimensional lattice 2πZ ⊆ R. We are interested in complex functions f with the doubly-periodic property that f (z + ω1 ) = f (z + ω2 ) = f (z), that is, functions that are periodic with respect to L or L-periodic.
ω1 ω2
Figure 6.1. The lattice L spanned by ω1 and ω2 in C.
The lattice L is represented as a discrete subset of C in Figure 6.1: The points of L are the points where the dashed lines intersect. The shaded region Π = {r1 ω1 + r2 ω2 | 0 r1 , r2 < 1} is a fundamental domain for the quotient C/L in the sense that each coset of L has exactly one representative in Π. The L-periodic function analogous to the exponential function that we will study is called the Weierstrass ℘-function corresponding to L. For any z ∈ / L, this is defined to be 1 1 1 . (6.1) − ℘L (z) = 2 + z (z − )2 2 0=∈L
6.1 Elliptic Functions
123
The elements of L have to be enumerated in some way in order to define the sum. For the moment,suppose some enumeration L\{0} = {1 , 2 , . . . } has ∞ been fixed and define 0=∈L f () to be n=1 f (n ). We will first prove that the series in Equation (6.1) converges absolutely. It follows that the order in which the enumeration takes place does not affect the value of the sum. Lemma 6.1. The series 1 1 1 ℘L (z) = 2 + − 2 z (z − )2 0=∈L
is absolutely convergent for any z ∈ / L. The series defines a meromorphic function whose only singularities are double poles at each lattice point in L. Proof. Let z be any point not in L. Write 1 1 1 2z − z 2 / − = . . (z − )2 2 3 (z/ − 1)2 Since |z/ − 1| is bounded below by a positive constant, there is a constant C1 depending on z such that 1 C1 1 − . ≤ (z − )2 2 ||3 Therefore, it is enough to prove that the series 0=∈L ||−3 converges. To see this, notice first that there is a constant C > 0 with the property that |mω1 + nω2 |
1 max{|m|, |n|}. C
Exercise 6.1. Prove that there are 8k integer pairs (m, n) with max{|m|, |n|} equal to k. (See Figure 6.2, which suggests an inductive proof.) It follows that 0=∈L
||−3 =
(m,n)=(0,0)
C3 ·
1 |mω1 + nω2 |3
(m,n)=(0,0)
= C3 ·
∞ 8k k=1
k3
1 max{|m|, |n|}3
= 8C 3
∞ 1 , k2
k=1
which converges. We have shown that the series defining ℘L (z) converges absolutely for z ∈ C\L. Finally, it is clear that the only pole of ℘L in Π is a double pole at 0 since
124
6 Elliptic Functions
r
r
r
r
r r 6
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r -
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
Figure 6.2. There are 8k integer pairs (m, n) with max{|m|, |n|} = k.
℘L (z) −
1 1 1 = − z2 (z − )2 2 0=∈L
converges absolutely in Π. Similarly, for any ∈ L, 1 1 1 1 + 2 = − ℘L (z) − 2 2 (z − )2 (z − ) z =∈L; =0
converges absolutely in Π + for the same reason, showing that the only pole of ℘L in Π + is a double pole at . The absolute convergence of ℘L (z) means that Equation (6.1) can be differentiated term by term (see Exercise 6.2 below) to give ℘L (z) = −2
∈L
1 , (z − )3
(6.2)
which also converges absolutely. It is clear that ℘L (z) is periodic with respect to L since if 0 ∈ L ℘L (z + 0 ) = −2
∈L
1 1 = −2 3 (z + 0 − ) (z − )3 ∈L
is just a rearrangement of the terms. Our ultimate goal is to prove that ℘L is periodic with respect to L. Periodicity of ℘L does not itself imply this, of course, but a simple argument does allow us to deduce it.
6.1 Elliptic Functions
125
∞
n Exercise 6.2. (a) Let f (z) = be a complex power series with n=0 cn z radius of convergence R > 0. Prove that f is differentiable (see ∞Definition 8.18 on p. 170) on the set {z ∈ C | |z| < R} and that f (z) = n=1 ncn z n−1 on this set. (b) Show how to use this to justify the expression Equation (6.2) by using the absolute convergence of the series defining ℘L to show that it may be expanded as a power series.
What we have done up to now might seem clumsy: Given a series whose terms are clearly differentiable, the most natural way to show it is differentiable is surely to differentiate term by term. This is a reasonable criticism, however it involves a more subtle notion of convergence called uniform convergence (see Section 8.5). Term-by-term differentiability is easily provable for power series, whose terms are simply monomials, but can be much trickier when the terms are more complicated functions. This alternative approach to the analyticity of ℘L is given in Exercise 8.20 on p. 173, using the concept of uniform convergence, once we have had time to introduce the concept properly. Lemma 6.2. The Weierstrass ℘-function ℘L is periodic with respect to L. Proof. We want to prove that ℘L (z + ω1 ) = ℘L (z + ω2 ) = ℘L (z) for all z ∈ / L. First, notice that by Equation (6.1) and Equation (6.2), ℘L (−z) = ℘L (z) and ℘L (−z) = −℘L (z). That is, ℘L (z) is an even function and ℘L (z) is an odd function. Now fix i to be 1 or 2 and let f (z) = ℘L (z + ωi ) − ℘L (z). Then f is differentiable for all z ∈ / L. Since ℘L (z) is periodic with respect to L, we deduce that f (z) = 0 for all z ∈ C\L, so f is constant on this open connected set. To determine the constant value of f let z = −ωi /2. Then f (−wi /2) = ℘L (ωi /2) − ℘L (−ωi /2), which shows that f (−ωi /2) = 0 since ℘L is an even function. It follows that f must be zero everywhere, showing that ℘L is periodic with respect to L. Definition 6.3. An elliptic function is a meromorphic function C → C that is periodic with respect to a lattice L. If L = Zω1 + Zω2 , then ω1 and ω2 are known as periods. With respect to a chosen basis {ω1 , ω2 }, the domain Π = {r1 ω1 + r2 ω2 | 0 r1 , r2 < 1} for the lattice L is the fundamental domain.
126
6 Elliptic Functions
Lemma 6.4. An elliptic function with no poles in its fundamental domain is constant. Let Πβ = β + Π be the fundamental domain translated by β ∈ C, and let f denote an elliptic function with no zeros or poles on the boundary of Πβ . If the zeros of f in Πβ have orders mi and the poles have orders nj , then mi = nj . Proof. The first statement is clear: Any such function would be bounded on Π, and therefore on all of C, by periodicity, so it is a bounded entire function and therefore must be constant by Liouville’s Theorem. For the second statement, first notice that f (z) dz = 0 Πβ
since f has the same values on opposite sides of Πβ , while dz changes sign. The result now follows by applying this to the elliptic function g(z) = f (z)/f (z). Near a zero z0 of order m for f , g has a simple pole with residue m (that m near z0 ). Near a pole z0 of order n for f , g has a is, g(z) behaves like z−z 0 n ). simple pole with residue −n (that is, g(z) behaves like − z−z 0 Cauchy’s Residue Theorem gives the result.
6.2 Parametrizing an Elliptic Curve Lemma 6.4 will be used to prove the main result of this section: The values of ℘L (z) and ℘L (z), for z lying in the fundamental domain, parametrize a complex elliptic curve. Before stating this important result, we return to the question raised at the end of Section 5.1: What is the identity element for the binary operation on an elliptic curve? In order to answer this, we need to come clean about elliptic curves. The discussion in Section 5.1 concerned the set of solutions to an equation y 2 = x3 + ax2 + bx + c in R2 ; these are just an affine part of the real points of the curve. A complex elliptic curve is really the set of complex points in projective space satisfying the projectivized version of the equation. The vague notion of adding a point ‘at infinity’ can be made precise by studying elliptic curves in this more natural setting of projective space. Two-dimensional projective space P2 (C) is defined to be the set of equivalence classes P2 (C) = {(z0 , z1 , z2 ) ∈ C3 | (z0 , z1 , z2 ) = (0, 0, 0)}/ ∼, where (z0 , z1 , z2 ) ∼ (z0 , z1 , z2 ) if there is a constant λ = 0 with (z0 , z1 , z2 ) = (λz0 , λz1 , λz2 ). An element of P2 (C) is then an equivalence class, and we write
6.2 Parametrizing an Elliptic Curve
127
[z0 , z1 , z2 ] = {(z0 , z1 , z2 ) | (z0 , z1 , z2 ) ∼ (z0 , z1 , z2 )} for the equivalence class containing (z0 , z1 , z2 ). The complex elliptic curve E(C) associated with the equation E : y 2 = x3 + ax2 + bx + c is the subset of P2 (C) defined by E(C) = {[z0 , z1 , z2 ] | z12 z2 = z03 + az02 z2 + bz0 z22 + cz23 }. Notice that this curve contains two parts. If z2 = 0, then we can assume without loss of generality that z2 = 1, so all the points [z0 , z1 , 1] with z12 = z03 + az02 + bz0 + c lie on E. This is the complex affine part of the curve. There is exactly one point with z2 = 0 (if z2 = 0, then z0 = 0 so z1 must be nonzero), namely [0, 1, 0]. This point is the “point at infinity” on the curve. We will write E : y 2 = x3 + ax2 + bx + c for the complex projective curve, suppressing the third variable (because it only contributes one point to the curve). We will always assume that the righthand side has no repeated zeros. (See Exercise 2.14 for a simple formulation of this condition in the case a = 0.) It will be useful to talk about the K-points of an elliptic curve for other fields K. The curve E : y 2 = x3 +ax2 +bx+c is said to be defined over a field L if the coefficients a, b, c come from L. For any field K containing L, the Kpoints of the curve, E(K), are the points in E whose projective coordinates can be chosen in K. Thus E(C) is the complex projective curve. The following is a major result and most of this section will be devoted to the proof. Theorem 6.5. Let L ⊆ C denote a lattice with fundamental domain Π. (1) There are constants a = a(L) and b = b(L) with 4a3 + 27b2 = 0 such that, for all z ∈ C\L, 1 2 4 ℘L (z)
= ℘L (z)3 + a℘L (z) + b.
(2) For z ∈ C/L, the map π : Π → P2 (Q) defined by π(0) = [0, 1, 0] and π(z) = [℘L (z), 12 ℘L (z), 1],
z = 0,
defines a bijection between Π and the set of complex projective points on the elliptic curve E : y 2 = x3 + ax + b. (3) Suppose z1 , z2 , z3 ∈ Π have images π(zi ) = Pi , i = 1, 2, 3. Then z 1 + z2 + z3 = 0 in Π if and only if P1 , P2 , and P3 lie on a straight line.
128
6 Elliptic Functions
The last part of the theorem is the long-awaited justification that the operation defined on the points of an elliptic curve in Chapter 5 is a group operation. Under the bijection π : z → [℘L (z), 12 ℘L (z), 1],
z = 0,
the fact that the point 0 = z ∈ C/L corresponds to the point at infinity relates the geometrical idea of infinity on the projective curve to the analytic idea that ℘L (z) −→ ∞ as z −→ 0. This is important if we work with the projective curve because the set of projective points forms a group with the point at infinity as the identity. Notice that this arises simply by transporting the group structure of C/L to the curve E. Theorem 6.5(3) says that the familiar addition in C is related, via the transcendental functions ℘L and ℘L , to the geometric addition on the projective curve. This transport of structure from the additive group C to the curve proves that the geometric binary operation on the projective curve really does satisfy the group axioms. Now the ‘Lefschetz principle’ (see the footnote on p. 108) shows that this result over C extends to verify the group law for elliptic curves over arbitrary fields in characteristic not equal to 2 or 3. Exercise 6.3. Show that ℘L (ω1 /2) = ℘L (ω2 /2) = ℘L ((ω1 + ω2 )/2) = 0. Show that there are no other solutions of ℘L (z) = 0 with z ∈ Π. Exercise 6.3 identifies the 2-torsion points on the elliptic curve with reference to the lattice L. The complex torsion on an elliptic curve can easily be described. We will take a brief interlude to apply Theorem 6.5 to the study of the complex torsion points on an elliptic curve. The proof of Theorem 6.5 will follow in Section 6.4.
6.3 Complex Torsion Theorem 6.5 allows the torsion points on an elliptic curve to be understood in a way that is analogous to our understanding of torsion points on the circle: Since e : R → S1 has kernel 2πZ, it induces an isomorphism e : R/2πZ −→ S1 . The distinct points of order dividing n in the additive group R/2πZ are those of the form 2πj n +2πZ for j = 0, 1, . . . , n−1. We deduce that the points of order dividing n in S1 are those of the form e(2πj/n) = e2πij/n for j = 0, 1, . . . , n−1. It is not difficult to find the points of order dividing n on S1 . Theorem 6.5 repeats the trick for the problem of finding all points of order dividing n for the group operation on a complex elliptic curve. Given 1 n ∈ N, the points
6.4 Partial Proof of Theorem 6.5
129
z = (r1 ω1 + r2 ω2 )/n for 0 r1 , r2 n all have nz ≡ 0 modulo L, and these are the n2 points with order dividing n in the group C/L. These are torsion points on the complex curve. Deciding which of these points correspond to rational torsion points on the curve is a different and difficult question. Exercise 6.4. Let En (C) for n ∈ N denote the subgroup of points on a complex elliptic curve E whose order divides n. Show that En (C) ∼ = Z/nZ ⊕ Z/nZ.
6.4 Partial Proof of Theorem 6.5 We are not going to prove all of Theorem 6.5; in particular we will not prove that the quantity 4a3 + 27b2 is not zero. A complete account may be found in the references. What we will show is how the important equation in Theorem 6.5(1) arises. Proof of Theorem 6.5(1). Assume first that z has |z| < || for all nonzero ∈ L. Then the Taylor expansion about z = 0 gives 1 1 1 1 2z 3z 2 4z 3 − 2 = 2 (1 − z/)−2 − 2 = 3 + 4 + 5 + · · · . 2 (z − ) By absolute convergence of the series defining ℘L (z), we can rearrange the terms in 2z 1 3z 2 4z 3 ℘L (z) = 2 + + 4 + 5 + ··· z 3 0=∈L
to get ℘L (z) =
1 + 2z −3 + 3z 2 −4 + 4z 3 −5 + · · · . 2 z
indicates that the sum is over the nonzero lattice points ∈ L only. For The any n ∈ N, the terms of the form −(2n+1) as runs through the nonzero terms −2n−1 of L cancel out in pairs: (−)−2n−1 = −−2n−1 . It follows that = 0, so the Laurent expansion of ℘L (z) about z = 0 looks like ℘L (z) =
1 + 3z 2 G4 (L) + 5z 4 G6 (L) + · · · , z2
where G2n (L) =
(6.3)
−2n , 1 n ∈ N.
This expression agrees with the classical result that even meromorphic functions only have even powers in their Laurent expansion at 0.
130
6 Elliptic Functions
Consider the function g(z) = ℘L (z)2 − 4℘L (z)3 + 60G4 (L)℘L (z) + 140G6 (L). This function is analytic on Π, moreover g is periodic with respect to L because it is an algebraic expression in periodic functions. Finally, it can be checked that the Laurent expansion of g(z) contains only positive powers of z. By Lemma 6.4, g must be a constant. Setting z = 0 shows that this constant value must be zero, so g is the zero function and hence the equation stated in the theorem holds (after dividing by 4). Notice that a = −15G4 (L) and b = −35G6 (L). Notice that Theorem 6.5(1) is a statement about all z ∈ C\L. In the proof, we have assumed that |z| < || for all nonzero lattice points. This means in
2 particular that the proof is valid for all points in the region − ω1 +ω + Π; 2 it follows for all z ∈ C\L by periodicity. Exercise 6.5. (a) Let L = 1, i. Show that the corresponding curve EL has equation y 2 = x3 + ax for some a ∈ R. (b) Let L = 1, ω, where ω denotes a cube root of unity. Show that the corresponding elliptic curve EL has equation y 2 = x3 + b for some b ∈ R. Proof of Theorem 6.5(2). We show that the map is a bijection, beginning with surjectivity. Suppose α ∈ C is given. The function ℘L (z) − α has two poles (actually one double pole) in Π so, by Lemma 6.4, it must have two zeros. To prove injectivity (which appears to be threatened by the existence of the two zeros) note that the two zeros are negatives of each other. This is because, for z ∈ / L, ℘L (−z) = ℘L (z). However, ℘L (−z) = −℘L (z). Thus, the images of z and −z will (usually) be distinct points on the curve, the only counterexamples arising when ℘L (z) = 0. By Exercise 6.3, this happens for only three values of z, namely w1 /2, w2 /2, and (w1 +w2 )/2, but this is exactly when z and −z define the same element of C/L. Finally, we show how an argument using complex analysis gives the third part of Theorem 6.5. Proof of Theorem 6.5(3). Let the equation of the line containing the points P1 and P2 be y = mz + b. Consider the function f (z) = ℘L (z) − m℘L (z) − b. This has three poles in Π (actually one triple pole) so, by Lemma 6.4, it has three zeros. Two of these are z1 and z2 ; let z3 denote the third. Then P1 , P2 , and P3 lie on the line y = mz + b and (3) is seen by integrating the function h(z) = zf (z)/f (z) over a displaced parallelogram Πβ = β + Π, where β is chosen so that h has no singularities on the boundary Γβ of Πβ shown in Figure 6.3.
6.4 Partial Proof of Theorem 6.5
131
β + ω1 + ω2 β + ω1
β + ω2 β
Figure 6.3. Integrating along the four sides of Γβ .
The main part of the proof is to show that z1 + z2 + z3 ∈ L. By Cauchy’s Residue Theorem, 1 (6.4) h(z) dz = z1 + z2 + z3 2πi Γβ because h has a simple pole at each zi with residue zi . Now break the integral in Equation (6.4) into two parts corresponding to pairs of opposite sides in Γβ : β+ω2 β+ω1 1 1 h(z) dz = h(z) dz + h(z) dz 2πi Γβ 2πi β β+ω1 +ω2 β β+ω1 +ω2 1 + h(z) dz + h(z) dz 2πi β+ω2 β+ω1 = I1 + I2 .
Substitute z = w + ω2 in the second integral of I1 , and use the periodicity of f to obtain β+w1 β+w1 zf (z) (z + w2 )f (z) 1 dz − dz I1 = 2πi f (z) f (z) β β ω2 β+ω1 f (z) = dz. 2πi β f (z) Now make the substitution u = f (z) to deduce that 1 ω2 I1 = du, 2πi Ω u where Ω is the image of the line joining β to β+ω1 in the variable u. Periodicity with respect to L means that Ω is a closed curve, so we finally obtain
132
6 Elliptic Functions
I1 =
ω2 2πi
Ω
1 du = mω2 ∈ Zω2 , u
where the integer m is the winding number, counting the number of times Ω winds around zero. A similar argument for the two other sides of Πβ shows that I2 = nw1 for some n ∈ Z. Thus z1 + z2 + z3 = nw1 + mw2 ∈ L. Exercise 6.6. (a) Prove that, for any lattice L ⊆ C, G8 (L) = 37 G24 (L). (b) More generally, prove that all the Gi (i 8) can be expressed as polynomials in G4 and G6 with rational coefficients. Exercise 6.7. (a) Given any nonzero c ∈ C, consider the map L → cL = L . Let EL and EL denote the corresponding elliptic curves. Prove that the map defines a group isomorphism between EL (C) and EL (C). (b) Prove that the map in (a) has the following effect upon the coordinates of the corresponding curves. If y 2 = x3 + ax + b is the equation defining EL and y 2 = x3 + a x + b is the equation defining EL , show that the effect of the map in (a) is to take (x, y) to (c−2 x, c−3 y). (Hint: Recall the definition of a and b from Theorem 6.5(1).) Exercise 6.8. (a) Show that, for any lattice L and c ∈ C∗ , G4 (cL) = c−4 G4 (L) and G6 (cL) = c−6 G6 (L). (b) Prove that any elliptic curve y 2 = x3 + ax + b with ab = 0 is parametrized by the Weierstrass ℘-function for some lattice L. Notes to Chapter 6: The Lefschetz principle is discussed in Silverman [139, Section VI.6]. Theorem 6.5 is also proved in [139] along with a converse result: Given a and b with 4a3 + 27b2 = 0, there exists a lattice L such that ℘L (z) and 12 ℘L (z) parametrize the elliptic curve with equation y 2 = x3 + ax + b. For an explanation of the remarkable phenomenon described in Exercise 6.6(b), consult Koblitz [89]. A classical treatment of elliptic functions from the analytic viewpoint is contained in Whittaker and Watson [160]; there are sophisticated accounts of elliptic functions and their role in number theory in the books of Apostol [5], Chandrasekharan [29], Lang [95] and Weil [159].
7 Heights
In this chapter we introduce a way to measure the arithmetic complexity of points on elliptic curves. This measurement of the height turns out to be an essential ingredient in understanding the structure of the rational points on an elliptic curve. Our understanding of heights will be a key ingredient in the proof of Mordell’s Theorem in Section 7.2.
7.1 Heights on Elliptic Curves Given a rational affine point P = ( M N , ∗), where M and N are coprime integers, define the na¨ıve height of P to be max{|M |, |N |} if M N = 0, H(P ) = 1 if M = 0. Write x(P ) and y(P ) for the coordinates of an affine point P = (x(P ), y(P )). Define the logarithmic height to be h(P ) = log H(P ). The definition of the complex projective plane P2 (C) on p. 126 extends to higher dimensions: For any field K, projective N -space over K is defined by PN (K) = {(x0 , . . . , xN ) | (x0 , . . . , xN ) = (0, . . . , 0)}/ ∼, where (x0 , . . . , xN ) ∼ (x0 , . . . , xN ) if there is a constant λ ∈ K∗ with (x0 , . . . , xN ) = λ(x0 , . . . , xN ). As before, we write [x0 , . . . , xN ] for the equivalence class (or point in projective space) containing the affine point (x0 , . . . , xN ). The na¨ıve height extends to projective space PN (Q). Given a point [y] in PN (Q), choose x = (x0 , . . . , xN ) ∈ ZN +1 in such a way that [y] = [x] and gcd(x0 , . . . , xN ) = 1.
134
7 Heights
Then the projective height H : PN (Q) → R is defined by H([x]) = max {|xi |}. i=0,...,N
Notice that this is compatible with the na¨ıve height in the following sense: If P = (x, y) is a point on the affine piece of E(Q), then H(P ) = H([x, 1]), where [x, 1] ∈ P1 (Q). The logarithmic quantity h(P ) is a simple example of a Mahler measure: log max{|M |, |N |} = m(N x − M ) (see p. 150). Examples 5.1 and 5.10 suggest that the number of decimal digits in the numerator and the denominator roughly quadruples each time a point is doubled. This is a manifestation of a general phenomenon, the duplication formula. Theorem 7.1. [Duplication Formula] Let E denote an elliptic curve defined over the rationals, and let P be a point in E(Q). Then h(2P ) = 4h(P ) + O(1),
(7.1)
where the implied constant in O depends on E but not on the point P . This will be proved on p. 137 after some more machinery has been developed. In multiplicative notation, the duplication formula may be written H(P )4 H(2P ) H(P )4 . Example 7.2. Consider the curve E : y 2 = x3 − n2 x with 1 n ∈ N. Let P be a rational point on E. A calculation gives x(2P ) = so if x(P ) =
M N
x2 + n2 2y
2 =
(x2 + n2 )2 , 4(x3 − n2 x)
in lowest terms, then x(2P ) =
(M 2 + n2 N 2 )2 . 4M N (M 2 − n2 N 2 )
(7.2)
It may be checked that any cancellation in Equation (7.2) is bounded: Explicitly, if d divides both numerator and denominator, then d|16n6 . Examining the cases |M | |N | and |M | < |N | separately shows that max{|M 2 + n2 N 2 |2 , |N 2 (M 2 − n2 N 2 )|}
7.1 Heights on Elliptic Curves
135
is commensurate1 with max{|M |4 , |N |4 } = max{|M |, |N |}4 , and the duplication formula Equation (7.1) follows. Exercise 7.1. Verify Theorem 7.1 for the curve y 2 = x3 + C, C = 0. The duplication formula is a special case of a general principle about polynomial maps on projective space, and so we prove Theorem 7.1 in greater generality. A polynomial f in N variables is called homogenous if there is a constant d ∈ N (the degree of f ) with f (λx0 , . . . , λxN ) = λd f (x0 , . . . , xN ). Exercise 7.2. Let f0 , . . . , fM be polynomials in N + 1 variables. Show that the map x → (f0 (x), . . . , fM (x)) between KN +1 and KM +1 induces a welldefined map PN (K) → PM (K) if and only if the polynomials f0 , . . . , fM are all homogenous of the same degree and the only common zero of the polynomials is the point (0, . . . , 0). Definition 7.3. A map f : PN (Q) −→ PM (Q) is called a morphism of degree d if f ([x]) = f ([x0 , . . . , xN ]) = [f0 ([x]), . . . , fM ([x])], where the fj , 0 j M are homogenous polynomials of degree d with the property that the only common zero is 0. Lemma 7.4. Let f : PN (Q) → PM (Q) be a morphism of degree d. Then H([x])d H(f ([x])) H([x])d . Proof. Write f ([x]) = [f0 (x), . . . , fM (x)], where [x] = [x0 , . . . , xN ] ∈ PN (Q). By clearing denominators, we may assume that each xj is an integer. Since each fi is homogenous of degree d, they may be written fi (x) = ce xe00 · · · xeNN , with ce ∈ Q, ei ∈ N, e0 + · · · + eN = d, and only finitely many ce nonzero. It follows that there is a constant C such that 1
In the sense that the ratio is bounded above and below by positive constants independent of N and M .
136
7 Heights
|fi (x)| C · (max{|xj |})d , for each i and all j, so there is a similar bound for max{|fi (x)|}. To find the height, notice that the only possible denominators that need to be cleared come from the coefficients of the polynomials fi , which is a bounded quantity in total. It follows that there is an upper bound for the height of the form C · H(x)d . To get the lower bound, we use Hilbert’s Nullstellensatz: There exists e ∈ N and polynomials gij ∈ Q[x] such that xe0 = g00 (x)f0 (x) + · · · + g0N (x)fN (x) .. . xeN = gN 0 (x)f0 (x) + · · · + gN N (x)fN (x). The gij s can be taken to be homogenous polynomials of degree (e − d) so |gij (x)| (max{|xk |})e−d . On the other hand, xej = gj0 (x)f0 (x) + · · · + gjN (x)fN (x) for j = 0, . . . , N , so (max{|xj |})e−d max{|f0 |, . . . , |fN |} (max{|xj |})e . It follows that max{|f0 |, . . . , |fN |} (max{|xj |})d , and since the only possible denominators are those arising from the coefficients of the fi , the lower bound is proved. Example 7.5. To see that e > d really occurs in the Nullstellensatz, define f : P1 (Q) → P1 (Q) by f : [x0 , x1 ] → [x20 , (x0 + x1 )2 ] = [f0 (x0 , x1 ), f1 (x0 , x1 )]. Then f is a morphism of degree 2. Now x20 = 1 · f0 , but there are no rational polynomials A, B for which x21 = A · f0 + B · f1 . However, x30 = x0 · f0 x31 = (2x0 + 3x1 ) · f0 + (−2x0 + x1 ) · f1 .
7.1 Heights on Elliptic Curves
137
Exercise 7.3. (a) Using the explicit formulas from Example 7.2, prove that the map defined by [x(P ), 1] → [x(2P ), 1] is a morphism of degree 4 for the curve y 2 = x3 − n2 x. (b) Do the same for the curve y 2 = x3 + c. Proof of Theorem 7.1. By Lemma 7.4, all we need to show is that the map [x, 1] → [x(2P ), 1] on P1 (Q) is a morphism of degree 4. Assume that the curve is E : y 2 = x3 + ax + b and P = (x, y). Then 2 3x2 + a − 2x 2y (3x2 + a)2 − 2x 4y 2 9x4 + 6x2 a + a2 − 2x 4(x3 + ax + b) x4 − 2x2 a − 8xb + a2 . 4(x3 + ax + b)
x(2P ) = = = =
Write x = xx01 ∈ Q (in lowest terms as usual). Then, writing x(2P ) = and dropping a factor of 4,
f0 (x0 ,x1 ) f1 (x0 ,x1 )
f0 (x0 , x1 ) = x40 − 2x20 x21 a − 8x0 x31 b + a2 x41 , and f1 (x0 , x1 ) = x30 x1 + ax0 x31 + bx41 . To show that these define a morphism of degree 4, it only remains to show that the unique common zero of f0 and f1 is (0, 0). If f0 = f1 = 0 and x1 = 0, then x0 = 0. Assume x1 = 0. Then we may assume that x1 = 1 and x0 = x. We now need to show that f (x) = x4 − 2x2 a − 8xb + a2 , and g(x) = x3 + ax + b cannot have a common zero. One way to see this is using resultants (see Exercise 7.4); we will use the Euclidean Algorithm (see Example 2.3(2)) to find the greatest common divisor of f and g. Assume first that a = 0 and recall we are assuming that 4a3 + 27b2 = 0. The Euclidean Algorithm gives
x4 −2x2 a−8xb+a2 = x3 +ax+b x−3ax2 −9bx+a2 ; 2
1 9b 4 b x3 + ax + b = −3ax2 − 9bx + a2 − x + 2 + + a x; 3a a a2 3 9a3 27ba2 4 b2 +a2, − 3 x− −3ax2 −9bx+a2 = a+9 2 x 3 a 4a +27b2 (4a3 +27b2 )
138
7 Heights
which shows that the greatest common divisor of f and g is a nonzero constant. If a = 0 then b = 0 since 4a3 + 27b2 = 0, so the Euclidean Algorithm gives x4 − 8xb = (x3 + b)x − 9xb; 1
(x3 + b) = (−9xb) − 9b x + b, which, again, shows the greatest common divisor of f and g is a nonzero constant. Exercise 7.4. Show that the resultant of the polynomials f (x) = x4 − 2x2 a − 8xb + a2 and g(x) = x3 + ax + b is (4a2 + 27b2 )2 . This shows that the condition 4a3 + 27b2 = 0 implies that f and g have no common zero. Exercise 7.5. Let E : y 2 = x3 + ax + b with a, b ∈ Z denote an elliptic curve. Using arguments from p-adic analysis, it can be shown that any nonzero torsion point Q ∈ E(Q) must have x(Q) and y(Q) integral. Assuming this, prove that y(Q) = 0 or y(Q)2 divides 4a3 +27b2 for any rational torsion point. Exercise 7.6. Recall from Exercise 5.12 that the point P = (3, 8) has order 7 on the elliptic curve y 2 = x3 − 43x + 166. Using Exercise 7.5, show that there are no rational torsion points other than those in the subgroup generated by P .
7.2 Mordell’s Theorem In this section, we will see how Mordell’s Theorem follows from the weak Mordell Theorem. In the next section, we will give a proof of the weak Mordell Theorem for the congruent number curve and discuss how the proof can be extended to cover a wider class of curves. The proof in full generality requires more algebraic number theory than we have at our disposal. Complete proofs may be found in the references discussed at the end of the chapter. Theorem 7.6. [Weak Mordell Theorem] Let E denote an elliptic curve defined over Q. Then E(Q)/2E(Q) is a finite Abelian group. Lemma 7.7. Let E : y 2 = x3 + ax + b be an elliptic curve defined over the rationals. (1) If P0 = 0 is a point in E(Q), then there is a constant c1 = c1 (E, P0 ) > 0 such that h(P + P0 ) < 2h(P ) + c1 . (7.3)
7.2 Mordell’s Theorem
139
(2) Given h0 > 0, there are only finitely many points P ∈ E(Q) with h(P ) < h0 . Proof. (2) is clear since only finitely many rationals m n (in lowest terms) have log max{|m|, |n|} < h0 . To prove (1), write P = (x, y) and P0 = (x0 , y0 ). From the equation y 2 = x3 + ax + b, write (in lowest terms) x=
s r s r , y = 3 , x0 = 20 , y0 = 30 , 2 t t t0 t0
with r, s, t, r0 , s0 , t0 all integers. Then x(P + P0 ) =
y0 − y x0 − x
2 − x − x0
=
y02 − 2y0 y + y 2 (x0 + x) 2 − (x − 2x0 x + x2 ) (x0 − x)2 (x0 − x)2 0
=
x30 + ax0 + b + x3 + ax + b − 2y0 y (x0 − x)2 −
(x30 − 2x20 x + x0 x2 + xx20 − 2x0 x2 + x3 ) (x0 − x)2
=
a(x0 + x) + 2b − 2y0 y − (−x20 x − x2 x0 ) (x0 − x)2
=
a(x0 + x) + 2b − 2y0 y + x0 x(x0 + x) (x0 − x)2
=
(a + x0 x)(x0 + x) + 2b − 2y0 y . (x0 − x)2
Substituting r, s, t then gives r r r r ss a + t20t2 t20 + t2 + 2b − 2 t3 t03 0 0 0 x(P + P0 ) = 2 r0 r − t2 t2 0
(at20 t2 + r0 r)(r0 t2 + rt20 ) + 2bt4 t40 − 2ss0 tt0 = . (r0 t2 − rt20 )2 The effect of clearing denominators in the rationals a and b appearing as coefficients in the elliptic curve can be absorbed into the constant c1 . It is therefore sufficient to check that the numerator and denominator satisfy the inequality in Equation (7.3).
140
7 Heights
First |numerator| < (c2 |t|2 + c3 |r|)(c4 |t|2 + c5 |r|) +c6 |t|4 + c7 |st|. !" #
(7.4)
(max{|r|,|t|2 })2
The first two terms have c8 (max{|r|, |t|2 })2 + c6 |t|4 c9 H(P )2 . Looking at the third term, we need to show that |st| c10 H(P )2 . Since y 2 = x3 + ax + b, we have (st)2 = r3 t2 + art6 + bt8 . There are two cases to consider. I: |r| |t|2 . In this case |st|2 c11 |r|4 + c12 |r|4 + c13 |r|4 = c14 H(P )4 . II: |r| < |t|2 . In this case |st|2 < c15 |t|8 + c16 |t|8 + c17 |t|8 = c18 H(P )4 . In both cases, |st| < c10 H(P )2 , as required. Therefore |numerator| < c19 H(P )2 , or in logarithmic form log |numerator| < c20 + 2h(P ). The denominator is simpler: |denominator| = |r0 t2 − rt20 |2
2 < c21 |t|2 + c22 |r| < c23 H(P )2 , so log |denominator| < c24 + 2h(P ). Proof of Theorem 5.11 Assuming Theorem 7.6. Let Q = {Q1 , . . . , Qs } denote a fixed set of coset representatives for 2E(Q) in E(Q). By Theorem 7.6, it is enough to prove the following: There is a constant R = R(E, Q) with the property that every point P ∈ E(Q) can be expressed as an integral
7.2 Mordell’s Theorem
141
combination of the Qi , i = 1, . . . , s and those Q ∈ E(Q) with h(Q) < R (finite in number by Lemma 7.7(2)). Let P be a rational point on E, and write (for some i0 , i1 , · · · ∈ {1, . . . , s}) P = P0 = Qi0 + 2P1 P1 = Qi1 + 2P2 .. . Pn = Qin + 2Pn+1 . The duplication formula Equation (7.1) says that 4h(Pn+1 ) − c1 < h(2Pn+1 )
(7.5)
for some c1 = c1 (E) > 0. On the other hand, Lemma 7.7(1) shows that h(2Pn+1 ) = h(Pn − Qin ) < 2h(Pn ) + c2
(7.6)
for some c2 = c2 (E, Q). Combining Equation (7.5) and Equation (7.6) gives 1 h(Pn ) + c3 2 for some c3 = c3 (E, Q). Iterating this gives 1 1 h(Pn−1 ) + c3 + c3 h(Pn+1 ) < 2 2 1 1 = 2 h(Pn−1 ) + c3 1 + 2 2 .. . 1 1 1 1 < n+1 h(P0 ) + c3 1 + + 2 + · · · + n . 2 2 2 2 h(Pn+1 ) <
As n → ∞, for fixed P0 , 1 2n+1
h(P0 ) → 0 and c3
1 1 1 1 + + 2 + ··· + n 2 2 2
−→ 2c3 .
(7.7)
Now P = Qi0 + 2P1 , P1 = Qi1 + 2P2 and so on gives P = Qi0 + 2(Qi1 + 2P2 ) = Qi0 + 2Qi1 + 22 P2 = Qi0 + 2Qi1 + 22 Qi2 + 23 P3 .. . so P is being written as an integer combination of elements of Q and a point whose height is uniformly bounded as n → ∞ by Equation (7.7). 1 Take R = (2 + 10 )c3 , a constant depending on E and Q. We have shown that any rational point P can be written as an integral combination of the points of Q and a point with height bounded by R.
142
7 Heights
7.3 The Weak Mordell Theorem: Congruent Number Curve We will now give a proof of Theorem 7.6 for the congruent number curve y 2 = x3 − n2 x, where n > 0 denotes an integer. The proof uses a homomorphism from E(Q) to a quotient group of the group of nonzero rationals and we begin my introducing this group. Let Q denote Q∗ /Q∗2 , which is the quotient of the group of nonzero rationals by the subgroup of all nonzero squares. The representatives for this group can be taken to be all nonzero integers r which are not divisible by the square of a prime. We will write r for the coset containing r. Notice that the identity of the group is 1 and the element −1 is an element of order 2 in Q. In this section, the point (0, 0) will play a distinguished role and will be denoted T = (0, 0). Lemma 7.8. Define a map φ1 : E(Q) → Q by φ1 (0) = 1 φ1 (T ) = −1 φ1 ((x, y)) = x otherwise. Then φ1 is a group homomorphism. This is a remarkable claim. If you try to prove it simply using the addition formula it can be difficult to dig out, and might even start to look impossible. We will use a simple trick already encountered to make it come out quite smoothly. The reason φ in the definition carries the suffix 1 is because we will define two other similar maps shortly. Proof of Lemma 7.8. Let P1 and P2 denote rational points with P1 + P2 = P3 . We wish to deduce that φ1 (P3 ) = φ1 (P1 )φ1 (P2 ). There are a number of special cases to be considered before we can deal with the general situation. The only nontrivial special case which requires any work arises when one of P1 or P2 is the 2-torsion point T = (0, 0). Say we add P = (x, y) to T , where x = 0. The image of the sum under φ1 is (y/x)2 − x = (y 2 − x3 )/x2 = −n2 x = −x = φ1 (P )φ1 (T ), hence the result is true in this special case. An almost identical proof gives the case where P3 = T = (0, 0). Recall Section 5.3, where we converted the geometric addition on an elliptic curve into explicit formulas. The group law on an elliptic curve tells us that
7.3 The Weak Mordell Theorem: Congruent Number Curve
143
the points P1 , P2 and −P3 lie on the same straight line. Writing P1 + P2 = P3 with Pi = (xi , yi ), we need to show that x1 x2 x3 is a rational square. From the above, we may assume each of x1 , x2 , and x3 are nonzero rational numbers. Let the line containing the points P1 , P2 and −P3 be written y = αx + β, for rationals α and