WIXLIB

Solutions toIntroduction to Analytic Number TheoryTom M. ApostolGreg Hurstghurst588@gmail.com

PrefaceThis is a solution manual for Tom Apostol’s Introduction to Analytic Number Theory. Sincegraduating, 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 canbe 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 indicateexercises 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 naturallythe ones I recommend the most:Exercise 1.24Exercise 1.30Exercise 2.8Exercise 3.12Exercise 4.24Exercise 4.25Exercise 4.26Exercise 4.27Exercise 4.28Exercise 4.29Exercise 4.30Exercise 5.13Exercise 5.18Exercise 5.19Exercise 5.20Exercise 6.18Exercise 10.8Exercise 10.9Exercise 10.13Exercise 11.15Exercise 11.16Exercise 12.12Exercise 12.19Exercise 13.10Exercise 14.5ii

ContentsPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ii1The Fundamental Theorem of Arithmetic . . . . . . . . . . . . . . . . . . .12Arithmetical Functions and Dirichlet Multiplication . . . . . . . . . . . .113Averages of Arithmetical Functions . . . . . . . . . . . . . . . . . . . . . .324Some Elementary Theorems on the Distribution of Prime Numbers . .515Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .736Finite Abelian Groups and Their Characters . . . . . . . . . . . . . . . . .847Dirichlet’s Theorem on Primes in Arithmetic Progressions . . . . . . . .928Periodic Arithmetic Functions and Gauss Sums . . . . . . . . . . . . . . .969Quadratic Residues and the Quadratic Reciprocity Law . . . . . . . . . . 10710 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11611 Dirichlet Series and Euler Products . . . . . . . . . . . . . . . . . . . . . . 12612 The Functions ζ(s) and L(s, χ) . . . . . . . . . . . . . . . . . . . . . . . . . . 14113 Analytic Proof of the Prime Number Theorem . . . . . . . . . . . . . . . 16014 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185iii

