[PDF] Number Theory Lecture Notes - Vahagn Aslanyan

950_6numbertheory.pdf

Number Theory

Lecture Notes

Vahagn Aslanyan

1 1 www.math.cmu.edu/~vahagn/

Contents

1 Divisibility 3

1.1 Greatest common divisors . . . . . . . . . . . . . . . . . . . .

3

1.2 Linear Diophantine equations . . . . . . . . . . . . . . . . . .

4

1.3 Primes and irreducibles . . . . . . . . . . . . . . . . . . . . . .

4

1.4 The fundamental theorem of arithmetic . . . . . . . . . . . . .

5

1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2 Multiplicative functions 7

2.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2 The Möbius inversion formula . . . . . . . . . . . . . . . . . .

8

2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3 Modular arithmetic 11

3.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.2 Wilson"s theorem . . . . . . . . . . . . . . . . . . . . . . . . .

12

3.3 Fermat"s little theorem . . . . . . . . . . . . . . . . . . . . . .

12

3.4 The Chinese Remainder Theorem . . . . . . . . . . . . . . . .

12

3.5 Euler"s totient function . . . . . . . . . . . . . . . . . . . . . .

13

3.6 Euler"s theorem . . . . . . . . . . . . . . . . . . . . . . . . . .

14

3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4 Primitive roots 17

4.1 The order of an element . . . . . . . . . . . . . . . . . . . . .

17

4.2 Primitive roots modulo a prime . . . . . . . . . . . . . . . . .

18

4.3 Primitive roots modulo prime powers . . . . . . . . . . . . . .

19

4.4 The structure of(Z/2kZ)×. . . . . . . . . . . . . . . . . . . .20

4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

5 Quadratic residues 23

5.1 The Legendre symbol and Euler"s criterion . . . . . . . . . . .

23

5.2 Gauss"s lemma . . . . . . . . . . . . . . . . . . . . . . . . . .

24
iii ivCONTENTS

5.3 The quadratic reciprocity law . . . . . . . . . . . . . . . . . .

25

5.4 Composite moduli . . . . . . . . . . . . . . . . . . . . . . . . .

26

5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

6 Representation of integers by some quadratic forms 29

6.1 Sums of two squares . . . . . . . . . . . . . . . . . . . . . . .

29

6.2 Sums of four squares . . . . . . . . . . . . . . . . . . . . . . .

30

6.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

7 Diophantine equations 33

7.1 The Pythagorean equation . . . . . . . . . . . . . . . . . . . .

33

7.2 A special case of Fermat"s last theorem . . . . . . . . . . . . .

34

7.3 Rational points on quadratic curves . . . . . . . . . . . . . . .

35

7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

8 Continued fractions 39

8.1 Finite continued fractions . . . . . . . . . . . . . . . . . . . .

39

8.2 Representation of rational numbers by continued fractions . .

41

8.3 Infinite continued fractions . . . . . . . . . . . . . . . . . . . .

41

8.4 Periodic continued fractions . . . . . . . . . . . . . . . . . . .

44

8.5 Pell"s equation . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

9 Diophantine approximations 51

9.1 Dirichlet"s theorem . . . . . . . . . . . . . . . . . . . . . . . .

51

9.2 Better approximations . . . . . . . . . . . . . . . . . . . . . .

52

9.3 Transcendental numbers and Liouville"s theorem . . . . . . . .

53

9.4 Transcendence ofe. . . . . . . . . . . . . . . . . . . . . . . .55

9.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

10 Quadratic number fields 59

10.1 Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

10.2 Gaussian integers . . . . . . . . . . . . . . . . . . . . . . . . .

61

10.3 Fermat"s little theorem for Gaussian integers . . . . . . . . . .

63

10.4 Using Gaussian integers to solve Diophantine equations . . . .

63

10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

11 Chebyshev"s theorem 65

11.1 Basic estimates . . . . . . . . . . . . . . . . . . . . . . . . . .

65

11.2 Proof of Chebyshev"s theorem . . . . . . . . . . . . . . . . . .

67

11.3 On the prime number theorem . . . . . . . . . . . . . . . . . .

68

11.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

CONTENTSv

Bibliography 70

Preface

Dominus Illuminatio Mea.

Psalm 27:1

These are lecture notes for the Number Theory course taught at CMU in Fall 2017 and Fall 2018. I used several texts when preparing these notes. In particular, most of the material can be found in [Bak12, Gre17, HW80]. The books [Bak12, HW80] go way beyond the material of these notes and the reader is referred to those books for more advanced topics. Please email me if you notice any mistakes or typos.

Synopsis

Divisibility in the ring of integers, primes, the fundamental theorem of arith- metic. Multiplicative functions, the Möbius inversion formula. Modular arithmetic, Wilson"s theorem, Fermat"s little theorem, Euler"s theorem, the Chinese Remainder Theorem. Primitive roots. Quadratic residues, Gauss"s law of quadratic reciprocity. Fermat"s theorem on sums of two squares, La- grange"s theorem on sums of four squares. Some classical Diophantine equa- tions. Continued fractions, Pell"s equation. Diophantine approximations, Liouville numbers, algebraic and transcendental numbers. Quadratic num- ber fields, Gaussian integers. Chebyshev"s theorem, a weak version of the prime number theorem.

Notations

•The sets of natural numbers1(positive integers), integers, rationals, re- als and complex numbers will be denoted byN,Z,Q,R,Crespectively.1 The standard convention is that0?Nbut in this course it is more convenient to assume0is not a natural number. 1

2CONTENTS

•For a field (or ring)Kthe ring of polynomials in indeterminateXwith coefficients fromKis denoted byK[X], whileK(X)is the field of rational functions. •The degree of a polynomialf(X)is denoted bydeg(f). •The greatest common divisor of two integersaandbis denoted by gcd(a,b). •For a real numberxits integral part, denoted[x], is the greatest integer which does not exceedx. The fractional part ofxis defined as{x}= x-[x]. More notations will be introduced throughout the text.

Chapter 1

Divisibility

1.1 Greatest common divisors

