Solutions to Introduction to Analytic Number Theory Tom M. Apostol Greg Hurst [email protected] Preface This is a solution manual for Tom Apostol’s Introduction to Analytic Number Theory. Since graduating, I decided to work out all solutions to keep my mind sharp and act as a refresher. There are many problems in this book that are challenging and worth doing on your own, so I recommend referring to this manual as a last resort. The most up to date manual can be found at gregoryhurst.com. Please report any errors you may find. Clearly some problems are harder than others so I used the following markers to indicate exercises I found hard: denotes problems I found particularly challenging. (+) denotes what I considered to be the most challenging problem of the chapter. (++) Furthermore I kept track of the exercises from which I learned the most, which are naturally the ones I recommend the most: Exercise 1.24 Exercise 1.30 Exercise 2.8 Exercise 3.12 Exercise 4.24 Exercise 4.25 Exercise 4.26 Exercise 4.27 Exercise 4.28 Exercise 4.29 Exercise 4.30 Exercise 5.13 Exercise 5.18 Exercise 5.19 Exercise 5.20 Exercise 6.18 Exercise 10.8 Exercise 10.9 Exercise 10.13 Exercise 11.15 Exercise 11.16 Exercise 12.12 Exercise 12.19 Exercise 13.10 Exercise 14.5 ii Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 1 The Fundamental Theorem of Arithmetic . . . . . . . . . . . . . . . . . . . 1 2 Arithmetical Functions and Dirichlet Multiplication . . . . . . . . . . . . 11 3 Averages of Arithmetical Functions . . . . . . . . . . . . . . . . . . . . . . 32 4 Some Elementary Theorems on the Distribution of Prime Numbers . . 51 5 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6 Finite Abelian Groups and Their Characters . . . . . . . . . . . . . . . . . 84 7 Dirichlet’s Theorem on Primes in Arithmetic Progressions . . . . . . . . 92 8 Periodic Arithmetic Functions and Gauss Sums . . . . . . . . . . . . . . . 96 9 Quadratic Residues and the Quadratic Reciprocity Law . . . . . . . . . . 107 10 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 11 Dirichlet Series and Euler Products . . . . . . . . . . . . . . . . . . . . . . 126 12 The Functions ζ(s) and L(s,χ) . . . . . . . . . . . . . . . . . . . . . . . . . . 141 13 Analytic Proof of the Prime Number Theorem . . . . . . . . . . . . . . . 160 14 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 iii Chapter 1 The Fundamental Theorem of Arithmetic In there exercises lower case latin letters a,b,c,...,x,y,z represent integers. Prove each of the statements in Exercises 1 through 6. Exercise 1.1. If (a,b) = 1 and if c | a and d | b, then (c,d) = 1. Proof. Since a and b are relatively prime, there are integers x and y such that ax+by = 1. Also because c | a and d | b, we have a = cn and b = dm for some integers n and m. Thus c(nx)+d(my) = 1, which implies (c,d) = 1. Exercise 1.2. If (a,b) = (a,c) = 1, then (a,bc) = 1. Proof. Since a is relatively prime to both b and c, there are integers x ,x ,y ,y such that 1 2 1 2 ax +by = 1 and ax +cy = 1. 1 1 2 2 Multiplying gives (ax +by )(ax +cy ) = 1 =⇒ a2x x +acx y +abx y +bcy y = 1 1 1 2 2 1 2 1 2 2 1 1 2 =⇒ a(ax x +cx y +bx y )+(bc)(y y ) = 1 1 2 1 2 2 1 1 2 =⇒ (a,bc) = 1. Exercise 1.3. If (a,b) = 1, then (an,bk) = 1 for all n ≥ 1,k ≥ 1. Proof. Suppose p | an and p | bk for some prime p. Then p | a and p | b, as p is prime. This implies p | (a,b), a contradiction. Exercise 1.4. If (a,b) = 1, then (a+b,a−b) is either 1 or 2. Proof. Since (a,b) = 1, there are integers x and y such that ax+by = 1. Then (a+b)(x+y)+(a−b)(x−y) = (ax+bx+ay +by)+(ax−bx−ay +by) = 2ax+2by = 2. Thus (a+b,a−b) ≤ 2, i.e. (a+b,a−b) is either 1 or 2. 1 2 Chapter 1 Solutions Exercise 1.5. If (a,b) = 1, then (a+b,a2 −ab+b2) is either 1 or 3. Proof. Let g = (a+b,a2−ab+b2). Since (a+b)2−(a2−ab+b2) = 3ab, we have g | 3ab. This means each prime factor p of g must divide 3, a, or b. However without loss of generality , if p | a then p | (a+b)−a = b. This contradicts (a,b) = 1, and so p (cid:45) ab. Therefore (g,ab) = 1, which means g | 3, i.e. g = 1 or g = 3. Exercise 1.6. If (a,b) = 1 and if d | a+b, then (a,d) = (b,d) = 1. Proof. Let g = (a,d), which means g | a and g | d. Additionally, d | a+b implies b = nd−a for some integer n, and so g | b. Thus g | (a,b), which forces g = 1. The same argument shows (b,d) = 1. Exercise 1.7. A rational number a/b with (a,b) = 1 is called a reduced fraction. If the sum of two reduced fractions in an integer, say (a/b)+(c/d) = n, prove that |b| = |d|. Proof. Since n = (ad+bc)/(bd), both b and d divide ad+bc. This means b | ad and d | bc, but since (a,b) = (c,d) = 1 we must have b | d and d | b. Therefore |b| = |d|. Exercise 1.8. An integer is called squarefree if it is not divisible by the square of any prime. Prove that for every n ≥ 1 there exist uniquely determined a > 0 and b > 0 such that n = a2b, where b is squarefree. Proof. Suppose n ≥ 1 and n = pα1···pαk. Define 1 k a = p(cid:98)α1/2(cid:99)···p(cid:98)αk/2(cid:99) and b = pα1 mod2···pαk mod2. 1 k 1 k We then have n = a2b since α = 2(cid:98)α /2(cid:99)+(α mod 2). Moreover, b is square free. i i i Now suppose n = c2d for c > 0 and d > 0. Then a2b = c2d which means a2 | c2d. However, d is squarefree so it follows that a2 | c2. Similarly c2 | a2, thus |a2| = |c2|. This forces a = c as they are both positive. Substituting a = c into a2b = c2d shows b = d. Hence this decomposition is unique. Exercise 1.9. For each of the following statements, either give a proof or exhibit a counter example. (a) If b2 | n and a2 | n and a2 ≤ b2, then a | b. (b) If b2 is the largest square divisor of n, then a2 | n implies a | b. Solution. (a) False: Let n = 36, a = 2, and b = 3. (b) If n = pα1···pαk and b2 is the largest square divisor of n, then by Exercise 1.8, 1 k b = p(cid:98)α1/2(cid:99)···p(cid:98)αk/2(cid:99). 1 k If a2 | n, then a = pβ1···pβk, where β ≤ (cid:98)α /2(cid:99). Thus a | b. 1 k i i Exercise 1.10. Given x and y, let m = ax+by, n = cx+dy, where ad−bc = ±1. Prove that (m,n) = (x,y). 3 Proof. Observe m and n are expressed as linear combinations of x and y. This means (x,y) | m and (x,y) | n, which implies (x,y) | (m,n). Treating m = ax+by and n = cx+dy as a system of linear equations, solving gives dm−bn an−cm x = and y = . ad−bc ad−bc Furthermore, since ad−bc = ±1, then x = ±(dm−bn) and y = ±(an−cm). So applying the exact argument from above, we conclude (m,n) | (x,y). This can only happen when |(x,y)| = |(m,n)|, and since gcd’s are positive, (x,y) = (m,n). Exercise 1.11. Prove that n4 +4 is composite if n > 1. Proof. Factoring shows n4 +4 = (n4 +4n2 +4)−4n2 = (n2 +2)2 −(2n)2 = (n2 +2n+2)(n2 −2n+2). Observe for n > 1, both factors are larger than 1 and so n4 +4 is composite. In Exercises 12, 13, and 14, a, b, c, m, n denote positive integers. Exercise 1.12. For each of the following statements, either give a proof or exhibit a counter example. (a) If an | bn then a | b. (b) If nn | mm then n | m. (c) If an | 2bn and n > 1, then a | b. Solution. (a) True: Suppose a = pα1···pαk. Then an | bn implies bn = pnα1···pnαk ·qnβ1···qnβl. This 1 k 1 k 1 l means b = pα1···pαk ·qβ1···qβl, i.e. a | b. 1 k 1 l (b) False: Let n = 8 and m = 12. (c) True: If a is odd then (a,2) = 1 and an | bn, hence (a) implies a | b. Now suppose a = 2sd where s > 0 and d is odd. Since an | 2bn, 2bn = 2nsdnm for some integer m. Thus bn = 2n(s−1)+(n−1)dnm. Since n−1 > 0, 2n(s−1)+(n−1) is not an nth power, which means m must be even. Therefore bn = 2nsdn(m(cid:48))n = an(m(cid:48))n, and so a | b. Exercise 1.13. If (a,b) = 1 and (a/b)m = n, prove that b = 1. If n is not the mth power of a positive integer, prove that n1/m is irrational. 4 Chapter 1 Solutions Proof. If (a/b)m = n, then am/bm −n/1 = 0. Thus by Exercise 1.7, |bm| = 1, and so b = 1. Next suppose n1/m = a/b where (a,b) = 1. Then n = (a/b)m, which we now know implies b = 1. Therefore n = am, i.e. n is an mth power. Exercise 1.14. If (a,b) = 1 and ab = cn, prove that a = xn and b = yn for some x and y. [Hint: Consider d = (a,c).] Proof. Suppose a = pa1···pak and b = qb1···qbl where all p and q are distinct. Then 1 k 1 l i j cn = pa1···pak ·qb1···qbl, 1 k 1 l and so c = pa1/n···pak/n ·qb1/n···qbl/n. 1 k 1 l Since each p and q are distinct, n | a and n | b . Therefore a and b are nth powers. i j i j Exercise 1.15. Prove that every n ≥ 12 is the sum of two composite numbers. Proof. If n is even, then n = 4+(n−4) and n−4 > 2 is even. On the other hand, if n is odd, then n = 9+(n−9) and n−9 > 2 is even. Exercise 1.16. Prove that if 2n −1 is prime, then n is prime. Proof. Suppose n is composite and n = ab for some a > 1 and b > 1. Then 2n −1 = (2a)b −1 = (2a −1)(2a(b−1) +2a(b−2) +···+2a +1). Since both factors are greater than one, 2n −1 must be composite. Exercise 1.17. Prove that if 2n +1 is prime, then n is a power of 2. Proof. Suppose n = 2sd where d is odd and d > 1. Then 2n +1 = (22s)d +1 = (22s +1)(22s(d−1) −22s(d−2) +···+22s·2 −22s +1). Furthermore since d > 1 is odd, (22s(d−1) −22s(d−2))+···+(22s·2 −22s)+1 > 0+···+0+1 = 1. Hence both factors are larger than 1 and so 2n + 1 is composite. Thus if 2n + 1 is prime, then d = 1, i.e. n is a power of 2. Exercise 1.18. If m (cid:54)= n compute the gcd (a2m + 1,a2n + 1) in terms of a. [Hint: Let A = a2n +1 and show that A | (A −2) if m > n.] n n m 5 Solution. Let g = (A ,A ), where m > n and define A = a2k +1. Now m n k A −2 = a2m −1 m = (a2n)2m−n −1 = (a2n +1)(a2n(2m−n−1) −a2n(2m−n−2) +···+a2n −1) = A ·(a2n(2m−n−1) −a2n(2m−n−2) +···+a2n −1), n and hence A | (A − 2). This shows g | A − 2 and g | A , thus by linearity g | 2. If a n m m m is even, then A is odd and hence g = 1. On the other hand, if a is odd, then A is even, k k giving g = 2. Exercise 1.19. The Fibonacci sequence 1,1,2,3,5,8,13,21,34,... is defined by the recur- sion formula a = a + a , with a = a = 1. Prove that (a ,a ) = 1 for each n+1 n n−1 1 2 n n+1 n. Proof. Induct on n. It’s clear (a ,a ) = 1. Let n > 1 and assume (a ,a ) = 1. Then 1 2 n−1 n (a ,a ) = (a ,a +a ) = (a ,a ) = 1. n n+1 n n n−1 n n−1 Exercise 1.20. Let d = (826,1890). Use the Euclidean algorithm to compute d, then express d as a linear combination of 826 and 1890. Solution. Applying the Euclidean algorithm, 1890 = 2·826+238 826 = 3·238+112 238 = 2·112+14 112 = 8·14+0, hence d = 14. Through back substitution, 14 = 238−2·112 = (1890−2·826)−2(826−3·238) = (1890−2·826)−2(826−3·(1890−2·826)) = 7·1890−16·826. Exercise 1.21. The least common multiple (lcm) of two integers a and b is denoted by [a,b] or by aMb, and is defined as follows. [a,b] = |ab|/(a,b) if a (cid:54)= 0 and b (cid:54)= 0 [a,b] = 0 if a = 0 or b = 0. Prove that the lcm has the following properties: (a) If a = (cid:81)∞ pai and b = (cid:81)∞ pbi then [a,b] = (cid:81)∞ pci, where c = max{a ,b }. i=1 i i=1 i i=1 i i i i (b) (aDb)Mc = (aMc)D(bMc). (c) (aMb)Dc = (aDc)M(bDc). (D and M are distributive with respect to each other.) 6 Chapter 1 Solutions Proof. (a) If c = max{a ,b } and m = min{a ,b }, then by definition [a,b] = (cid:81)∞ pai+bi−mi. Now i i i i i i i=1 i it’s easy to see a +b = c +m , and hence [a,b] = (cid:81)∞ pci. i i i i i=1 i For the next parts assume a = (cid:81)∞ pai, b = (cid:81)∞ pbi, and c = (cid:81)∞ pci. i=1 i i=1 i i=1 i (b) We have (cid:104)(cid:89) (cid:89) (cid:105) (cid:89) [(a,b),c] = pmin{ai,bi}, pci = pmax{min{ai,bi},ci} i i i and (cid:16)(cid:89) (cid:89) (cid:17) (cid:89) ([a,c],[b,c]) = pmax{ai,ci}, pmax{bi,ci} = pmin{max{ai,ci},max{bi,ci}}. i i i To show these exponents are equal, we will compare the two in a table. ordering max{min{a ,b },c } min{max{a ,c },max{b ,c }} i i i i i i i a ≥ b ≥ c b b i i i i i a ≥ c ≥ b b b i i i i i b ≥ a ≥ c b b i i i i i b ≥ c ≥ a a a i i i i i c ≥ a ≥ b b b i i i i i c ≥ b ≥ a a a i i i i i This shows max{min{a ,b },c } = min{max{a ,c },max{b ,c }} and the result follows. i i i i i i i (c) We have (cid:16)(cid:89) (cid:89) (cid:17) (cid:89) ([a,b],c) = pmax{ai,bi}, pci = pmin{max{ai,bi},ci} i i i and (cid:104)(cid:89) (cid:89) (cid:105) (cid:89) [(a,c),(b,c)] = pmin{ai,ci}, pmin{bi,ci} = pmax{min{ai,ci},min{bi,ci}}. i i i To show these exponents are equal, we will compare the two in a table. ordering min{max{a ,b },c } max{min{a ,c },min{b ,c }} i i i i i i i a ≥ b ≥ c c c i i i i i a ≥ c ≥ b b b i i i i i b ≥ a ≥ c c c i i i i i b ≥ c ≥ a b b i i i i i c ≥ a ≥ b b b i i i i i c ≥ b ≥ a b b i i i i i This shows min{max{a ,b },c } = max{min{a ,c },min{b ,c }} and the result follows. i i i i i i i Exercise 1.22. Prove that (a,b) = (a+b,[a,b]). Lemma 1.22. If (c,d) = 1, then (c+d,cd) = 1. Proof of Lemma. Suppose p | c + d and p | cd for some prime p. Then without loss of generality p | c, and so p | (c+d)−c = d. This means p | (c,d), a contradiction. 7 Proof of Exercise. Note by Theorem 1.4 (c) if c > 0, then (ac,bc) = c(a,b). Now if g = (a,b), then a = gn and b = gm for some integers n and m. By Lemma 1.22, (a+b,[a,b]) = (a+b,|ab|/g) = (g(n+m),±gnm) = g(n+m,nm) = g. Exercise 1.23. The sum of two positive integers is 5264 and their least common multiple is 200340. Determine the two integers. Solution. We have a+b = 5264 and [a,b] = 200340. So by Exercise 1.22, 200340 = ab/(5264,200340) = ab/28, and therefore a+b = 5264 and ab = 5609520. Assuming a < b, solving the system gives a = 1484 and b = 3780. Exercise 1.24. Prove the following multiplicative property of the gcd: (++) (cid:18) (cid:19)(cid:18) (cid:19) a k b h (ah,bk) = (a,b)(h,k) , , . (a,b) (h,k) (a,b) (h,k) In particular this shows that (ah,bk) = (a,k)(b,h) whenever (a,b) = (h,k) = 1. Lemma 1.24. Ifn, m, andg > 0areintegers, theng = (n,m)ifandonlyif(n/g,m/g) = 1. Proof of Lemma. By Theorem 1.4 (c), (n,m) = g ⇐⇒ (g(n/g),g(m/g)) = g ⇐⇒ g(n/g,m/g) = g ⇐⇒ (n/g,m/g) = 1. Proof of Exercise. Let a = a/(a,b),b = b/(a,b),h = h/(h,k),k = k/(h,k). Then apply- 1 1 1 1 ing Lemma 1.24, (cid:18) (cid:19)(cid:18) (cid:19) a k b h (ah,bk) = (a,b)(h,k) , , (a,b) (h,k) (a,b) (h,k) ⇐⇒ (a h ,b k ) = (a ,k )(b ,h ) 1 1 1 1 1 1 1 1 (cid:18) (cid:19) a h b k 1 1 1 1 ⇐⇒ , = 1. (a ,k )(b ,h ) (b ,h )(a ,k ) 1 1 1 1 1 1 1 1 Now define α = a1 ,γ = h1 ,β = b1 ,δ = k1 . Then by Lemma 1.24, (a1,k1) (b1,h1) (b1,h1) (a1,k1) (α,δ) = 1 and (γ,β) = 1.