Solucionario, Teoría de Números, Tom Apostol PDF

Preview

Summary

Solucionario del libro de teoría de números, Tom Apostol...

Description

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

ii

Exercise 14.5

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 x1 , x2 , y1 , y2 such that ax1 + 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. 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 ∤ 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 = a2 b, where b is squarefree. Proof. Suppose n ≥ 1 and n = p1α1 · · · pαk k . Define ⌊α1 /2⌋

a = p1

⌊αk /2⌋

and b = p1α1

· · · pk

mod 2

· · · pαkk

mod 2

.

We then have n = a2 b since αi = 2 ⌊αi /2⌋ + (α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 |. This forces a = c as they are both positive. Substituting a = c into a2 b = c2 d 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 = p1α1 · · · pαk k and b2 is the largest square divisor of n, then by Exercise 1.8, ⌊α1 /2⌋

b = p1

⌊αk /2⌋

· · · pk

.

If a2 | n, then a = p1β1 · · · pkβk , where βi ≤ ⌊αi /2⌋. 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).

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 x=

dm − bn ad − bc

and y =

an − cm . 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. k 1 (a) True: Suppose a = p1α1 · · · pαkk . Then an | bn implies bn = p1nα1 · · · pnα · · · qlnβl . This · q nβ 1 k βl β1 αk α1 means b = p1 · · · pk · q 1 · · · ql , 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 m for some integer m. Thus bn = 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. Therefore bn = 2ns dn (m′ )n = an (m′ )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 = y n for some x and y . [Hint : Consider d = (a, c).] Proof. Suppose a = p1a1 · · · pakk and b = q1b1 · · · qlbl where all pi and qj are distinct. Then cn = pa11 · · · pakk · q1b1 · · · qlbl , and so a /n

c = p11

a /n

· · · pkk

b /n

· q 11

b /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 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 = 2s d where d is odd and d > 1. Then s

s

2n + 1 = (22 )d + 1 = (22 + 1)(22

s (d−1)

− 22

s (d−2)

+ · · · + 22

s ·2

s

− 22 + 1).