Definition 1.1.For two integersaandbwitha?= 0we say thatadividesb orbis divisible byaand writea|b, iff there is an integercsuch thatb=ca. Definition 1.2.Thegreatest common divisorof two integersaandb, de- notedgcd(a,b), is defined as a positive numberdwhich dividesaandband is divisible by every common divisor ofaandb. Proposition 1.3.The greatest common divisor of any two numbersaand b, which are not simultaneously zero, exists and is unique. It is the biggest among the common divisors ofaandb. Proof.Denoted:= min{ax+by:x,y?Z, ax+by >0}. We claim that d= gcd(a,b). Ifd?|a,bthen clearlyd?|ax+byfor all integersx,yand henced?|d. Further, ifa=dq+rfor somerwith0≤r < d, then it is easy to see that r=a-dq=ax0+by0for somea0,b0?Z. Now ifr >0then we get a contradiction to minimality ofd. Uniqueness ofdis evident.Lemma 1.4.For any integersa,bthere are integersx,ysuch that gcd(a,b) =ax+by. Proof 1.This follows immediately from the proof of the previous result.Proof 2.(Euclid"s algorithm) Leta=bq0+r0for some0≤r0< b. Ifr0= 0thengcd(a,b) =b. Otherwise letb=q1r0+r1with0≤r1< r0. Now ifr1= 0thengcd(a,b) = 3

4CHAPTER 1. DIVISIBILITY

r

0. Otherwise continue the process and divider0byr1with remainder. In

the(k+ 2)-th step we getrk-1=qk+1rk+rk+1with0≤rk+1< rk. The sequence of non-negative integersriis strictly decreasing so the process must terminate at some point, that is,rk+1= 0for somek. Thenrk= gcd(a,b) and going up from the bottom we see thatrkcan be written as a linear

combination ofaandbwith integer coefficients.Remark1.5.Euclid"s algorithm allows one to compute the numbersxandy

for whichax+by= gcd(a,b). Definition 1.6.Two integers are calledcoprimeorrelatively primeif their greatest common divisor is1.

Corollary 1.7.Ifaandbare coprime anda|bcthena|c.

Proof.There are integersx,ysuch thatax+by= 1. This impliesacx+bcy= c. Nowadivides the left hand side and so it must divide the right hand side as well.1.2 Linear Diophantine equations Theorem 1.8.Leta,b,cbe integers witha,b?= 0. Then the linear equation ax+by=c has an integer solution, that is, a solution(x,y)?Z2, if and only ifd:= gcd(a,b)|c. Given one solution(x0,y0), all solutions are of the formx= x

0+k·bd

, y=y0-k·ad fork?Z. Proof.If the equation has a solution(x0,y0)then obviouslyd|ax0+by0=c. Conversely, ifc=dlthen sinced=am+bnfor some integersm,n, we know that(ml,nl)is a solution. If(x,y)and(x0,y0)are two solutions thena(x-x0) +b(y-y0) = 0. Denoteu=x-x0, v=y0-y. Thenau=bv. Ifa=da?, b=db?then gcd(a?,b?) = 1anda?u=b?vand soa?|v, b?|u. Thereforev=a?k, u=b?k for some integerk. The result follows.1.3 Primes and irreducibles Definition 1.9.An integerp?= 0,±1is calledirreducibleifa|pimplies a=±1ora=±p. A numberp?= 0,±1isprimeif wheneverp|ab, we have p|aorp|b.

1.4. THE FUNDAMENTAL THEOREM OF ARITHMETIC5

Here1and-1are the onlyunitsof the ringZ, that is, integers with a multiplicative inverse inZ. Lemma 1.10.An integerpis prime iff it is irreducible. Proof.Supposepis prime andp=ab. But thenp|ab, hencep|aorp|b. Assume the former holds. On the other handaandbdividep. This shows thatb=±1anda=±p. Now supposepis irreducible andp|ab. Ifp-athengcd(p,a) = 1. Thereforep|b.Note that primes and irreducibles may not coincide in other rings. Lemma 1.11.Every non-zero integer has a prime divisor. Proof.The numbermin{d: 1< d, d|n}is a prime divisor ofn.1.4 The fundamental theorem of arithmetic Theorem 1.12(Fundamental theorem of arithmetic).Every natural number n >1can be factored into a product of (positive) primes in a unique way (up to the order of the factors). Proof.Firs we prove the existence of a factorisation. Take a prime divisorp1 ofnand writen=p1n1. Now, by induction,n1is a product of primes and hence so isn. Now let us prove uniqueness. Supposep1···pk=q1···qswhere allpi andqjare prime. Sincep1divides the right hand side, it must divide one of the factorsqj, sayq1(after reorderingqj"s). However,q1is prime and hence p

1=q1. Thus,p2···pk=q2···qsand we can proceed by induction. This

shows in particular thatk=sand the two collections of primesp1,...,pk andq1,...,qkcoincide up to reordering.Proposition 1.13(Euclid).There are infinitely many primes. Proof.Suppose there are only finitely many primes. Denote those byp1,...,pk. Consider the numberN:=p1...pk+ 1. Ifqis a prime divisor ofN(which

exists!) then it must be different fromp1,...,pkwhich is a contradiction.Proof 2.(Euler) Suppose there are finitely many primes, namelyp1,...,pk.

Thenk?

i=111-p-1i=k ? i=1∞ ? l=0p-li=∞ ? n=11n =∞, which is a contradiction. Note that the second equality follows from the fundamental theorem.

6CHAPTER 1. DIVISIBILITY

1.5 Exercises

1.

Sho wthat

(i) ev eryt woco nsecutivein tegersare relativ elyprime, (ii) e veryt woconsecutiv eo ddin tegersare relativ elyprime. 2.

Find all in tegersxandyfor which84x+ 120y= 24.

3. Let pandqbe prime numbers. Suppose that the polynomialx2-px+q has an integer root. Find all possible values ofpandq. 4. Sho wthat a natura ln umberis divisible b y3iff the sum of its digits is divisible by3. 5.

Pro vethat 4-n2+ 1for any integern.

6.

Sho wthat gcd(am-1,an-1) =agcd(m,n)-1.

7. Sho wthat if for a p ositivein tegernthe number2n-1is prime thenn is prime as well. 8.

Find all in tegersa,bfor whicha2b2|a4+a3b+ab3+b4.

9. Pro vethat for ev eryp ositivein tegernthere arenconsecutive numbers none of which is prime. 10. Sho wthat if for a p ositivein tegernthe number2n+1is prime thenn must be a power of2. 11. Le ta,b,c,n?Nwithgcd(a,b) = 1andab=cn. Prove that botha andbmust ben-th powers of some positive integers. 12. Pro vethat there are infinitely man yprimes of the form 4k+3, k?N. 13. Le ta,bbe positive integers. Show that ifgcd(a,b) = 1thengcd(a+ b,a

2-ab+b2)is either1or3.

14.

Sho wthat if pis an odd prime andgcd(a,b) = 1then

gcd ? a+b,ap+bpa+b? = 1orp.

Chapter 2

Multiplicative functions

2.1 Basics

Definition 2.1.A functionf:N→Cismultiplicativeiff(1) = 1and wheneverm,nare coprime natural numbers, we havef(mn) =f(m)f(n).

Lemma 2.2.Iffis multiplicative andg(n) =?

d|nf(d)thengis also mul- tiplicative. Proof.Ifgcd(m,n) = 1then any divisordofmncan be factored into a productabwitha|mandb|n. The numbersaandbare determined uniquely byd,m,n. Therefore g(mn) =? d|mnf(d) =? a,b:a|m,b|nf(ab) =? a,b:a|m,b|nf(a)f(b) = ? a|mf(a)·? b|nf(b) =g(m)g(n).Example 2.3.Ifτ(n)andσ(n)are respectively the number and the sum of all positive divisors of a natural numbern, then those are multiplicative.

Indeed,τ(n) =?

d|n1andσ(n) =? d|ndand the functionsf(n) = 1and f(n) =nare obviously multipliactive. An important multiplicative function, namely Euler"s totient function, will be introduced in the next chapter.

The following is obvious.

Lemma 2.4.Iffis multiplicative andn=?

ipkiiis the prime factorisation ofnthen f(n) =? if(pkii). 7

8CHAPTER 2. MULTIPLICATIVE FUNCTIONS

Thus, in order to show that two multiplicative functions are identically equal, it suffices to show they agree on prime powers.

2.2 The Möbius inversion formula

Definition 2.5.The Möbius functionμ(n)is defined as

μ(n) =?

? ?0,ifnis divisible by a square, (-1)k,ifnis a product ofkdistinct primes. It is obvious thatμis multiplicative. Hence, by Lemma 2.2, the function

ν(n) =?

d|nμ(d) is multiplicative as well.

Lemma 2.6.

ν(n) =?

? ?0,ifn >1,

1,ifn= 1.

Proof.Since both the left hand side and the right hand side are multiplicative functions, it suffices to establish the equality forn=pkfor primesp. This is left as an exercise.Proposition 2.7(Möbius Inversion Formula).Iff:N→Candg(n) =? d|nf(d)then f(n) =? d|nμ(d)g(n/d). Note that herefdoes not have to be multiplicative.

Proof.We have

? d|nμ(d)g(n/d) =? d|n? d ?|nd

μ(d)f(d?) =?

d ?|n? d|nd ?μ(d)f(d?) = ? d ?|n( ( (f(d?)? d|nd ?μ(d)) ) )=? d ?|nf(d?)ν(n/d?) =f(n).

2.3. EXERCISES9

Proposition 2.8.If

f(n) =? d|nμ(d)g(n/d) theng(n) =? d|nf(d).

Proof.We have

? d|nf(d) =? d|n? d ?|dμ(d?)g(d/d?) =? d ?|n? d:d?|d,d|nμ(d?)g(d/d?) = ? d ?|n? a|nd ?μ(d?)g(a) =? a|n( ( g(a)? d ?|na

μ(d?))

) =? a|ng(a)ν(n/a) =g(n).2.3 Exercises 1.

F ora complex n umbersdenote

σ s(n) :=? d|nds. Prove thatσsis multiplicative. Notice thatσ0=τ, σ1=σ. 2.

If nhaskdistinct prime factors, show that?

d|n|μ(d)|= 2k. 3.

Pro vethat

? d|nμ(d)2?(d)=n?(n). 4.

Pro vethat τ(n)≤2⎷nfor alln?N.

Chapter 3

Modular arithmetic

3.1 Congruences

Definition 3.1.Fora,b,m?Zwithm?= 0it is said thatais congruent to bmodulom, writtena≡bmodm, ifm|b-a. This gives rise to residue classes modm. More precisely for an integera we denote[a]m:={b?Z:a≡bmodm}. ObviouslymZ={mk:k?Z} is an ideal of the ring of integers and[a]m=a+mZis just its coset with a representativea. Then the quotient ringZ/mZconsists of the residue classes modulomand the operations are defined by (a+Z/mZ) + (b+Z/mZ) = (a+b) +Z/mZ, (a+Z/mZ)·(b+Z/mZ) = (ab) +Z/mZ. We will often identifya+mZwith the integeraand by abuse of notation writeZ/mZ={0,1,...,m-1}. Definition 3.2.For a ringRitsmultiplicative groupR×is the set of all invertible elements ofRwhich is a group under multiplication of the ring.

Lemma 3.3.Form?= 0we have

(Z/mZ)×={a+mZ: gcd(a,m) = 1}. Note that heregcd(a,m)does not depend on the choice of the represen- tativea. Proof.Clearly,a+mZis invertible iffak≡1 modmfor some integerk. Such akexists iffgcd(a,m) = 1.Corollary 3.4.Ifpis prime then every non-zero element inZ/pZis invert- ible. Hence it is a field and is normally denoted byFp. 11

12CHAPTER 3. MODULAR ARITHMETIC

3.2 Wilson"s theorem

Theorem 3.5.Ifpis prime then(p-1)!≡ -1 modp.

Proof.Pair each element ofF×p={1,2,...,p-1}with its inverse. Ifa=a-1 thena2≡1 modpand hencea≡ ±1 modp. Thus, ifa?=±1then its inverse is different from itself. The product of all those numbers and their inverses is clearly1modulop. Adding1and-1to the product we get the desired result.3.3 Fermat"s little theorem Theorem 3.6.Ifpis prime andp-athenap-1≡1 modp. Remark3.7.This is equivalent to the following:ap≡amodpfor all integers a. This is a special case of Euler"s theorem that we prove later. The standard proof of Fermat"s little theorem presented in textbooks is actually a special case of the proof of Euler"s theorem. To avoid repetition, we now give a different proof to Fermat"s theorem. Proof.We can assumea >0and we use induction ona. Fora= 1the theorem is obvious. Now since?p k?is divisible bypfor0< k < p, we deduce that (a+ 1)p=p ? k=0? p k? a k≡ap+ 1p≡a+ 1 modp, where the last equality follows from the induction hypothesis.3.4 The Chinese Remainder Theorem Theorem 3.8(Chinese Remainder Theorem).Letai,mi?Z, i= 1,...,n, withmi?= 0andgcd(mi,mj) = 1fori?=j. Then there is an integerxsuch thatx≡aimodmifor alli. This follows immediately from the following result which is also known as the Chinese Remainder Theorem. Theorem 3.9.Letm1,...,mmbe pairwise coprime and denoteM:=?ni=1mi. Then

Z/MZ≂=Z/m1Z× ··· ×Z/mnZ.

3.5. EULER"S TOTIENT FUNCTION13

Proof.Consider the map

ψ:Z/MZ→Z/m1Z× ··· ×Z/mnZ,

ψ:x+MZ?→(x+m1Z,...,x+mnZ).

Observe thatx+MZ=y+MZiffx≡ymodMiffx≡ymodmi,1≤ i≤niffx+miZ=y+miZ,1≤i≤niffψ(x+MZ) =ψ(y+MZ). This shows thatψis well defined and injective. Hence, it is surjective since its domain and range have the same cardinalityM. It is now evident thatψis also an isomorphism.Remark3.10.For the proof of Theorem 3.8 we need only surjectivity ofψ. However, the isomorphism of the rings is an important result and we will use it later. The above proof is not constructive so we give a second proof for Theorem 3.8.

Second proof of Theorem 3.8.DenoteMi:=Mm

iwhereM=m1···mn. It is easy to see thatgcd(Mi,mi) = 1. Hence there are integerskiwithkiMi≡1 modmifor alli. Now take x=n ? i=1a ikiMi.

SinceMi≡0 modmjfori?=j, we deduce thatx≡aimodmi.Remark3.11.Compare this to Lagrange interpolation.

Note that ifxsolves the above system of congruences thenyis also a solution if and only ifx≡ymodM.

3.5 Euler"s totient function

Definition 3.12(Euler"s function).Form >0define?(m) = #{k: 1≤ k≤m,gcd(k,m) = 1}.

The following result follows from Lemma 3.3.

Proposition 3.13.The order of the group(Z/mZ)×is?(m).

Lemma 3.14.Euler"s function?is multiplicative. Hence ifn=pk11···pkllis the prime factorisation ofnthen

?(n) =? ipki-1 i(pi-1).

14CHAPTER 3. MODULAR ARITHMETIC

Proof.Theorem 3.9 implies that ifgcd(m,n) = 1then

(Z/mnZ)×≂=(Z/mZ)××(Z/nZ)×, and the result follows. For the second part of the theorem notice that ifpis prime andk >0 then among the numbers1,2,...,pkall multiples ofpand only those are not coprime topk. There arepk-1many such numbers. Therefore?(pk) = p k-pk-1.Proposition 3.15. ? d|n?(d) =n. Proof 1.For a divisordofndenoteAd:={a: 1≤a≤n: gcd(n,a) =d}. Then{1,...,n}is the disjoint union of(Ad)d|nand|Ad|=?(n/d).Proof 2.Since?is multiplicative,? d|n?(d)is also multiplicative. So it suffices to establish the equality forn=pkwherepis a prime. In this case ? d|n?(d) =k ? i=0?(pi) = 1 + (p-1) + (p2-p) +···+ (pk-pk-1) =pk.3.6 Euler"s theorem Theorem 3.16(Euler).Ifgcd(a,m) = 1thena?(m)≡1 modm. Proof 1.Denotek:=?(m)and letm1,...,mkbe areduced residue system modulom, that is,gcd(mi,m) = 1for alliandmi?≡mjmodmfori?=j.

In other words,(Z/mZ)×={m1,...,mk}.

Observe thatam1,...,amkis again a reduced residue system modmand hence it is a permutation ofm1,...,mkmodm. Therefore ? im i≡? iam i=ak? im i.

Sincegcd(?

imi,m) = 1, we can deduce thatak≡1 modm.Proof 2.Consider the multiplicative group(Z/mZ)×and its subgroup(a)

generated bya. If the latter has order (cardinality)nthenan= 1. By Lagrange"s theoremndivides the order of the group(Z/mZ)×which is?(m).

Thus,a?(m)= 1in(Z/mZ)×and we are done.Corollary 3.17(Fermat"s little theorem).Ifpis prime andp-athen

a p-1≡1 modp.

Proof.Whenpis prime,?(p) =p-1.

3.7. EXERCISES15

3.7 Exercises

1. Find a p ositivein tegerxsuch thatx≡2 mod 4,2x≡3 mod 9,7x≡

1 mod 11.

2. Supp osea28+28bis prime for some positive integersaandb >1. Prove that2|bor29|a. 3.

Le tn≥6be composite. Show thatn|(n-1)!.

4.

F ora comp ositenshow that?(n)≤n-⎷n.

5. Le tp >2be a prime number withp≡3 mod 4. Show that ifp|a2+b2 for some integersaandbthenp|aandp|b. 6.

Find all in tegersx,ysuch that15x2-7y2= 9.

Chapter 4

Primitive roots

4.1 The order of an element

Definition 4.1.For integersa,m?= 0withgcd(a,m) = 1theorderofa modmis its order in the multiplicative group(Z/mZ)×, that is, ord m(a) = min{γ?N:aγ≡1 modm}. Lemma 4.2.Ifan≡1 modmthenordm(a)|n. In particularordm(a)| ?(m). Proof.Denotek:= ordm(a)and letn≡lmodkwith0≤l < k. Then a l≡1 modmand by minimality ofkwe must havel= 0. The second part of the lemma follows from the first part and Euler"s

theorem (or from Lagrange"s theorem directly).Definition 4.3.Ifordm(a) =?(m)thenais called a primitive root modulo

m. In other words, a primitive root is a generator of the multiplicative group (Z/mZ)×. So there is a primitive root modmif and only if(Z/mZ)×is cyclic. We are going to describe all integers that have a primitive root. More generally, we will prove a structure theorem about the multiplicative group (Z/mZ)×. But now we recall two classical results from the theory of finite groups. Lemma 4.4.IfGis a group anda,b?Gwithab=baandord(a) = k,ord(b) =landgcd(k,l) = 1thenord(ab) =lk. 17

18CHAPTER 4. PRIMITIVE ROOTS

Proof.Letord(ab) =m. Since(ab)kl= (ak)l(bl)k= 1, we havem|kl. On the other hand(ab)m= 1, hence1 = (ab)ml=aml. This impliesk|mland sok|m. Similarly,l|mandkl|m.Lemma 4.5.LetGbe a group anda?Gbe an element of orderm. Then for every integerkthe order ofakis equal tomgcd(m,k). Proof.Letord(ak) =:l. Thenakl= 1and som|kl. Now ifd:= gcd(m,k) thenm=dm?, k=dk?withgcd(m?,k?) = 1. Som?|k?landm?|l. Thusmd |l. On the other hand(ak)m/d=amk?= 1.4.2 Primitive roots modulo a prime Letpbe a prime number. SinceFp=Z/pZis a field, every polynomial equationf(x) = 0hast at mostdeg(f)solutions inFpwheref(X)?Fp[X]\ {0}. Alternatively, we could say the congruencef(x)≡0 modphas at mostdeg(f)integer solutions incongruent modpwheref(X)?Z[X]andp does not divide all coefficients off. Lemma 4.6.Ford|p-1the polynomialXd-1has exactlydroots inFp. Proof.Sinced|p-1there is a polynomialg(X)?Fp[X]such that X p-1-1 = (Xd-1)g(X). Obviously,deg(g) =p-1-dand henceg(X)has at mostp-1-droots. However,Xp-1-1has exactlyp-1roots and thereforeXd-1has at least p-1-(p-1-d) =droots. On the other hand, it cannot have more than

droots and therefore it has exactlydroots.Lemma 4.7.Ifp,qare primes andqk|p-1for somek≥1, then there is

a?Fpwithordp(a) =qk. Proof.By the above lemma the equationxqk-1 = 0has exactlyqksolutions inFp. Suppose none of them has orderqk. This means that for eacha?Fp withaqk= 1we haveordp(a)|qk-1. Thereforeais a root ofXqk-1-1. But

this polynomial has onlyqk-1roots which is a contradiction.Theorem 4.8.For every primepthere is a primitive root modp. Equiva-

lently,F×pis cyclic. Proof.Letp-1 =qk11···qkssbe the prime factorisation ofp-1and let a i?F×pbe of orderqkii. Theng=a1···ashas orderp-1.

4.3. PRIMITIVE ROOTS MODULO PRIME POWERS19

Remark4.9.This proof actually shows that every finite subgroup of the multiplicative group of a field is cyclic. Proof 2.For each divisord|p-1letAd:={a?Fp: ordp(a) =d}and ψ(d) :=|Ad|. Clearly,(Ad)d|p-1is a partition ofF×p. Therefore ? d|p-1ψ(d) =p-1. Now supposeAd?=∅and leta?Ad. Thenordp(ak) =dgcd(d,k)for eachk. In particular,ordp(ak) =diffgcd(d,k) = 1, hence the setAd∩{1,a,...,ad-1} has?(d)elements. Thusψ(d)≥?(d). We claim that the equality holds. Indeed, letb?F×pwithordp(b) =d. Thenbis a root of the polynomial X d-1. However, the latter has exactlydroots and those are1,a,...,ad-1. Hencebis actually a power ofkwhich proves our claim. Thus, for everydeitherψ(d) = 0orψ(d) =?(d). Since ? d|p-1ψ(d) =p-1 =? d|p-1?(d),

ψ(d) =?(d)for everyd|p-1. In particularψ(p-1) =?(p-1)>0.Corollary 4.10.There are exactly?(p-1)primitive roots modulop.

4.3 Primitive roots modulo prime powers

Theorem 4.11.Ifpis an odd prime then there is a primitive root modpk for every positive integerk. Proof.The proof is split into two steps presented in the following claims. Claim.Ifgis a primitive root modpthen eithergorg+pmust be a primitive root modp2. Letgbe a primitive root modp. Denotek:= ordp2(g). We havek| ?(p2) =p(p-1)andgk≡1 modp2. Sinceordp(g) =p-1,kmust be divisible byp-1. Thusk=p(p-1)ork=p-1. In the former casegis a primitive root modulop. So assumek=p-1, that is,gp-1≡1 modp2. Then (g+p)p-1≡gp-1+p(p-1)gp-2≡1 +p(p-1)gp-2?≡1 modp2. Asg+pis a primitive root modp, by the above argument it must be primitive modp2.

20CHAPTER 4. PRIMITIVE ROOTS

Claim.Ifgis a primitive root modp2then it is primitive modpnfor all n≥2. We prove by induction onnthatordpn(g) =pn-1(p-1). It is true for n= 2. Now assume it is true fornand prove it forn+ 1. Letl:= ordpn+1(g)so thatl|pn(p-1). On the other hand, since ord pn(g) =pn-1(p-1), eitherl=pn(p-1)orl=pn-1(p-1). In the former case we are done, so assume the latter is the case. Nowgpn-2(p-1)≡1 modpn-1and thereforegpn-2(p-1)= 1 +pn-1tfor some integert. Furthermore,p-tas otherwise we would havegpn-2(p-1)≡1 modpnwhich contradicts the induction hypothesis. Thus, g pn-1(p-1)= (1 +pn-1t)p≡1 +pnt?≡1 modpn+1.

Note that here we used the fact that

?p i?is divisible bypfor0< i < pand thatpn+1|p2n-1forn≥2. For the last term, where the binomial coefficient

is1, we actually havepn+1|pp(n-1)forp >2andn≥2.There is no primitive root mod2kfork >2according to the following

result the proof of which is left to the reader as an exercise. Actually, to show that(Z/2kZ)×is not cyclic it suffices to notice that it has a non-cyclic subgroup, namely(Z/8Z)×. Lemma 4.12.Fork >2and oddawe havea2k-2≡1 mod 2k. Theorem 4.13.There is a primitive root modmiffm= 2,4,pk,2pkwhere pis an odd prime andkis a positive integer. Proof.Clearly,1is primitive mod2and-1is primitive mod4. Now letm=pk11···pkssbe the prime factorisation ofm. Then (Z/mZ)×≂=(Z/pk11Z)×× ··· ×(Z/pkssZ)×, which is cyclic iffmis not divisible by8and the numbers?(pk11),...,?(pkss)

are pairwise coprime. Since?(pk)is even for an oddp, the result follows.14.4 The structure of(Z/2kZ)×

Now we give a characterisation of the group(Z/2kZ)×fork >2which will allow us to understand the structure of any group(Z/mZ)×using the Chinese

Remainder Theorem.1

We can also show directly that ifgis a primitive root modpkthen eitherg(if it is odd) org+pk(ifgis even) is a primitive root mod2pk.

4.4. THE STRUCTURE OF(Z/2KZ)×21

Notation.For a positive integerndenote byCnthe cyclic group of ordern (which is unique up to isomorphism). Proposition 4.14.Fork >2we have(Z/2kZ)×≂=C2×C2k-2. Definition 4.15.For a prime numberp, thep-adic valuationof a non-zero integern, denotedvp(n), is the biggest integerγfor whichpγdividesn. Proof of Proposition 4.14.We claim thatord2k(5) = 2k-2. By Lemma 4.12 it suffices to prove that52k-3?≡1 mod 2k. We have 5

2k-3= (1 + 22)2k-3= 1 + 2k-1+2

k-3? i=2? 2k-3 i? 2 2i.

So it is enough to show that2k|?2k-3

i=2? 2k-3 i?22i. For this we need to prove thatv2??2k-3 i??≥k-2ifori≥2. Observe that form < n ?n m? =nm ? n-1 m-1? hence v

2??2k-3

i?? ≥k-3-v2(i)≥k-2i, as clearlyv2(i)< i. This proves our claim. Now let(5) ={1,5,52,...,52k-2-1}be the subgroup of(Z/2kZ)×gener- ated by5. We claim that none of those elements is congruent to-1mod 2 k. Indeed, suppose5l≡ -1 mod 2kfor somel? {0,1,...,2k-2-1}. Then 5

2l≡1 mod 2kand so2k-2|2l. Obviouslyl?= 0as otherwise we would

have1≡ -1 mod 2kwhich is wrong. Thus,l= 2k-3. However, we saw above that 5

2k-3≡1 + 2k-1?≡ -1 mod 2k.

Thus, the subgroup{±1} ·(5)≤(Z/2kZ)×has the same cardinality as the whole group(Z/2kZ)×. Hence(Z/2kZ)×={±1}·(5).So the intersection of the subgroups(5)and{±1}is the trivial subgroup{1}and their product is equal to the whole group(Z/2kZ)×. Therefore

(Z/2kZ)×≂={±1} ×(5).Example 4.16.Let us decompose the group(Z/360Z)×into a direct product

of cyclic groups. By the Chinese Remainder Theorem we have (Z/360Z)×≂=(Z/23Z)××(Z/32Z)××(Z/5Z)×≂=C2×C2×C6×C4.

22CHAPTER 4. PRIMITIVE ROOTS

4.5 Exercises

1.

Let n >0be an integer. Prove thatn|?(2n-1).

2. Sho wt hatif g1andg2are primitive roots modulo an odd primep, then g

1g2is not a primitive root modulop.

3. Find all p ositivein tegersnfor which the congruencea25≡amodn holds for all integersa. 4. Sho wthat a primitiv ero otmo dulop2is also a primitive root modulo p, wherepis an odd prime. 5.

Pro vethat for k >2anda?Z, ifais odd, then

a

2k-2≡1 mod 2k.

6. Sho wthat if mhas a primitive root then it has exactly?(?(m))of them. 7. Let pbe an odd prime. Prove that there is a number1< g < pwhich is a primitive root modulopnfor every positive integern.

Chapter 5

Quadratic residues

5.1 The Legendre symbol and Euler"s crite-

rion Throughout this chapterpis going to be an odd prime unless explicitly stated otherwise. Definition 5.1.An integera?Z(or its residue class modp) withp-ais aquadratic residuemodpiff there isx?Zsuch thatx2≡1 modp, and a quadratic non-residueotherwise. In other words, quadratic residues are the non-zero squares in the field F

×p.

Lemma 5.2.There are exactlyp-12

quadratic residues andp-12 non-residues.

Proof.InFpx2=y2iffx=±y. Thus12,22,...,?p-12

?

2are all quadratic

residues.Definition 5.3(Legendre symbol).Fora?Zwe define ? ap ? =? ??? ? ??1,ifais a quadratic residue modp, -1,ifais a quadratic non-residue modp,

0,ifp|a.

Proposition 5.4(Euler"s criterion).Ifp-athenap-12

≡?ap ?modp. Proof.By Fermat"s little theorem, all quadratic residues are roots of the polynomialXp-12 -1inFp. There are exactlyp-12 quadratic residues and the polynomial has at most (in fact, exactly) p-12 roots, hence quadratic residues 23

24CHAPTER 5. QUADRATIC RESIDUES

are all the roots of the above polynomial, that is, ifais a quadratic non- residue thenap-12 ?= 1inFp. However, we know thatap-1= 1and sinceFpis a field,ap-12 =±1. Thus, ifais a quadratic non-residue thenap-12 =-1.Corollary 5.5.-1is a quadratic residue modpiffp≡1 mod 4. Lemma 5.6.The Legendre symbol has the following properties. •Ifa≡bmodpthen?ap ?=?bp ?, • ?a2p ?= 1, • ?abp ?=?ap ?? bp ?. Proof.The first two are evident and the third one follows from Euler"s cri- terion.Remark5.7.The third property states that the product of two quadratic residues is a quadratic residue, the product of a quadratic residue and a non- residue is a non-residue, and the product of two quadratic non-residues is a quadratic residue. These could be deduced directly from definitions. Indeed, the first two statements are obvious, while the third one follows from the first two and the pigeonhole principle.

5.2 Gauss"s lemma

Proposition 5.8(Gauss"s Lemma).LetI?F×pbe such thatF×pis the disjoint union ofIand-I. Then fora?F×pwe have?ap ?= (-1)twhere t= #{i?I:ai? -I}. Proof.LetI+:={i?I:ai?I}andI-:={i?I:ai? -I}. ThenIis the disjoint union ofI+andI-. Now we show thatIis also the disjoint union ofaI+and-aI-. First, ifai=-ajfor somei?I+,j?I-theni=-j?I∩ -Iwhich is a contradiction. Further,|aI+|=|I+|and| -aI-|=|I-|therefore|aI+? -aI-|=|I+|+|I-|=|I|. By definitionaI+?-aI-?Iand soaI+?-aI-=I by the pigeonhole principle. Thus, ? i?Ii=? i?I+ai·? i?I-(-ai) = (-1)t·ap-12 ·? i?Ii and the result follows.

5.3. THE QUADRATIC RECIPROCITY LAW25

Note that in applications one always takesI={1,2,...,p-12 }. In partic- ular, it follows immediately from Gauss"s lemma that?-1p ?= (-1)p-12 giving a second proof of this result. Now we give a slightly more sophisticated application.

Proposition 5.9.

?2p ?= (-1)p2-18 , that is,2is a quadratic residue modp iffp≡ ±1 mod 8. Proof.We need to find the numbertof all elementsi? {1,...,p-12 }for which2i? {p+12 ,...,p-1}. Ifp≡1 mod 4thenp-14 < i≤p-12 and so t=p-14 . This is even iffp≡1 mod 8. Ifp≡ -1 mod 4thenp+14 ≤i≤p-12 andt=p+14 . This is even iffp≡ -1 mod 8.5.3 The quadratic reciprocity law We will now formulate and prove one of the most prominent theorems in ele- mentary number theory established by Gauss, known as the law of quadratic reciprocity. Theorem 5.10(Quadratic Reciprocity Law).For distinct odd primesp,q ?pq ?? qp ? = (-1)(p-1)(q-1)4 .

Proof.Consider the rectangle

E:=? (x,y)?Z2: 0< x Denote E 1:=? (x,y)?E:qx-py <-p2 ? , E 2:=? (x,y)?E:-p2 < qx-py <0? , E 3:=? (x,y)?E: 0< qx-py 1,...,E4.

26CHAPTER 5. QUADRATIC RESIDUES

By Gauss"s lemma we know that

?qp ?= (-1)twhere t= #? x: 0< x Givenxas above, there is a uniquea??-p2 ,p2 ?withqx≡amodp. Furthermore, there is a unique integerysuch thata=qx-py. Moreover, if-p2 < a <0theny=qx-ap ??0,q2 ?(since it is an integer). Therefore t= #E2=t2and?qp ?= (-1)t2.

Similarly,?pq

?= (-1)t3. Thus, to prove the theorem we need to show that(p-1)(q-1)4 -(t2+t3) is even. But this number is equal to#E-#E2-#E3=t1+t4. Observe that the map(x,y)?→?p+12 -x,q+12 -y?is a bijection fromE1ontoE4.

Hencet1=t4andt1+t4is indeed even.The law of quadratic reciprocity, along with the results on the quadratic

nature of-1and2, gives an algorithm for determining whether a given number is a quadratic residue modulo a prime. Example 5.11.Is-6a quadratic residue modulop= 113?

We have?-6p

?=?-1p ?? 2p ?? 3p ?.

Sincep≡1 mod 4,?-1p

?= 1. Also,p≡1 mod 8and so?2p ?= 1.

By the reciprocity law

?3113 ? = (-1)(3-1)(113-1)4 ?1133 ? =?1133 ? =?23 ? =-1. Thus, ?-6113 ?=-1.

5.4 Composite moduli

So far we have only studied quadratic residues modulo primes. Now we consider the case of composite moduli. We define a quadratic residue modulo a numbermto be an integera which is coprime tomand for which the congruencex2≡amodmhas a solution. 11 Given a description of coprime quadratic residues one can easily get a description of non-coprime quadratic residues as well.

5.5. EXERCISES27

Proposition 5.12.Letm=?

ipkiibe the prime factorisation ofm. Then a numberais a quadratic residue modmiff it is a qaudratic residue modpkiifor eachi. Proof.Letxibe an integer withx2i≡amodpkii. By the Chinese Remainder Theorem there is an integerxsuch thatx≡ximodpkii.Now it is easy to see thatx2≡amodm.Proposition 5.13.Letpbe an odd prime. Ifais a quadratic residue modulo pthen it is a quadratic residue modulopkfor everyk >0. Proof.We induct onk. Assumeais a quadratic residue modpk. This means that for some integersxandbwe have x

2=a+pkb.

Lety:=x+pkzwherezis yet to be determined. We want the congruence y

2≡amodpk+1

to hold. This is equivalent to p k+1|(2xz-b)pk.

Sincegcd(2x,p) = 1, we can findzsuch that2xz≡bmodp.Now let us explore quadratic residues modulo powers of2. All odd num-

bers are quadratic residues modulo2, and quadratic residues modulo4are exactly the numbers of the form4n+ 1. Proposition 5.14.An odd integerais a quadratic residue modulo2kfor k≥3iffa≡1 mod 8. Proof.Ifais a quadratic residue modulo8then it must be1mod8. Now assumea≡1 mod 8and prove by induction thatais a quadratic residue mod2kfork≥3. To this end we replicate the above argument, only in this caseyis taken to be of the forma+ 2k-1b. We leave the details to the reader.5.5 Exercises 1. Sho wthat a primitiv ero otmo duloan o ddprime is a quadratic non- residue.

28CHAPTER 5. QUADRATIC RESIDUES

2. Let pbe an odd prime. Prove that the product of quadratic residues modpis≡(-1)p+12 modp. 3. Do est hecongruence x2-20x+ 10≡0 mod 50893have a solution?

Note that50893is prime.

4. Sho wthat th ereare infinitely man yprimes of the form 4k+ 1, k?N. 5. Describ eall primes p(in terms of congruences) for which7is a quadratic residue. 6. Supp osep≡1 mod 4is prime and2p+ 1is prime. Show that2is a primitive root mod2p+ 1. 7. Sho wthat the reare infinitely man yprimes of the form 3k+ 1, k?N.

Chapter 6

Representation of integers by

some quadratic forms

6.1 Sums of two squares

In this section we are going to prove a result of Fermat describing all natural numbers that can be represented as sums of two squares. Proposition 6.1.An odd prime numberpcan be expressed as a sum of two squares if and only ifp≡1 mod 4.

Proof.Ifp=x2+y2then obviouslyp≡1 mod 4.

Now letp≡1 mod 4. Then?-1p

?= 1and hence there is an integeru such thatu2≡ -1 modp. Consider the numbers au+b; 0≤a,b≤[⎷p]. This list contains more thanpelements, hence there area1,a2,b1,b2?[0,⎷p) such that(a1,b1)?= (a2,b2)and a

1u+b1≡a2u+b2modp.

Denotex:=a1-a2, y:=b2-b1. Thenx2+y2?= 0andxu≡ymodp.

Therefore

y

2≡x2u2≡ -x2modp.

Thus,p|x2+y2and0< x2+y2≤2[⎷p]2<2p. Hencex2+y2=p.Theorem 6.2.Let n= 2l·? iprii·? jqsj j 29

30CHAPTER 6. REPRESENTATION OF INTEGERS BY SOME QUADRATIC FORMS

be the prime factorization ofnwherepi≡1 mod 4andqj≡3 mod 4and l,r i,qj≥0. Thenn=x2+y2for some integersxandyiffsjis even for all j.

Proof.First observe that for alla,b,c,d

(a2+b2)(c2+d2) = (ac+bd)2+ (ad-bc)2. Therefore, if allsj"s are even thennis the sum of two squares (note that 2 = 1

2+ 12).

Conversely, supposen=x2+y2andq|nis a prime divisor withq≡3 mod 4withvq(n) =s, that is,qs|nandqs+1-n. We claim thatq|x,y. Indeed, otherwise lety??Zbe such thatyy?≡1 modq. Then since q|x2+y2, we haveq|(xy?)2+ 1, i.e.?-1q ?= 1which contradictsq≡3 mod 4. Thus,q|x,yandx=qx1,y=qy1. Now we deduceqs-2|x21+y22. Ifswere odd, this would lead to a contradiction (after applying the same argument repeatedly).6.2 Sums of four squares Theorem 6.3(Lagrange).Every natural number can be expressed as a sum of four squares.

Proof.Notice that

(x2+y2+z2+w2)(x21+y21+z21+w21) = (xx1+yy1+zz1+ww1)2+ (xy1-yx1+wz1-zw1)2+ (xz1-zx1+wy1-yw1)2+ (xw1-wx1+zy1-yz1)2.(2.1) Thus, it is enough to prove the theorem for prime numbers. Letpbe an odd prime. Consider thep+ 1numbers x

2,-y2-1; 0≤x,y≤p-12

.

If0≤x1,x2≤p-12

andx1?=x2thenx21?≡x22modp. Hence for somexand ywe must havex2≡ -y2-1 modp.

Thus, there are integersx,y??0,p-12

?such thatp|x2+y2+ 1. So mp=x2+y2+1for some positive integermwherem≤1p ?

2?p-12

? 2+ 1? < p. Letlbe the smallest positive integer for which there are integersx,y,z,w such that lp=x2+y2+z2+w2.

6.3. EXERCISES31

Such anlexists and1≤l≤m < p. We will show thatl= 1. Assume for contradiction thatl >1. Iflis even then an even number ofx,y,z,ware odd and, assumingx≡y mod 2andz≡wmod 2, we get l2 p=?x+y2 ?

2+?x-y2

?

2+?z+w2

?

2+?z-w2

? 2 which contradicts minimality ofl.

Thereforelmust be odd. Letx1??-l2

,l2 ?be such thatx≡x1modl.

Definey1,z1,w1similarly. Then

n:=x21+y21+z21+w21≡0 modl. Moreover, asl-pwe must have0< n <4·(l/2)2=l2. Hencen=klwith

0< k < l.

Now (lp)(kl) = (x2+y2+z2+w2)(x21+y21+z21+w21) =A2+B2+C2+D2, whereA,B,C,Dare determined by the identity (2.1). In particular, it is clear thatB,C,D≡0 modl. Furthermore,A=xx1+yy1+zz1+ww1≡ x

2+y2+z2+w2≡0 modl. Thus,

kp=?Al ? 2 +?Bl ? 2 +?Cl ? 2 +?Dl ? 2 which contradicts the minimality ofl.6.3 Exercises 1. Descr ibe(in terms of congruences) all primes pwhich can be expressed asp=x2+ 2y2for somex,y?Z.

Chapter 7

Diophantine equations

Equations of the form

f(x1,...,xn) = 0, wheref(X1,...,Xn)?Z[X1,...,Xn]is a polynomial with integer coeffi- cients, and where we are interested in integer (or rational) solutions, are known as Diophantine equations. We studied linear Diophantine equations in Section 1.2. In this chapter we are going to consider some classical non- linear Diophantine equations. Note that Hilbert"s tenth problem asks to find a general algorithm which, given a Diophantine equation, would decide whether there is an integer solu- tion. It was proven by M. Davis, Y. Matiyasevich, H. Putnam, J. Robinson (the theorem being completed by Matiyasevich in 1970) that such an algo- rithm does not exist.

7.1 The Pythagorean equation

Theorem 7.1.All solutions of the equation

x

2+y2=z2

are of the form(d(a2-b2),2dab,d(a2+b2))or(2dab,d(a2-b2),d(a2+b2)) wherea,b,c,dare arbitrary integers (and all those triples are solutions). Proof.First, ifgcd(x,y) =dthend|zandx=dx?,y=dy?,z=dz?with (x?)2+ (y?)2= (z?)2. Hence, dividing bydwe can assume without loss of generality thatgcd(x,y) = 1which implies thatx,y,zare pairwise coprime. A solution to the Pythagorean equation with this property is known as a primitive solution. 33

34CHAPTER 7. DIOPHANTINE EQUATIONS

Reducing the equation modulo4we see thatzis odd and exactly one of x,yis even. Since the equation is symmetric with respect toxandy, we can assume thatyis even. Furthermore, it suffices to find positive solutions and so we can assumex,y,z >0. Thus, the theorem follows from the following claim. Claim.All primitive positive solutions of the Pythagorean equation withy even are given byx=a2-b2,y= 2ab,z=a2+b2wherea,b?Nwith gcd(a,b) = 1anda > b.

Lety= 2w. We write the equation in the form

w

2=z-x2

·z+x2

.

Sincegcd(z-x2

,z+x2 ) = 1, and the product of two coprime numbers is a square iff each of them is, z-x2 andz+x2 must be squares themselves. Thus, there must be coprime numbersaandbsuch that z-x2 =b2,z+x2 =a2. This yieldsz=a2+b2,x=a2-b2,y= 2ab. Conversely, for anya,bwe have (a2-b2)2+ (2ab)2= (a2+b2)2.We will shortly give another proof of this theorem.

7.2 A special case of Fermat"s last theorem

Fermat"s last theorem states that the equation

x n+yn=zn withn >2does not have any positive integer solutions. This turned out to be an extremely difficult problem solved by A. Wiles in 1995 (after being unsuccessfully attacked by many mathematicians for about 350 years). It is easy to see that in order to prove Fermat last theorem, it is enough to prove it forn= 4and odd prime values ofn. We consider the casen= 4 below. It is also interesting to note that the equation forn= 2has infinitely many solutions while forn >2it does not have any solutions.

7.3. RATIONAL POINTS ON QUADRATIC CURVES35

Theorem 7.2.The equation

x

2+y4=z4(2.1)

has no solutions in positive integers. Proof.Ifgcd(y,z) =dthend2|xand(x/d2)2+ (y/d)4= (z/d)4. So we can assumex,y,zare pairwise coprime. Case 1.First supposeyis even. By Theorem 7.1 there are coprime integers a,bsuch that x=a2-b2, y2= 2ab, z2=a2+b2. Assumeais even andbis odd. From the third equation we deduce thata= 2uv, b=u2-v2for some relatively prime integersu,v. Now (y/2)2=uv(u2-v2)henceu=p2, v=q2, u2-v2=r2for some integers p,q,r(sinceu,v,u2-v2are mutually coprime). Therefore r

2+q4=p4.

Thus, assuming(x,y,z)is a positive solution to (2.1), we found another pos- itive solution(r,q,p)withp < z. Applying the same procedure to this new solution, we will find yet another solution the third coordinate of which is smaller thanp. This can be repeated indefinitely which will yield an infinite strictly decreasing sequence of positive integers which is a contradiction. Case 2.Now supposexis even. Then by Theorem 7.1 there are coprime integersa,bsuch that x= 2ab, y2=a2-b2, z2=a2+b2. Therefore(yz)2+b4=a4anda < z. This leads to a contradiction as above.Remark7.3.The method of the proof, invented by Fermat, is known as the method of infinite descent. Corollary 7.4.The equationx4+y4=z4has no positive integer solutions.

7.3 Rational points on quadratic curves

Letf(X,Y)?Q[X,Y]be a quadratic polynomial with rational coefficients. We will see in this section that we can find all rational solutions of the equation f(x,y) = 0(3.2) provided we know one rational solution(x0,y0).

36CHAPTER 7. DIOPHANTINE EQUATIONSxy

(x0,y0)•(x1,y1)•DenoteC(R) :={(x,y)?R2: f(x,y) = 0}1andC(Q) :=C(R)∩ Q

2. Thus(x0,y0)?C(Q). Now

pick an arbitrary point(x1,y1)?

C(Q)and consider the linelpass-

ing through(x0,y0)and(x1,y1). Its equation is y-y0x-x0=y1-y0x 1-x0 and it has rational slopet=y1-y0x 1-x0.

Conversely, letlbe a line with a

rational slopetpassing through(x0,y0). Its equation is y=t(x-x0) +y0. The linelintersects the quadratic curveCin two points one of which is (x0,y0). Let(x1,y1)?R2be the other point of intersection. It may actually coincide with(x1,y1)iflis tangent toC. The abscissax1is a root of the quadratic polynomialf(X,t(X-x0) +y0). Since one of the roots of this polynomial, namelyx0, is rational, and its coefficients are rational, the second root must be rational as well. Thereforex1is rational and hence y

1=t(x1-x0) +y0is rational too.

Thus, there is a one-to-one correspondence between rational points onC and lines with rational slope passing through(x0,y0). This gives an algorithm for finding all rational solutions of (3.2). We just need to solve the equation f(x,t(x-x0) +y0)forx. Note that sincex0is a root, the rootx1will be given by a rational function oft, that is,x1=r(t)for somer(X)?Q(X). So for each rational value oftthe point(r(t),t(r(t)-x0)+y0)is a solution of (3.2) and all solutions are of that form. In other words we found a rational parametrisation of the quadratic curveC. One says in this case thatCis rational. Example 7.5.Let us find all rational solutions of the equation x

2+y2= 1.

Obviously,(-1,0)is a solution. So consider the liney=t(x+ 1). Solving x

2+t2(x+ 1)2= 1we getx=-1orx=1-t21+t2. Thus, all rational points on1

One says thatC(R)is the set ofR-rational points of the curve given by the equation (3.2)

7.4. EXERCISES37

the unit circle are of the form ?1-t21 +t2,2t1 +t2? , t?Q. This can be used to find all integer solutions of the Pythagorean equation x

2+y2=z2.

As we have seen before, we may assumex,y,zare pairwise coprime. Then since(x/z)2+ (y/z)2= 1, we must have xz =1-t21 +t2,yz =2t1 +t2.

Lett=ba

withgcd(a,b) = 1. Then xz =a2-b2a

2+b2,yz

=2aba 2+b2. Hence x=a2-b2, y= 2ab, z=a2+b2. Remark7.6.Here we implicitly assumed thataandbhave different parities in order to deduce the last qualities from the previous ones. We leave it as an exercise for the reader to prove that when bothaandbare odd,x,yand zcan be written asx= 2mn, y=m2-n2, z=m2+n2for some integers m,nwithgcd(m,n) = 1.

7.4 Exercises

1. Find all in tegersolutions of the equation y2=x3+ 16. 2. Find all pairs (x,y)of positive rational numbers such thatx2+3y2= 1. 3.

Find all in tegersx,yfor whichx4-2y2= 1.

Chapter 8

Continued fractions

8.1 Finite continued fractions

Definition 8.1.Afinite continued fractionis a function[a0,a1,...,aN]of variablesa0,a1,...,aNof the form a 0+1a 1+1a

2+...+1a

N. We calla0,...,aNthepartial quotientsof the continued fraction, and[a0,...,an], n≤

N,is called then-thconvergentto[a0,...,aN].

Lemma 8.2.Define the sequencespnandqnrecursively by •p0=a0, p1=a1a0+ 1, pn=anpn-1+pn-2,2≤n≤N, •q0= 1, q1=a1, qn=anqn-1+qn-2,2≤n≤N.

Then[a0,...,an] =pnq

n. Remark8.3.Note thatpnandqnare functions ofa0,...,anand hence they depend only on these variables. Proof.We induct onn. Forn= 0,1the equality holds obviously. Now [a0,...,an,an+1] =? a

0,...,an-1,an+1a

n+1? =?a n+1a n+1?p n-1+pn-2? a n+1a n+1?q n-1+qn-2 = an+1(anpn-1+pn-2) +pn-1a n+1(anqn-1+qn-2) +qn-1=an+1pn+pn-1a n+1qn+qn-1=pn+1q n+1. 39

40CHAPTER 8. CONTINUED FRACTIONS

In the second equality we used the induction hypothesis and the above re- mark.Lemma 8.4.The following identities hold. •pnqn-1-pn-1qn= (-1)n-1forn >0, •pnqn-2-pn-2qn= (-1)nanforn >1. Proof.For the first identity we use induction onn. p nqn-1-pn-1qn= (anpn-1+pn-2)qn-1-pn-1(anqn-1+qn-2) =-(pn-1qn-2-pn-2qn-1) =-(-1)n-2= (-1)n-1. The second identity follows easily from the first one.Corollary 8.5.The functionspnandqnsatisfy • pnq n-pn-1q n-1=(-1)n-1q n-1qn, • pnq n-pn-2q n-2=(-1)nanq n-2qn. Now we assign numerical values to the quotientsan. We will assume thatan?Zfor allnandan>0whenevern >0. Observe that then gcd(pn,qn) = 1.

Letxn=pnq

nbe then-th convergent. Lemma 8.6.The sequencex2nis strictly increasing andx2n+1is strictly decreasing. Furthermore,x2n< x2m+1for everym,n. Proof.The first part follows immediately from the second identity of Corol- lary 8.5 (note thatqnis positive). For the second part, first botice thatx2n< x2n+1according to the first identity of Corollary 8.5. Ifn≤mthenx2n≤x2m< x2m+1, and ifn≥m

thenx2n< x2n+1≤x2m+1.Thus, if the value of the continued fraction isxthenx2n≤xandx2m+1≥

x, and equality holds only once when the index is equal toN.

8.2. REPRESENTATION OF RATIONAL NUMBERS BY CONTINUED FRACTIONS41

8.2 Representation of rational numbers by con-

tinued fractions Theorem 8.7.Every finite continued fraction represents a rational number and every rational number can be represented by a finite continued fraction. Proof.It is obvious that finite continued fractions represent rational num- bers, since the partial quotients are integers. We show now that every rational number does have such a representation. Letx?Qand denotex0=x. Define the sequencesan,xnbyan= [xn] andxn+1=1x n-an. Continue this process as long asxn?=an. Now we show that the process must terminate, that is,xk=akfor somek.

We use Euclid"s algorithm. Ifx=ab

withgcd(a,b) = 1then write a=a0·b+r0, b=a1·r0+r1, r

0=a2·r1+r2,

···

r

N-2=aN·rN-1+ 0.

We know Euclid"s algorithm terminates. We see thatx0=ab ,x1=br 0,xn= r n-1r

n,2≤n < N.Then obviouslyx= [a0,...,aN].Ifx= [a0,...,aN]then alsox= [a0,...,aN-1,1]and thus the con-

tinued fraction representation is not unique. But these are the only two representations ofxaccording to the following result. Proposition 8.8.Ifx= [a0,...,an] = [b0,...,bm]withan>1,bm>1then m=nandai=bifor everyi. Proof.Note that[a1,...,an]>1andx= [a0,...,an] =a0+1[a1,...,an], thereforea0= [x]. Similarly,b0= [x] =a0and[a1,...,an] = [b1,...,bm]. Now the result follows by induction.8.3 Infinite continued fractions Let(an)n≥0be a sequence of integers withan>0forn >0. Denote x n:= [a0,...,an] =pnq n.

42CHAPTER 8. CONTINUED FRACTIONS

Lemma 8.9.The sequencexnis convergent.

Proof.Our results on finite continued fractions show thatx2nis strictly in- creasing,x2n+1is strictly decreasing andx2n< x2m+1for alln,m. Hence the limits x ?:= limn→∞x2nandx??:= limn→∞x2n+1 exist andx2n< x?≤x??< x2m+1.

Now Corollary 8.5 implies

|x?-x??| ≤ |x2n-x2n+1|=1q

2n+1q2n→0.

Thereforex?=x??=:xandxn→x.Definition 8.10.We define the infinite continued fraction[a0,a1,...]as the

limitxof its convergentsxn= [a0,...,an]. One also writes x=a0+1a 1+1a

2+....

Remark8.11.The proof shows actually that

?????x-pnq n? ????≤ |xn+1-xn|=1q n+1qn<1q 2n. Proposition 8.12.Every irrational number can be represented by an infinite continued fraction. Proof.Letx?R\Qand denoteu0:=x. Define the sequencesan,unby a n= [un], un+1=1u n-an, n≥0. This process does not terminate, i.e.un?=an, since otherwisexwould be rational. We claim thatx= [a0,a1,...]. To this end notice that x= [a0,...,an,un+1] =un+1pn+pn-1u n+1qn+qn-1. Hence x-pnq n=pn-1qn-pnqn-1(un+1qn+qn-1)qn=(-1)n(un+1qn+qn-1)qn→0 asun>1whenevern >0.

8.3. INFINITE CONTINUED FRACTIONS43

The proof of Proposition 8.8 generalises to infinite continued fractions. Proposition 8.13.Two infinite continued fractions are equal if and only if all their corresponding partial quotients are equal. Furthermore, an infinite continued fraction cannot be equal to a finite one. Corollary 8.14.The value of an infinite continued fraction is irrational. Proof.Indeed, if the value is rational then the continued fraction algorithm terminates. This contradicts uniqueness.We sum up the above results in the following theorems. Theorem 8.15.Every real number can be represented by a continued fraction (uniquely for irrational numbers). The continued fraction representation of a number is finite iff it is rational. Theorem 8.16.Ifxis an irrational real number then there are infinitely many rational numbers pq such that ? ????x-pq ? ????<1q 2.

Proof.Takepq

=pnq n.This is known as Dirichlet"s theorem on diophantine approximations. We will give another proof (independent of continued fractions) and establish stronger results in the next chapter. Example 8.17.Let us find the continued fraction representation of⎷2. We have ⎷2 = 1 + ( ⎷2-1),

1⎷2-1=⎷2 + 1 = 2 + (

⎷2-1).

Noticing the repeating pattern we conclude that

⎷2 = [1,2,2,...] = 1 +12 +

12 +....

44CHAPTER 8. CONTINUED FRACTIONS

8.4 Periodic continued fractions

Definition 8.18.A continued fraction[a0,a1,a2,...]is called (ultimately) periodicif there are integersn0≥0andl >0such thatan+l=anfor all n > n

0. Whenn0= 0, it is calledpurely periodic.

A periodic continued fraction is denoted (using the above notation) [a0,...,an0,a n0+1,...,an0+l], and[a n0+1,...,an0+l]is called the purely periodic part. Definition 8.19.Aquadratic irrationalis an irrational root of a quadratic equation with rational coefficients. In other words a complex numberαis a quadratic irrational iff the field extensionQ(α)?Qhas degree2. We will only consider real numbers so by a quadratic irrational we will normally understand a real one. The following is obvious. Lemma 8.20.A real number is a quadratic irrational iff it is of the form a+b⎷d c fora,b,c,d?Zwithd >0non-square andc?= 0. Proposition 8.21.A numberu?Ris a quadratic irrational iff its continued fraction representation is periodic.

Proof.Letu= [a0,...,an,a

n+1,...,an+l]. Ifpmq mis them-th convergent tou andv:= [a n+1,...,an+l]then u=pnv+pn-1q nv+qn-1 and hence it suffices to show thatyis a quadratic irrational.

Observe that

v= [an+1,...,an+l,v] =pv+p?qv+q? for some integersp,p?,q,q?. This shows thatvis a root of a quadratic equa- tion. It is irrational since its continued fraction representation is infinite. Conversely, letube a root of a polynomialaX2+bX+cwitha,b,c?Z withd=b2-4ac >0non-square. Consider the quadratic form f(X,Y) =aX2+bXY+cY2. If pnq nis then-th convergent touthen the substitution

X=pnX?+pn-1Y?, Y=qnX?+qn-1Y?

8.4. PERIODIC CONTINUED FRACTIONS45

takesf(X,Y)into a form f n(X?,Y?) =anX?2+bnX?Y?+cnY?2 where a n=ap2n+bpnqn+cq2n=f(pn,qn), c n=ap2n-1+bpn-1qn-1+cq2n-1=f(pn-1,qn-1) =an-1, b n= 2apnpn-1+ 2cqnqn-1+b(pnqn-1+pn-1qn). It is easy to see thatb2n-4a2nc2n=d. This also follows from the fact that the above transformation has determinantpnqn-1-pn-1qn= (-1)n-1and hence it does not change the discriminant of the form.

Sincef(u,1) = 0, we have

a nq

2n=a?p2nq

2n-u2?

+b?pnq n-u? .

We know that

???u-pnq n? ??<1q

2n<1, hence???u+pnq

n? ??≤ |u|+???pnq n? ??<(2|u|+1).

Therefore|an|q

2n<|a|2|u|+ 1q

2n+|b|1q

2n. Thus,|an|<|a|(2|u|+1)+|b|and the right hand side does not depend onn. So we showed that the sequenceanis bounded, hencecn=an-1is bounded.

Also,b2n= 4a2nc2n+dandbnis bounded as well.

Now letu= [a0,a1,...]andun= [an,an+1,...]be then-th complete quotient ofu. Then u=pnun+1+pn-1q nun+1+qn-1 and f n(un+1,1) =f(pnun+1+pn-1,qnun+1+qn-1) = (qnun+1+qn-1)2·f(u,1) = 0. Thus,un+1is a root of the quadratic polynomialfn(X,1)which has bounded coefficients. Therefore there are only finitely many possibilities forun. Soun0=un0+lfor somen0≥0andl >0. By uniqueness of the

continued fraction representationan=an+lfor alln≥n0.For a quadratic irrationalx=a+b⎷dwherea,b?Qandd?Zis not a

square, itsconjugateis the number¯x:=a-b⎷d. It is the other root of the quadratic polynomial which vanishes atx.

46CHAPTER 8. CONTINUED FRACTIONS

Proposition 8.22.The continued fraction representation of a quadratic ir- rationalxis purely periodic iffx >1and-1<¯x <0. Proof.Assumex >1and-1<¯x <0. Letx= [a0,a1,...]and letxn= [an,an+1,...]be then-th complete quotient. First,a0>0asx >1. Further, we show by induction that-1<¯xn<0.

Sincexn=an+1x

n+1, we have¯xn=an+1¯xn+1. Hence-1<¯xn+1<0by the induction hypothesis. Now-1¯xn+1=an-¯xnand0<-¯xn<1, hencean=?-1¯xn+1?. We know thatxn=xn+lfor somen,l. Hence1¯xn=1¯xn+l.This implies a n-1=an+l-1which shows in its turn thatxn-1=xn-1+l. Repeating this argument we getx0=xland we are done. Conversely, ifx= [a0,a1,...]is purely periodic thena0=al≥1for some l >0. Sox > a0≥1.

Moreover,

x=pnx+pn-1q nx+qn-1 and therefore q nx2+ (qn-1-pn)x-pn-1= 0. The roots of the above quadratic equation arexand¯x, hencex·¯x= - pn-1q n<0. In particular¯x <0asx >0. Recall that even convergents of a continued fraction are less than its value while odd convergents are greater. So ifnis even, thenpn-1q nThereforex·¯x >-xand¯x >-1.Example 8.23.Letd >0be a non-square andx=1⎷d-[⎷d]. Thenx >1

and¯x=1- ⎷d-[⎷d]?(-1,0). Thusxhas a purely periodic continued fraction representation,x= [a

1,...,al]. Since⎷d= [⎷d]+1x

, the continued fraction representation of⎷dis almost purely periodic, i.e. ⎷d= [a0,a

1,...,al]

wherea0= [⎷d].

8.5 Pell"s equation

Letd >0be a non-square positive integer. The equation x

2-dy2= 1(5.1)

8.5. PELL"S EQUATION47

is known as Pell"s equation. We are going to apply the results of the last section to solve Pell"s equation. First, notice that for alldthere is a trivial solution(±1,0). We will first show that for alldthere is a non-trivial solution. Lemma 8.24.The equation(5.1)has a non-trivial solution. Proof.We know that the continued fraction representation of⎷dis "almost" purely periodic, that is, ⎷d= [a0,a

1,...,am].

Denoteθ:= [a

1,...,am]. Letnbe an even multiple ofm. Then

⎷d=θpn+pn-1θq n+qn-1 where pkq kis thek-th convergent to⎷d.

On the other hand,⎷d=a0+1θ

. Substitutingθ=1⎷d-a0in the previous equation we get ⎷d=pn+pn-1(⎷d-a0)q n+qn-1(⎷d-a0).

This yields

q n-a0qn-1=pn-1, pn-a0pn-1=qn-1d and therefore p

2n-1-dq2n-1=-(pnqn-1-pn-1qn) = (-1)n= 1

sincenis even. Thus, for every even multiplenofmthe pair(pn-1,qn-1)is a solution to

Pell"s equation. So there are infinitely many non-trivial solutions.Solutions(x,y)to Pell"s equation are in one-to-one correspondence with

the numbersz:=x+y⎷d. Often we will say thatzis a solution to Pell"s equation. Recalling that the conjugate is defined by¯z=x-y⎷dwe can rewrite (5.1) in the form z·¯z= 1.(5.2) Lemma 8.25.Ifz=x+y⎷dwithz¯z= 1thenz >1iffx >0,y >0. Proof.Ifx >0,y >0thenz > x≥1. Conversely, ifz >1then0<¯z <1, hencex >0,-y <0.

48CHAPTER 8. CONTINUED FRACTIONS

Definition 8.26.The numberz1= min{z?Z[⎷d] :z >1, z¯z= 1}is called thefundamental solutionof the equation (5.2). Proposition 8.27.All solutions of the equation(5.2)are given by±zm1, m? Z.

Proof.Sincez1¯z1= 1,zm1·z

m1= (z1¯z1)m= 1. Now, taking into account thatz-11= ¯z1, it suffices to show that for every solutionzwithz >1there is a positive integermsuch thatz=zm1. Asz1>1there ism >0such thatzm1≤z < zm+11. If the first inequality is strict thenz?:=zz m1satisfies z ?·¯z?= 1and1< z?< z1which contradicts the definition ofz1. This finishes the proof.Remark8.28.The above proposition shows that ifz1=x1+y1⎷dthen all solutions of Pell"s equation are given by x=±(x1+y1⎷d)n+ (x1-y1⎷d)n2 , y=±(x1+y1⎷d)n-(x1-y1⎷d)n2 ⎷d , wherenis a positive integer. Alternatively, ifxn,yn,n >0, are determined from the equationxn+yn= (x1+y1⎷d)nthen all solutions are given by(±xn,±yn). The trivial solutions correspond ton= 0. Remark8.29.In the proof of Lemma 8.24 if we choosen= (m,2), that is,m=nifnis even andm= 2nifnis odd, then(pn-1,qn-1)is the fundamental solution of Pell"s equation. Though we will not prove this, it gives an algorithm for solving the equation. Moreover, all solutions of Pell"s equation are of the form(pn-1,qn-1)wherenis an even multiple ofm.

Example 8.30.Consider the equation

x

2-2y2= 1.

Since ⎷2 = [1,2],(3,2)is the fundamental solution. So all solutions are of the form ?

±(3 + 2⎷2)

n+ (3-2⎷2) n2 ,±(3 + 2⎷2) n-(3-2⎷2) n2 ⎷2 ? .

8.6 Exercises

1. Find the con tinuedfraction represen tationof the n umbers2,-236 ,⎷5,⎷7,1⎷3 .

8.6. EXERCISES49

2.

Ev aluatethe con tinuedfract ion[1,2,3,1,4].

3. Find all in tegersolutions of the follo wingequations: (i)x2-3y2= 1, (ii)x2-6y2= 1. 4. Pro vethat the sum of the first nnatural numbers is a perfect square for infinitely manyn. 5. (i)

Sho wthat x2-7y2=-1has no integer solutions.

(ii) Sho wthat if dis divisible by a prime numberpwithp≡3 mod 4 then the equationx2-dy2=-1has no integer solutions. 6. Le tn?= 0be an integer. Show that ifx2-dy2=nhas an integer solution (dis a non-square) then it has infinitely many integer solutions.

Chapter 9

Diophantine approximations

9.1 Dirichlet"s theorem

Theorem 9.1.Letxbe a real number. For every integerQ >1there are integersp,qwith0< q < Qsuch that|qx-p| ≤1/Q. Proof.Consider the numbers{0x},{x},{2x},...,{(Q-1)x},1.1By the pigeonhole principle, we can choose two of these numbers the distance of which is at most1/Q. Assume first for some0≤i < j < Qwe have |{ix} - {jx}| ≤1/Q. This means |(j-i)x+ ([ix]-[jx])| ≤1/Q and we can chooseq=j-i, p= [ix]-[jx]. If one of those two numbers whose distance is≤1/Qis1then we have

|{ix} -1| ≤1/Qfor some0< i < Qand we chooseq=i, p= [ix] + 1.Corollary 9.2.Ifxis irrational then there are infinitely many fractionsp/q

such that|x-p/q|<1/q2. Proof.For an arbitraryQletp,qbe such that|qx-p| ≤1/Q <1/q. Then |x-p/q|<1/q2so there is at least one suchp/q. Now letQ >1qx-pbe an arbitrary integer and letp?,q?be such that |q?x-p?| ≤1/Q <|qx-p|. This means thatp?/q??=p/qand|x-p?/q?| ≤1/q?Q <1/q?2.1 For a real numberrits fractional part, denoted{r}, is defined by{r}=r-[r]where [r]is the integral part ofr. 51

52CHAPTER 9. DIOPHANTINE APPROXIMATIONS

The latter is known as Dirichlet"s theorem. We have already proved it in the previous chapter using continued fractions. In the next section we will use the properties of continued fractions to strengthen Dirichlet"s theorem. Remark9.3.Ifxis rational then there are finitely many such fractionsp/q. Indeed, ifx=a/band|a/b-p/q|<1/q2withp/q?=a/bthenq < bso there are only finitely many possibilities forq. Further, for everyqthere are only finitely many possibilities forp.

9.2 Better approximations

Proposition 9.4.For an irrational numberxthere are infinitely many ra- tional numbersp/qsuch that|x-pq |<12q2. Proof.We show that at least one of any two consecutive convergents to (the continued fraction of)xsatisfies the desired inequality. Indeed, we have ?????x-pnq n? ????+? ????x-pn+1q n+1? ????=? ????p n+1q n+1-pnq n? ????=1q nqn+1<12q2n+12q2n+1, where the first equality holds sincex-pnq nandx-pn+1q n+1have opposite signs and the last inequality follows from the obvious fact that for all real numbers a?=bwe have2ab < a2+b2.

Now we deduce from the above inequality that either|x-pn/qn|<1/2q2nor|x-p

Politique de confidentialité -Privacy policy