Chapter 1The Fundamental Theorem ofArithmeticIn 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. Thusc(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 x1 , x2 , y1 , y2 such thatax1 by1 1 and ax2 cy2 1.Multiplying gives(ax1 by1 )(ax2 cy2 ) 1 a2 x1 x2 acx1 y2 abx2 y1 bcy1 y2 1 a(ax1 x2 cx1 y2 bx2 y1 ) (bc)(y1 y2 ) 1 (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. Thisimplies 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

2Chapter 1 SolutionsExercise 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. Thismeans each prime factor p of g must divide 3, a, or b. However without loss of generality , ifp a then p (a b) a b. This contradicts (a, b) 1, and so p - 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 afor some integer n, and so g b. Thus g (a, b), which forces g 1. The same argumentshows (b, d) 1.Exercise 1.7. A rational number a/b with (a, b) 1 is called a reduced fraction. If the sumof 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 anyprime. Prove that for every n 1 there exist uniquely determined a 0 and b 0 suchthat n a2 b, where b is squarefree.Proof. Suppose n 1 and n pα1 1 · · · pαk k . Definebα1 /2ca p1bαk /2cand b pα1 1· · · pkmod 2· · · pαk kmod 2.We then have n a2 b since αi 2 bαi /2c (αi mod 2). Moreover, b is square free.Now suppose n c2 d for c 0 and d 0. Then a2 b c2 d which means a2 c2 d.However, d is squarefree so it follows that a2 c2 . Similarly c2 a2 , thus a2 c2 . Thisforces a c as they are both positive. Substituting a c into a2 b c2 d shows b d. Hencethis decomposition is unique.Exercise 1.9. For each of the following statements, either give a proof or exhibit a counterexample.(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 1 · · · pαk k and b2 is the largest square divisor of n, then by Exercise 1.8,bα1 /2cb p1bαk /2c· · · pk.If a2 n, then a pβ1 1 · · · pβkk , where βi bαi /2c. Thus a b.Exercise 1.10. Given x and y, let m ax by, n cx dy, where ad bc 1.Prove that (m, n) (x, y).

3Proof. 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 givesx dm bnad bcand y an cm.ad bcFurthermore, since ad bc 1, then x (dm bn) and y (an cm). So applyingthe 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 showsn4 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 counterexample.(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.k1(a) True: Suppose a pα1 1 · · · pαk k . Then an bn implies bn pnα· · · pnα· q1nβ1 · · · qlnβl . This1kmeans b pα1 1 · · · pαk k · q1β1 · · · qlβl , i.e. a b.(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 2s d where s 0 and d is odd. Since an 2bn ,2bn 2ns dn mfor some integer m. Thusbn 2n(s 1) (n 1) dn m.Since n 1 0, 2n(s 1) (n 1) is not an nth power, which means m must be even. Thereforebn 2ns dn (m0 )n an (m0 )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.

4Chapter 1 SolutionsProof. 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 impliesb 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 y n for some x and y.[Hint : Consider d (a, c).]Proof. Suppose a pa11 · · · pakk and b q1b1 · · · qlbl where all pi and qj are distinct. Thencn pa11 · · · pakk · q1b1 · · · qlbl ,and soa /nc p1 1a /n· · · pk kb /n· q11b /n· · · ql l .Since each pi and qj are distinct, n ai and n bj . Therefore a and b are nth powers.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 isodd, 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. Then2n 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 2s d where d is odd and d 1. Thensss (d 1)2n 1 (22 )d 1 (22 1)(22 22s (d 2)s ·2 · · · 22s 22 1).Furthermore since d 1 is odd,s (d 1)(22s (d 2) 22s ·2) · · · (22s 22 ) 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.mnExercise 1.18. If m 6 n compute the gcd (a2 1, a2 1) in terms of a. [Hint : LetnAn a2 1 and show that An (Am 2) if m n.]

5kSolution. Let g (Am , An ), where m n and define Ak a2 1. NowmA m 2 a2 1n (a2 )2 (a2nm n 1n (2m n 1) 1)(a2n (2m n 1) An · (a2n (2m n 2) a2n (2m n 2) a2n · · · a2 1)n · · · a2 1),and hence An (Am 2). This shows g Am 2 and g Am , thus by linearity g 2. If ais even, then Ak is odd and hence g 1. On the other hand, if a is odd, then Ak is even,giving g 2.Exercise 1.19. The Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . is defined by the recursion formula an 1 an an 1 , with a1 a2 1. Prove that (an , an 1 ) 1 for eachn.Proof. Induct on n. It’s clear (a1 , a2 ) 1. Let n 1 and assume (an 1 , an ) 1. Then(an , an 1 ) (an , an an 1 ) (an , an 1 ) 1.Exercise 1.20. Let d (826, 1890). Use the Euclidean algorithm to compute d, thenexpress d as a linear combination of 826 and 1890.Solution. Applying the Euclidean algorithm,1890 2 · 826 238826 3 · 238 112238 2 · 112 14112 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 aM b, and is defined as follows.[a, b] ab /(a, b) if a 6 0 and b 6 0[a, b] 0 if a 0 or b 0.Prove thatQthe lcm has the Qfollowing properties: Q aibici(a) If a i 1 pi and b i 1 pi then [a, b] i 1 pi , where ci max{ai , bi }.(b) (aDb)M c (aM c)D(bM c).(c) (aM b)Dc (aDc)M (bDc).(D and M are distributive with respect to each other.)

6Chapter 1 SolutionsProof.Qai bi mi(a) If ci max{ai , bi } and mi min{ai , bi }, then byQdefinition [a, b] . Nowi 1 pi ciit’s easy to see ai bi ci mi , and hence [a, b] i 1 pi .QQ biQ ciaiFor the next parts assume a i 1 pi , b i 1 pi , and c i 1 pi .(b) We havehYY i Y max{min{a ,b },c }min{ai ,bi }i ii[(a, b), c] pi,pci i piand([a, c], [b, c]) Ymax{ai ,ci }pi,Ymax{bi ,ci }pi Ymin{max{ai ,ci },max{bi ,ci }}pi.To show these exponents are equal, we will compare the two in a table.orderingai b i c iai c i b ib i ai c ib i c i aic i ai b ic i b i aimax{min{ai , bi }, ci }bibibiaibiaimin{max{ai , ci }, max{bi , ci }}bibibiaibiaiThis shows max{min{ai , bi }, ci } min{max{ai , ci }, max{bi , ci }} and the result follows.(c) We have YY Y min{max{a ,b },c }max{ai ,bi }i iipi([a, b], c) ,pci i piand[(a, c), (b, c)] hYmin{ai ,ci }pi,Ymin{bi ,ci }pii Ymax{min{ai ,ci },min{bi ,ci }}pi.To show these exponents are equal, we will compare the two in a table.orderingai b i c iai c i b ib i ai c ib i c i aic i ai b ic i b i aimin{max{ai , bi }, ci }cibicibibibimax{min{ai , ci }, min{bi , ci }}cibicibibibiThis shows min{max{ai , bi }, ci } max{min{ai , ci }, min{bi , ci }} and the result follows.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 ofgenerality p c, and so p (c d) c d. This means p (c, d), a contradiction.