Furthermore since d > 1 is odd, (22

s (d−1)

− 22

s (d−2)

) + · · · + (22

s ·2

s

− 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. m

n

Exercise 1.18. If m 6= n compute the gcd (a2 + 1, a2 + 1) in terms of a. [Hint : Let n An = a2 + 1 and show that An | (Am − 2) if m > n.]

5 k

Solution. Let g = (Am , An ), where m > n and define Ak = a2 + 1. Now m

Am − 2 = a2 − 1 n

= (a2 )2 = (a

2n

m−n

−1

+ 1)(a2

= An · (a2

n (2m−n −1)

n (2m−n −1)

− a2

− a2

n (2m−n −2)

n (2m−n −2)

n

+ · · · + a2 − 1) n

+ · · · + a2 − 1),

and hence An | (Am − 2). This shows g | Am − 2 and g | Am , thus by linearity g | 2. If a is 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 each n. 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, 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 6= 0 and b 6= 0 [a, b] = 0 if a = 0 or b = 0. Prove that the lcm has the Q following properties: Q Q∞ ai ∞ ∞ p i and b = i=1 pibi then [a, b] = i=1 pci i , where ci = max{ai , bi }. (a) If a = i=1 (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. Q∞ ai+bi−mi . Now (a) If ci = max{ai , bi } and mi = min{ai , bi }, then by definition [a, b] = i=1 pi Q∞ ci it’s easy to see ai + bi = ci + mi , and hence [a, b] = i=1 pi . Q∞ Q∞ Q∞ ai p i , b = i=1 pibi , and c = i=1 pici . For the next parts assume a = i=1 (b) We have hY Y ci Y min{ai ,bi } max {min{ai ,bi },ci } , pi i = pi [(a, b), c] = pi and

([a, c], [b, c]) =

Y

max{ai ,ci }

pi

Y

,

max{bi ,ci }

pi



=

Y

min{max {ai ,ci },max {bi ,ci }}

pi

.

To show these exponents are equal, we will compare the two in a table. ordering max{min{ai , bi }, ci } a i ≥ bi ≥ c i bi a i ≥ c i ≥ bi bi bi ≥ a i ≥ c i bi bi ≥ c i ≥ a i ai c i ≥ a i ≥ bi bi c i ≥ bi ≥ a i ai

min{max{ai , ci }, max{bi , ci }} bi bi bi ai bi ai

This shows max{min{ai , bi }, ci } = min{max{ai , ci }, max{bi , ci }} and the result follows. (c) We have Y Y c  Y min{max{a ,b },c } max{ai ,bi } i i i pi ([a, b], c) = pi , pi i =

and

[(a, c), (b, c)] =

hY

min{ai ,ci }

pi

,

Y

min{bi ,ci }

pi

i

=

Y

max {min{ai ,ci },min{bi ,ci }}

pi

.

To show these exponents are equal, we will compare the two in a table. ordering min{max{ai , bi }, ci } a i ≥ bi ≥ c i ci a i ≥ c i ≥ bi bi bi ≥ a i ≥ c i ci bi ≥ c i ≥ a i bi c i ≥ a i ≥ bi bi c i ≥ bi ≥ a i bi

max{min{ai , ci }, min{bi , ci }} ci bi ci bi bi bi

This 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 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 200 340. Determine the two integers. Solution. We have a + b = 5264 and [a, b] = 200 340. So by Exercise 1.22, 200 340 = ab/(5264, 200 340) = ab/28, and therefore a + b = 5264 and ab = 5 609 520. Assuming a < b, solving the system gives a = 1484 and b = 3780. Exercise 1.24.(++) Prove the following multiplicative property of the gcd:    b k h a . , , (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. If n, m, and g > 0 are integers, then g = (n, m) if and only if (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 a1 = a/(a, b), b1 = b/(a, b), h1 = h/(h, k), k1 = k/(h, k). Then applying Lemma 1.24,    k h a b , , (ah, bk) = (a, b)(h, k) (a, b) (h, k) (a, b) (h, k) ⇐⇒ (a1 h1 , b1 k1 ) = (a1 , k1 )(b1 , h1 )   k1 h1 b1 a1 = 1. , ⇐⇒ (a1 , k1 ) (b1 , h1 ) (b1 , h1 ) (a1 , k1 ) Now define α =

a1 ,γ (a1 ,k1 )

=

h1 ,β (b1 ,h1 )

=

b1 ,δ (b1 ,h1 )

= (a1k,k1 1 ) . Then by Lemma 1.24,

(α, δ) = 1 and (γ, β) = 1.

8

Chapter 1 Solutions

Additionally, note α=

a d1 (a, b)

and β =

b d2 (a, b)

for some d1 and d2 , so Lemma 1.24 shows (α, β) = 1 and similarly (γ, δ) = 1. This means αγ and βδ can share no positive divisors other than 1, that is (αγ, βδ) = 1. Prove each of the following statements in Exercises 25 through 28. All integers are positive. Exercise 1.25. If (a, b) = 1 there exist x > 0 and y > 0 such that ax − by = 1. Proof. If a = 1 then take x = b + 1 and y = 1, so we can assume a > 1 and b > 1. Since (a, b) = 1, there are x and y such that ax+by = 1. If x > 0 and y < 0, we’re done. Otherwise we make a few quick observations. • x= 6 0 and y = 6 0 because a = 6 1 and b = 6 1. • x and y can’t both be negative since this implies ax + by < 0. • x and y can’t both be positive since this implies ax + by > 1. So at this stage we must conclude x < 0 and y > 0. Define xn = x + bn and yn = y − an for some integer n. Then axn + byn = ax + abn + by − abn = ax + by = 1, so choosing n large enough to force xn > 0 and yn < 0 gives the result. Exercise 1.26. If (a, b) = 1 and xa = y b then x = nb and y = na for some n. [Hint : Use Exercises 25 and 13.] Proof. Suppose (a, b) = 1. Then by Exercise 1.25, there are positive c and d such that ac − bd = 1. We then have xad = y bd = y ac−1 . Raising both sides to the power 1/a, yields xd = y c ·y −1/a, or in other words y 1/a = y c /xd ∈ Q. By Exercise 1.13, this implies y is an ath power and so y = na for some positive n. Finally xa = y b = nab = (nb )a, hence raising both sides to the power 1/a gives x = nb . Exercise 1.27.(+) (a) If (a, b) = 1 then for every n > ab there exist positive x and y such that n = ax + by . (b) If (a, b) = 1 there are no positive x and y such that ab = ax + by.

9 Proof. (a) Let n > ab and consider the sequence S = {n − ib | 1 ≤ i ≤ a}. Each member of S will have a different remainder when divided by a, since (a, b) = 1 and adding n simplify shifts the conjugacy classes. Since |S| = a, we deduce there is a unique element in S that is divisible by a. That is to say there is n − yb ∈ S such that n − yb = ax. Since 1 ≤ y ≤ a we have ax = n − yb > 0, which means x > 0. (b) Suppose ab = ax + by, where x > 0 and y > 0. Then a(b − x) = by which means a | by, but since (a, b) = 1 we have a | y. If y = az, dividing through by a gives b = x + bz. Thus b(1 − z) = x, which means 1 > z as x > 0. This is a contradiction since y > 0 implies z > 0. Thus ab = ax + by has no solution for x > 0 and y > 0. Exercise 1.28.(+) If a > 1 then (am − 1, an − 1) = a(m,n) − 1. Proof. If m = n, the result is immediate. Suppose m > n and m = qn + r with 0 ≤ r < n. Then am − 1 = aqn+r − 1 = ar (aqn − 1) + (ar − 1) = ar (aq−1 + · · · + a + 1)(an − 1) + (ar − 1). Since 0 ≤ r < n, we have 0 ≤ ar −1 < an −1. By the Euclidean algorithm, if we continue this process, we’ll arrive at the gcd. But this process is also performing the Euclidean algorithm on the exponents, starting with m and n. From here we see (am − 1, an − 1) = a(m,n) − 1. Exercise 1.29. Given n > 0, let S be a set whose elements are positive integers ≤ 2n such that if a and b are in S and a 6= b then a ∤ b. What is the maximum number of integers that S can contain? [Hint : S can contain at most one of the integers 1, 2, 22 , 23 , . . ., at most one of 3, 3 · 2, 3 · 22 , . . ., etc.] Solution. Define Sm = {m, 2 · m, 22 · m, . . .} for 1 ...