[PDF] ma257: introduction to number theory lecture notes 2018

950_6ma257.pdf

MA257: INTRODUCTION TO NUMBER THEORY

LECTURE NOTES 2018

J. E. CREMONA

Contents

0. Introduction: What is Number Theory? 2

Basic Notation 3

1. Factorization 4

1.1. Divisibility inZ4

1.2. Greatest Common Divisors inZ5

1.3. The Euclidean Algorithm inZ6

1.4. Primes and unique factorization 7

1.5. Unique Factorization Domains 9

2. Congruences and modular arithmetic 14

2.1. Denition and Basic Properties 14

2.2. The structure ofZ=mZ15

2.3. Euler's, Fermat's and Wilson's Theorems 16

2.4. Some Applications 18

2.5. The Chinese Remainder Theorem or CRT 19

2.6. The structure ofUm21

3. Quadratic Reciprocity 23

3.1. Quadratic Residues and Nonresidues 23

3.2. Legendre Symbols and Euler's Criterion 23

3.3. The Law of Quadratic Reciprocity 24

4. Diophantine Equations 28

4.1. Geometry of Numbers and Minkowski's Theorem 28

4.2. Sums of squares 28

4.3. Legendre's Equation 30

4.4. Pythagorean Triples 32

4.5. Fermat's Last Theorem 33

4.6. Proof of Minkowski's Theorem 35

5.p-adic Numbers 37

5.1. Motivating examples 37

5.2. Denition ofZp38

5.3. The ringZp39

5.4. The eldQp42

5.5. Squares inZp45

5.6. Hensel lifting 47c

2018 Creative Commons Attribution-ShareAlike (CC BY-SA)

1

2 J. E. CREMONA

0.Introduction: What is Number Theory?

Number Theory is (of course) primarily the Theory of Numbers: ordinary whole numbers (integers). It is, arguably, the oldest branch of mathematics. Integer solutions to Pythagoras's equation a

2+b2=c2

have been found, systematically listed with all the arithmetic carried out in base60, on ancient Babylonian clay tablets. There are several dierent avours of Number Theory, distinguished more by the methods used than by the problems whose solutions are sought. These are ElementaryNumber Theory: using elementary methods only; AnalyticNumber Theory: using analysis (real and complex), notably to study the distribution of primes; AlgebraicNumber Theory: using more advanced algebra, and also studyingalgebraic numberssuch as1 +3p2 +

17p17;

GeometricNumber Theory: using geometric, algebraic and analytic methods; also known asarithmetic algebraic geometry. Andrew Wiles used a vast array of new techniques and previously known results in arithmetic algebraic geometry to solve Fermat's Last Theorem, whose statement is entirely elementary (see below). This is typical of progress in Number Theory, where there have been many cases of entirely new mathematical theories being created to solve specic, and often quite elementary-seeming problems. This module is mostly elementary with some analytic and algebraic parts. The algebraic ap- proach is pursued further in the module MA3A6 (Algebraic Number Theory). The geometric approach is pursued further in the module MA426 (Elliptic Curves). Number Theory starts out with simple questions about integers: simple to state, if not to answer. Here are three types of question: Diophantine Equationsare equations to which one seeks integers solutions (or some- times rational solutions). For example, (1)x2+y2=z2has innitely many integral solutions (so-called Pythagorean triples); later, we will see how to nd them all. (2)xn+yn=znhasnononzero integer solutions whenn3. This is Fermat's Last Theorem, which we will certainly not be proving in these lectures, though we will prove the casen= 4. (3)y2=x3+ 17has exactly8integer solutions(x;y),x=2;1;2;4;8;43;52 and one further value which you can nd for yourselves. Proving that there are

no more solutions is harder; usingSageyou can solve this as follows:sage : EllipticCurve ([0 ,17]). integralpoints ()

(4) Every p ositiveinteger ncan be written as a sum of four squares (including0), for example

47 = 1 + 1 + 9 + 36 = 1

2+ 12+ 32+ 62;

but not all may be written as a sum of 2 or 3 squares. Which?sage : sumofksquares (4 ,47) We will answer the two- and four-square problems later, with a partial answer for three squares. Questions about primes, for example (1) There a reinnitely many p rimes(an ancient result p rovedi nEuclid.) MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 3 (2) Is every even numb er(greater than 2) expressible as the sum of two primes? This was conjectured by Goldbach in 1746 and still not proved, though it has been veried for numbers up to41018; the \weak form" of the conjecture, that every odd number greater than5is a sum of three primes, was proved in

2013 by the Peruvian Harald Helfgott.

(3) Are all the F ermatnumb ersFn= 22n+1prime (as Fermat also claimed)? Cer- tainly not: the rst four are (F1= 5,F2= 17,F3= 257,F4= 65537) but then F

5= 6416700417,F6= 27417767280421310721,F7= 59649589127497217

5704689200685129054721, and no more prime values have been discovered in

the sequence.sage : [(2^2^n+1). factor ()fornin range(9)](4)Ho wmany p rimesend in the di git7? Innitely many? Of the 664579 primes less

than 10 million, the number which end in the digits1,3,7and9respectively are166104,166230,166211, and166032(that is,24:99%,25:01%,25:01%and

24:98%). What does this suggest?sage : pc=dict([( d ,0)fordin range(10)])sage :forpinprimerange (10^7): pc [p%10]+=1

sage : [(d , pc [d] ,100.0pc [d]/sum(pc . values ()))fordin[1 ,3 ,7 ,9]](5)Are there innitely many so-called prime pairs: primes which dier by only2,

such as(3;5),(71;73)or(1000000007;1000000009)? Ecient algorithms for basic arithmetic: many modern applications of Number Theory are in the eld of cryptography (secure communication of secrets, such as transmitting condential information over the Internet). These application rely on the fact that the following two questions, which seem trivial from the theoretical points of view, are not at all trivial when asked about very large numbers with dozens or hundreds of digits: (1) Primalit yT esting:given a p ositiveinteger n, determine whethernis prime; (2) F actorization:given a p ositiveinteger n, determine the prime factors ofn. In this module, we will study a variety of such problems, mainly of the rst two types, while also laying the theoretical foundations to further study. Basic Notation.Z,Q,R,Cwill denote, as usual, the sets of integers, rational numbers, real numbers and complex numbers. The integers form a ring, the others sets are elds. N=fn2Zjn1gis the set ofnatural numbers(positive integers). N

0=fn2Zjn0gis the set of non-negative integers.

Pwill denote the set of (positive) prime numbers: integersp >1which have no factor- izationp=abwitha;b >1. Divisibility: fora;b2Zwe writeajb, and sayadividesb, whenbis a multiple ofa: ajb() 9c2Z:b=ac: Ifadoes not dividebwe writea6 jb. The divisibility relation gives a partial order onNwith

1as the \least" element and no \greatest element".

Congruence: fora;b;c2Zwithc6= 0we writeab(modc)and say thatais congruent tobmodulocifcj(ab): ab(modc)()cj(ab): Divisibility and congruence will be studied in detail later.

4 J. E. CREMONA

1.Factorization

1.1.Divisibility inZ.

Denition 1.1.1.Leta;b2Z. Then we say thatadividesband writeajbifb=acfor somec2Z: ajb() 9c2Z:b=ac: Alternatively, we may say that \bis a multiple ofa". Ifa6= 0this is equivalent to the statement that the rational numberb=ais an integerc. Ifadoes not dividebwe writea6 jb. Lemma 1.1.2.[Easy facts about divisibility] For alla,b,:::2Z: (1)ajb=)ajkb(8k2Z); (2)ajb1,ajb2=)ajb1b2; hence ifb1andb2are multiples ofa, then so are all integers of the formk1b1+k2b2. (3)ajb,bjc=)ajc; (4)ajb,bja()a=b; (5)ajb,b6= 0 =) jaj  jbj; so nonzero integers have only a nite number of divisors; (6)Ifk6= 0thenajb()kajkb; (7)Special properties of1:1ja(8a2Z), andaj 1()a=1; (8)Special properties of0:aj0 (8a2Z), and0ja()a= 0. Proposition 1.1.3(Division Algorithm inZ).Leta;b2Zwitha6= 0. There exist unique integersq;rsuch that b=aq+rwith0r 0, takeq= [b=a], theinteger partofb=a, soqb=a < q+ 1, and set r=baq. Then0r < a. Ifa <0, similarly withq=[b=a]. Uniqueness: ifb=aq1+r1=aq2+r2with0r1;r2jr1r2j=jajjq1q2j  jaj, contradiction.

Henceq1=q2, and thenr1=r2also.

Notation:the set of all multiples of a xed integerais denoted(a)oraZ: (a) =aZ=fkajk2Zg: Then we haveajb()b2(a)()(a)(b): \to contain is to divide". From

Lemma 1.1.2(4) we have(a) = (b)()a=b.

Anidealin a commutative ringRis a subsetIofRsatisfying (i)02I; (ii)a;b2I=)ab2I; (iii)a2I,r2R=)ra2I. Notation:I / R. For example, the set of all multiples of a xed elementaofRis the principal idealdenoted(a)oraR. We say thatageneratesthe principal ideal(a). The other generators of(a)are theassociatesofa: elementsb=uawhereuis a unit ofR.

Proposition 1.1.4.Every ideal inZis principal.

Proof.LetI /Z. IfI=f0gthenI= (0)and so is principal. OtherwiseIcontains positive integers, sincea2I() a2Iby property (iii); letabe the least positive element inI. By property (iii) we have(a)I. Conversely, letb2I; writeb=aq+rwith0r < a, thenr=bqa2I, so by minimality ofawe haver= 0, sob=qa2(a). SoI= (a). MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 5 Denition 1.1.5.APrincipal Ideal Domainor PID is a (nonzero) commutative ringRsuch that (i)ab= 0()a= 0orb= 0; (ii)every ideal ofRis principal. SoZis a principal ideal domain. Every nonzero ideal ofZhas a unique positive generator.

1.2.Greatest Common Divisors inZ.

Theorem 1.2.1.Leta;b2Z.

(1)There exists a unique integerdsatisfying (i)djaanddjb; (ii)ifcjaandcjbthencjd; (iii)d0. (2)The integerdcan be expressed in the formd=au+bvwithu;v2Z. Denition 1.2.2.Fora;b2Zwe dene theGreatest Common Divisor(or GCD) ofa andbto be the integerdwith the properties given in the theorem. Notation:gcd(a;b), or sometimes just(a;b). Integersaandbare said to becoprime(or relatively prime) if gcd(a;b) = 1. So integers are coprime if they have no common factors other than1. The identity gcd(a;b) =au+bvis sometimes calledBezout's identity. Proof of Theorem 1.2.1.LetI=fax+byjx;y2Zg; thenIis an ideal ofZ, soI= (d) for some integerd0. Nowdhas the formd=au+bvsinced2I, anddjaanddjbsince a;b2I= (d). Lastly, ifcjaandcjbthencjau+bv=d. Corollary 1.2.3.[Basic Properties ofgcd] For alla;b;k;m2Z: (1)aandbare coprime i there existu;v2Zsuch thatau+bv= 1; (2)gcd(a;b) = gcd(b;a) = gcd(jaj;jbj); (3)gcd(ka;kb) =jkjgcd(a;b); (4)gcd(a;0) =jaj;gcd(a;1) = 1; (5)gcd(a;b) = gcd(a;b+ka)for allk2Z; (6)ifgcd(a;m) = gcd(b;m) = 1thengcd(ab;m) = 1; (7)ifgcd(a;b) = 1thengcd(ak;bl) = 1for allk;l2N. Lemma 1.2.4.[Euler's Lemma] Ifajbcandgcd(a;b) = 1thenajc.

Proof.Write1 =au+bv; thenc=a(uc) + (bc)vsoajc.

Ifa1,a2,:::,anis any nite sequence of integers then we similarly nd that the ideal they generate,I= (a1;a1;:::;an) =fk1a1+k2a2+


+knanjk1;k2;:::;kn2Zgis an ideal ofZ, henceI= (d)for a uniqued0, and we dened= gcd(a1;a2;:::;an). We say thata1,a2,:::,anarecoprimeifgcd(a1;a2;:::;an) = 1. This is weaker than the condition thatgcd(ai;aj) = 1for alli6=j: for example,gcd(6;10;15) = 1since6 + 1015 = 1, but no pair of6;10;15is coprime. Whengcd(ai;aj) = 1for alli6=j, we say that theaiare pairwise coprime. Our proofs have been non-constructive. A very important computational tool is the Eu- clidean Algorithm, which computesd= gcd(a;b)givenaandb2Z, and its extended form which also computes the (non-unique)u;vsuch thatd=au+bv.

6 J. E. CREMONA

1.3.The Euclidean Algorithm inZ.The Euclidean Algorithm is an ecient method of

computinggcd(a;b)for any two integersaandb, without having to factorize them. It may also be used to compute the coecientsuandvin the identityd= gcd(a;b) =au+bv. The basic idea is this. We may assumeb > a >0(see the Basic Properties above). Write r=baqwith0r < a; thengcd(a;b) = gcd(r;a)and we have reduced the problem to a smaller one. After a nite number of steps we reach0, and the last positive integer in the sequencea;b;r;:::is thegcd. Example:(963;657) = (657;963) = (306;657) = (45;306) = (36;45) = (9;36) = (0;9) = 9. Here we have used963657 = 306,6572
306 = 45,3066
45 = 36,

4536 = 9.

To solve9 = 963u+ 657vwe can back-substitute in these equations:9 = 4536 =

45(3066
45) = 7
45306 = 7
(6572
306)306 = 7
65715
306 =

7
65715(963657) = 22
65715
963, sou=15andv= 22.

There is a simpler way of keeping track of all these coecients while reducing the amount which needs to be written down, using some auxiliary variables, which leads to the Euclidean algorithm. We give it in a form which keeps all the auxiliary variables positive which is easier to carry out in practice. Extended Euclidean Algorithm:Given positive integersaandb, this algorithm computes (d;u;v)such thatd= gcd(a;b) =au+bv: (1)

Set a1=a,a2=b;x1= 1,x2= 0;y1= 0,y2= 1.

(2)

Let q= [a1=a2].

(3)

Set a3=a1qa2;x3=x1+qx2;y3=y1+qy2.

(4)

Set a1=a2,a2=a3;x1=x2,x2=x3;y1=y2,y2=y3.

(5)

If a2>0loop back to Step 2.

(6) If ax1by1>0return(d;u;v) = (a1;x1;y1), else return(d;u;v) = (a1;x1;y1). Proof of the algorithm.It is clear that the sequenceaiis just the sequence of successive terms in the ordinary Euclidean Algorithm, startinga;b;:::, in which the last nonzero term isgcd(a;b). Each new term of this sequence is rst calleda3and then theaimove up by one. This shows that the algorithm terminates with the correct value ofd. Initially,ax1by1=a1andax2by2=a2. If at a general stage we haveax1by1="a1 andax2by2="a2with"=1, then a calculation shows that the same will hold at the next stage with the opposite value of". Since the last nonzero value ofa1(whena2= 0) isd, at the end we haveax1by1=d, and the sign is adjusted if necessary (which will depend on whether the number of steps is even or odd).

Example:In the previous example, theaisequence is

963;657;306;45;36;9;0

using quotients q= 1;2;6;1;4:

So thexisequence is

1;0;1;2;13;15;73

and theyisequence is

0;1;1;3;19;22;107:

Using the lastxiandyiprovides a check:

73a107b= 73
963107
657 = 0

and the preceding values give the solution:

15a22b= 15
96322
657 =9:

MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 7

So we may takeu=15,v= 22.

1.4.Primes and unique factorization.

Denition 1.4.1.Aprime number(orprimefor short) is an integerp >1whose only divisors are1andp; the set of primes is denotedP: p2P()p >1andp=ab=)a=1orb=1: For example2;3;5;7;11are primes. Integersn >1which are not prime are called composite. Ifais any integer then eitherpja, in which casegcd(p;a) =p, orp6 ja, in which casegcd(p;a) = 1. Lemma 1.4.2.Letpbe a prime anda;b2Z. Ifpjabthen eitherpjaorpjb(or both). Proof.Special case of Euler's Lemma 1.2.4: ifpjabandp6 jathengcd(p;a) = 1sopjb. This property of primes is very important, and the uniqueness of prime factorization relies on it. (It is easy to see that composite numbers do not have this property.) More generally: Corollary 1.4.3.Letpbe a prime anda1;a2;:::;an2Z. Then pja1a2:::an=)pjaifor somei: Theorem 1.4.4(Fundamental Theorem of Arithmetic).Every positive integernis a product of prime numbers, and its factorization into primes is unique up to the order of the factors. Note that this includesn= 1which is an \empty" product, and primes themselves with only one factor in the product. Collecting together any powers of primes which occur in a prime factorization, we obtain Corollary 1.4.5.Every positive integernmay be expressed uniquely in the form n=pe11pe22:::pekk wherep1;:::;pkare primes withp1< p2<


< pkand eachei1. Alternatively, every positive integernmay be expressed uniquely in the form n=Y p2Pp ep where the product is overallprimes, eachep0, but only anitenumber ofep>0. The exponentepwhich appears in this standard factorization ofnis denoted ordp(n); it is characterized by the following property: e=ordp(n)()pejnandpe+16 jn: For example,700 = 22
52
7, so ord2(700) =ord5(700) = 2, ord7(700) = 1, and ordp(700) =

0for primesp6= 2;5;7. Every positive integernis uniquely determined by the sequence of

exponents ord p(n). This standard factorization of positive integers into primes may be extended to negative integers by allowing a factor1in front of the product, and to nonzero rational numbers by allowing the exponents to be negative. We may accordingly extend the function ord ptoQ, by setting ord p(n) =ordp(n)and ordp(n=d) =ordp(n)ordp(d)for nonzero rationalsn=d. [You should check that this is well-dened, independent of the representation of the fraction n=d.] Then we have the following extension of the main theorem on unique factorization: Corollary 1.4.6.Every nonzero rational numberxmay be uniquely expressed in the form x=Y p2Ppordp(x):

8 J. E. CREMONA

For example,72=91 =233271131.

Proof of the Fundamental Theorem.Existence (using strong induction): Letn1and sup- pose true for allm < n; eithern= 1(OK, empty product) ornis prime (OK with one factor), orn=abwitha;b < n, in which case by induction bothaandbare products of primes, hence so isn. Uniqueness: Supposen=p1p2:::pr=q1q2:::qswherer;s0and all thepiandqj are primes. We use induction onr. Ifr= 0thens= 0(and vice versa) since thenn= 1 which has no prime divisors. So supposer;s1. Nowp1jq1q2:::qs, sop1jqjfor somej, sop1=qjsincep1andqjare both prime. By reordering theqs we may assumej= 1, so p

1=q1. Dividing both sides byp1givesp2p3:::pr=q2q3:::qs. The left hand side now has

r1prime factors, so by inductionr1 =s1, sor=s, and the remainingpiare equal to the remainingqjin some order. Many facts about integers may easily be proved using their unique factorization into primes.

For example:

Proposition 1.4.7.Letm;n2Zbe nonzero. Then

m=n()ordp(m) =ordp(n)8p2P:

The function ord

pworks rather like a logarithm. The following is easy to check: Proposition 1.4.8.Letm;n2Zbe nonzero. Then ordp(mn) =ordp(m) +ordp(n).

Proof.Exercise.

The previous result looks elementary enough, but it is sucient to imply the uniqueness of prime factorization: for ifn=Qpepisanyfactorization ofnin to primes, applying ordq to both sides (whereqis some xed prime) and using the Proposition gives ord q(n) =Xe pordq(p) =eq; since ord q(q) = 1and ordq(p) = 0whenp6=q. It follows that the exponentsepare uniquely determined. Proposition 1.4.9.Letn2Zbe nonzero. Thennis a perfect square if and only ifn >0 and ord p(n)is even for all primesp. Proof.Ifn=m2then clearlyn >0, and ordp(n) = 2ordp(m)which is even.

Conversely, if all ord

p(n)are even, setm=Q p2Ppordp(n)=22Z; thenm2=Q p2Ppordp(n)= n(notnsincen >0). We end this section with a famous and ancient result of Euclid. Theorem 1.4.10.[Euclid] The number of primes is innite. Proof.Letp1,p2,:::,pkbe a nite set of primes. Setn=p1p2:::pk+ 1. Thenn2, so nhas a prime factorq, andqis not equal to any of thepisince they clearly do not dividen. So there exists a prime outside the nite set. Hence the set of all primes cannot be nite. Note that this proof actually shows how to construct a \new" prime from any given nite set of known primes. Variations of this proof can show that there are innitely many primes of various special forms: see the Exercises. MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 9

1.5.Unique Factorization Domains.Theorem 1.4.4 (extended to include negative inte-

gers) may be expressed succinctly by the statement thatZis aUnique Factorization Domain or UFD. Roughly speaking, a UFD is a ring in which every element has an essentially unique factorization as a unit times a product of \prime" elements. Every PID is a UFD (but not conversely:Z[X]is a UFD but not a PID), and an important source of PIDs is rings which have a \division algorithm" similar to the one forZ. Such rings are called Euclidean Domains, and we start by dening these. Denition 1.5.1.(a)A nonzero ringRis anIntegral Domainif, fora;b2R, ab= 0()(a= 0orb= 0): (b)A nonzero ringRis aEuclidean Domainor ED if it is an integral domain equipped with a function:R f0g !N0such that, fora;b2Rwitha6= 0, there exist q;r2Rsuch that b=aq+rwith eitherr= 0or(r)< (a):

Examples:

Zis an ED with(n) =jnj: this is what Proposition 1.1.3 states (though note that the denition of an ED does not requireqandrto be unique). Any eldFis an ED with(x) = 0for allx6= 0; this is a degenerate example since we may always taker= 0in division. IfFis a eld then the polynomial ringF[X]is an ED, using the degree function (f(X)) = deg(f(X)). The required division property is well-known, being just the usual long division for polynomials. It is important thatFis a eld here: for example,Z[X]isnotEuclidean (exercise). The ringZ[i]ofGaussian Integersis dened as

Z[i] =fa+bija;b2Zg;

it is a subring ofC. We will study this in some detail as it gives another example of a Euclidean Domain which is of interest in number theory, both for its own sake and also for proving some properties of the ordinary or \rational" integersZ. The Euclidean functiononZ[i]is usually called thenormand denotedN:

N() ==a2+b2for=a+bi2Z[i]:

Theorem 1.5.2.The ringZ[i]of Gaussian Integers is a Euclidean Domain. Lemma 1.5.3.The norm functionNonZ[i]has the following properties: (1)Multiplicativity: for all,2Z[i],N() =N()N(); (2)Positivity:N(0) = 0,N()1for6= 0; (3)Units:N() = 1()2U(Z[i]) =f1;ig. Recall that for a ringR, the group ofunits(invertible elements) is denotedU(R). Elements of an integral domain are calledassociateif one is a unit times the other, or (equivalently) if each divides the other.

Proof.1.N() = ()() = ()() =N()N().

2. Fora;b2Z,a2+b20with equality ia=b= 0.

3. Let=a+bi, soN() =a2+b2. ThenN() = 1()a2+b2= 1()(a;b)2

f(1;0);(0;1)g ()2 f1;ig. These elements are units since= 1 =)1=2Z[i]. Conversely, ifis a unit with= 1then1 =N(1) =N() =N()N(), so

N() =N() = 1since both are positive integers.

10 J. E. CREMONA

Proof of Theorem.First of all,Z[i]is an integral domain, as it is a subring ofC. Now let=a+bi;=c+di2Z[i]with6= 0. ThenN() =a2+b26= 0, and  =c+dia+bi=(c+di)(abi)N()=ac+bdN()+adbcN()i: Leteandfbe the nearest integers to the rational numbersac+bdN()andadbcN()respectively, and set =e+fi2Z[i]and= . Then= =x+yiwithjxj;jyj 1=2, sox2+y21=4 + 1=4 = 1=2. HenceN() =N()(x2+y2)12

N()< N()as

required.

Example:Take= 3 + 4iand= 10 + 11i. Then

10 + 11i3 + 4i=(10 + 11i)(34i)25

=747i25 = 3 +17i25 ; so the quotient is3and remainder(10 + 11i)3(3 + 4i) = 1i. Check:N(1i) = 2is less thanN(3 + 4i) = 25. Just as we did forZ, we can now prove that every ED is a PID: Theorem 1.5.4.LetRbe a Euclidean Domain. ThenRis a Principal Ideal Domain. Proof.LetI / R. IfI=f0gthenIis certainly principal (I= (0)) so assume thatIis nonzero. Leta2Ibe a nonzero element with minimal value of(a). Then(a)I. Conversely, ifb2I, writeb=aq+rwithr= 0or(r)< (a). The second possibility is not possible by minimality of(a), sincer=baq2I, sor= 0andb=aq2(a). Thus

I= (a)is principal.

In a PID we havegcds just as inZ, and Bezout's identity. In general we do not have uniqueness ofgcds, only uniqueness up to associates (multiplication by a unit). (InZwe avoided this non-uniqueness by insisting that allgcds were non-negative.) Denition 1.5.5.In a ringR, agcdof two elementsaandbis an elementdsatisfying (i)djaanddjb; (ii)ifcjaandcjbthencjd. Lemma 1.5.6.Ifgcd(a;b)exists then it is unique up to associates. Proof.Ifd1andd2both satisfy the conditions of Denition 1.5.5, then we have bothd1jd2 andd2jd1, sod1andd2are associate. Because of this non-uniqueness we cannot talk aboutthegcd, onlyagcdofaandb. In specic rings, one may impose an extra condition to ensure uniqueness: inZwe insisted thatgcd(a;b)0; in the polynomial ringF[X](withFa eld) one usually insists that gcd(a(X);b(X))ismonic(with leading coecient1). Proposition 1.5.7.In a PID, thegcdof two elementsaandbexists, and may be expressed in the formau+bv. Proof.Leta;b2Rwhich is a PID. LetI= (a;b) =fra+sbjr;s2Rgbe the ideal they generate, and letd2Rbe such thatI= (d). Thend=au+bvfor someu;v2Rby construction;a;b2(d)sodjaanddjb; and ifcjaandcjbthen(d) = (a;b)(c)socjd. So in a PID, whether Euclidean or not, thegcdalways exists. However, it is only in a ED that computinggcds is easily possible via the Euclidean Algorithm. Example:Take= 3 + 4iand= 10 + 11i. Then from the previous example we have 3= 1i. Similarly,3i(1i) =i, and lastly1i=i(1i)with zero remainder. The last nonzero remainder wasiwhich is therefore agcdofand; one would MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 11 normally adjust this sinceiis a unit and say thatgcd(;) = 1. Back-substitution gives i=3i(3) = (1 + 9i)3i, so nally1 = (9i)3. The next step is to show that every PID is also a unique factorization domain. In the case ofZ, we used the Euclidean property again, and not just the PID property, for this step, but since there are rings which are PIDs but not Euclidean we give a proof which works for all PIDs. Denition 1.5.8.In an integral domainR, an elementpis calledirreducibleif it is neither0 nor a unit andp=abimplies that eitheraorbis a unit;pis calledprimeif it is neither0 nor a unit andpjabimplies that eitherpjaorpjb. Lemma 1.5.9.Every prime is irreducible. In a PID, every irreducible is prime. Proof.Letpbe prime and suppose thatp=ab. Thenpjabsopja(say). Writea=pc, then p=ab=pcb, sop(1cb) = 0, and sincep6= 0andRis an integral domain,1cb= 0so bc= 1andbis a unit. In a PID, letpbe irreducible and suppose thatpjab. Ifp6 jathen the only common divisors ofpandaare units, sogcd(p;a) = 1. Hence we can write1 =pu+av, sob=p(ub)+(ab)v which is a multiple ofp. The last property will be crucial in proving the uniqueness of factorizations into irreducibles, but for the existence we need to do some more preparation. The following lemma is called the \ascending chain condition" or ACC for ideals in a PID. Lemma 1.5.10.LetRbe a PID. Let(ai)i2Nbe a sequence of elements ofRwith(a1) (a2)(a3):::. (So eachaiis a multiple of the next). Then there existsksuch that (ak) = (ak+1) = (ak+2) =:::, so the chain of ideals stabilizes. Hence any strictly ascending chain of ideals(a1)(a2)(a3):::must be nite. Proof.LetI=[i2N(ai). An easy check shows thatIis an ideal, henceI= (a)for some a2R. Buta2I=[i2N(ai)implies thata2(ak)for somek, soI= (a)(ak)I. It follows thatI= (a) = (ak) = (ak+1) =:::. This lemma is used to replace induction in the proof of the existence of factorizations into irreducibles, which was used forZ. Proposition 1.5.11.LetRbe a PID. Every element ofRwhich is neither0nor a unit is a product of irreducibles. Proof.First we show that every nonzero non-unit ofRhas an irreducible factor. Leta2R be neither0nor a unit. Ifais irreducible there is nothing more to do. Otherwise there is a factorizationa=a1b1with neither factor a unit. Ifa1is not irreducible thena1=a2b2with neither factor a unit. Continuing in this way we have(a)(a1)(a2):::with strict inclusions sinceb1=a1=a,b2=a1=a2,:::are non-units. By the ACC lemma the sequence must be nite, so eventually someakis irreducible. Now we show thatais a product of irreducibles. Ifaitself is irreducible, there is nothing to do; otherwise, by the rst step,a=p1c1withp1irreducible andc1not a unit. Ifc1is irreducible, stop, elsec1=p2c2withp2irreducible andc2not a unit. Continuing in this way, the process must stop since(a)(c1)(c2):::. Finally, we use the fact that in a PID irreducibles are prime to prove that the factorizations of any given nonzero non-unit are essentially the same, up to reordering the factors and replacing irreducibles by associates. Denition 1.5.12.An Integral DomainRis aUnique Factorization Domainor UFD if (i)every nonzero element may be expressed as a unit times a product of irreducibles;

12 J. E. CREMONA

(ii)the factorization in (i) is unique up to the order of the factors and replacing the irreducibles by associates; that is, ifa2Ris nonzero and a=up1p2:::pr=vq1q2:::qs withu;vunits and allpi,qjirreducibles, thenr=s, and after permuting theqjif necessary, there are unitsvjfor1jrsuch thatqj=vjpjandu=vv1v2:::vr.

Theorem 1.5.13.LetRbe a PID. ThenRis a UFD.

Proof.The existence of factorizations into irreducibles has already been shown for non-units; units are included by allowing an empty product of irreducibles and an extra unit factor. Uniqueness: Suppose thata=up1p2:::pr=vq1q2:::qswithu;vunits and allpi,qj irreducibles. Ifr= 0thenais a unit, hence alsos= 0(since a unit cannot be divisible by any irreducible), and conversely. So suppose thatr;s1, and use induction onr. Now p

1jvq1q2:::qs, so primality ofp1implies thatp1jqjfor somej(we cannot havep1jvsincev

is a unit). Permuting if necessary, we may assume thatj= 1sop1jq1. Henceq1=v1p1for somev1which must be a unit sinceq1is irreducible. Dividing gives up

2:::pr= (vv1)q2:::qs;

with onlyr1irreducibles on the left, so by induction we haver1 =s1, sor=s, and unitsvjforj2such thatqj=vjpjandu= (vv1)v2:::vras required. Example (continued):Since the ringZ[i]of Gaussian Integers is Euclidean, it is a PID and a UFD. We have already determined that its units are the four elements1andi, but what are its primes/irreducibles? (1) If 2Z[i]is prime thendivides some ordinary \rational" primep, since ifn= N() =thenjnso by primality of,divides at least one prime factorpofn. (2) If N() =pis prime, thenis irreducible: for if=thenp=N() = N()N(), so one of,has norm1and is a unit. For example,1+i,2+i,3+2i,

4 +iare prime since their norms are2,5,13,17.

(3) If a rational p rimepis a sum of two squares,p=a2+b2, then setting=a+bi givesp=N() =N(), soandare both Gaussian primes. We will prove later, in Theorem 2.4.2, that every rational primepof the form4k+1can be expressed in this way; the factorsandare not associate (exercise). (4) Ho wever,rational p rimesqof the form4k+ 3cannotbe expressed as sums of two squares, since squares all leave remainder of0or1when divided by4, so all numbers of the forma2+b2leave a remainder of0,1or2on division by4. Such primesqremain prime inZ[i]. For ifq=with neithernora unit, then q

2=N()N()with bothN(),N()>1, so (by unique factorization inZ) we

must haveN() =N() =q, soqwould be a sum of two squares. We sum up this example as follows; we have proved everything stated here except for the fact that all primes of the form4k+ 1are sums of two squares (Theorem 2.4.2), and the remark about associates (exercise). Theorem 1.5.14.The ringZ[i]of Gaussian Integers is a Euclidean Domain and hence also a Principal Ideal Domain and a Unique Factorization Domain. Its units are the four elements 1,i. Its primes are as follows (together with their associates): (1)1 +i, of norm2; (2)each rational primepof the form4k+ 1is a sum of two squares,p=a2+b2, and pfactorizes inZ[i]asp=where=a+biand=abiare non-associate

Gaussian primes of normp;

(3)each rational primeqof the form4k+ 3is also a Gaussian prime. MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 13 For example, here are some Gaussian factorizations:123+456i= 3
(1+2i)
(69+14i)

(the last factor has prime norm4957),2000 = (1 +i)8(1 + 2i)3(12i)3.sage : Qi.= QQ. extension (x^2+1)sage : 2018. factor ()

21009sage : Qi (2018). factor ()

( i )(15i28)( i + 1)^2(15i + 28)sage : (123+456i ). norm (). factor ()3^254957sage : (123+456i ). factor ()(1)(14i69)(2i + 1)3There are other \number rings" similar toZ[i], but not many which are known to have

unique factorization. A complete study requires more algebra, and is done in Algebraic

Number Theory. Here are some further examples.

Example:The ringR=Z[p2]is also Euclidean and hence a UFD. The proof is almost identical to the one given above forZ[i], using the normN() =, so thatN(a+bp2) = a

2+ 2b2. The key fact which makesREuclidean via the norm is that every point in the

complex plane is at distance less than1from the nearest element ofR, as was the case with Z[i]. Factorization of primespnow depends onp(mod 8). Example:The ringR=Z[p3]isnotEuclidean, and neither a PID nor a UFD. For example,4 = 2
2 = (1 +p3)
(1p3)with all factors on the right irreducible inR. Also: the ideal(2;1+p3)is not principal; and the element2is irreducible but not prime (as the previous equation shows, since neither1p3are divisible by2inR). However, if we enlarge the ring by including numbers of the form(a+bp3)=2whereaandbare both odd, we obtain the larger ringS=Z[!], where!= (1 +p3)=2, satisfying!2+!+ 1 = 0, which is Euclidean and hence a UFD. The norm is againN() =; with=a+b!one computes thatN() =a2ab+b2, and4N() = (2ab)2+ 3b2. This ring turns out to be useful in the solution of the Fermat equationx3+y3=z3. Example:As in the previous example, the ringZ[p19]is not Euclidean. Enlarging it to R=Z[!], where now!= (1+p19)=2, satisfyingw2+w+5 = 0, we nd a ring which is still not Euclidean, but is a PID and hence a UFD. This example shows that not every PID is Euclidean. We omit the details.

14 J. E. CREMONA

2.Congruences and modular arithmetic

The notation for congruence is an invention of Gauss. It simplies many calculations and arguments in number theory.

2.1.Denition and Basic Properties.

Denition 2.1.1.Letmbe a positive integer. Fora;b2Zwe say thatais congruent tob modulomand writeab(modm)iabis a multiple ofm: ab(modm)()mj(ab): Heremis called themodulus. Ifm6 j(ab)then we writea6b(modm). For example,318 (mod 7)and1961 (mod 4). All even integers are congruent to0 (mod 2), while odd integers are congruent to1 (mod 2). Congruence may be expressed in algebraic terms: to sayab(modm)is equivalent to saying that the cosetsa+mZandb+mZofmZinZare equal. The basic properties of congruence are summarized in the following lemmas. Lemma 2.1.2.For each xed modulusm, congruence modulomis an equivalence relation: (i)Re exive:aa(modm)for alla2Z; (ii)Symmetric:ab(modm) =)ba(modm); (iii)Transitive: Ifab(modm)andbc(modm)thenac(modm). Proof.All parts are easy exercises. They follow from the fact that the subgroupmZofZ satises: (i)02mZ; (ii)x2mZ=) x2mZ; (iii)x;y2mZ=)x+y2mZ. Lemma 2.1.3.Ifab(modm)andcd(modm)thena+cb+d(modm)and acbd(modm). Proof.Another exercise. The second part follows fromacbd=a(cd) +d(ab). The preceding result has the following interpretation. As well asmZbeing a subgroup of the additive groupZ, it is also an ideal of the ringZ, and hence there is a well-dened quotient ringZ=mZ. The lemma says that addition and multiplication inZ=mZare well-dened. We will return to this viewpoint in the next section. Lemma 2.1.4.(i)Ifab(modm)thenacbc(modmc)for allc >0; (ii)Ifab(modm)andnjmthenab(modn).

Proof.Immediate from Denition 2.1.1.

Lemma 2.1.5.Ifaxay(modm), thenxy(modm=gcd(a;m)).

Two important special cases:

Ifaxay(modm)andgcd(a;m) = 1, thenxy(modm).

Ifaxay(modm)andajm, thenxy(modm=a).

Proof.Letg= gcd(a;m)and writem=gm1anda=ga1withgcd(a1;m1) = 1. Then axay(modm) =)mja(xy) =)m1ja1(xy) =)m1j(xy), the last step using Euler's Lemma. The special cases are the casesg= 1andg=arespectively. Proposition 2.1.6.Leta;b2Z. The congruenceaxb(modm)has a solutionx2Zif and only ifgcd(a;m)jb. If a solution exists it is unique modulom=gcd(a;m). In particular, whengcd(a;m) = 1the congruenceaxb(modm)has a solution for everyb, which is unique modulom. MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 15 Proof.Solvingaxb(modm)forx2Zis equivalent to solvingax+my=bforx;y2Z. Since the set of all integers of the formax+myis the ideal(a;m) = (d)whered= gcd(a;m), there is a solution ib2(d), as stated. Ifx,x0are two solutions thenaxax0(modm), which implies thatxx0(modm=d)by Lemma 2.1.5. How to solve the congruenceaxb(modm): Use the EEA to ndd;u;vwithd= gcd(a;m) =au+mv. Check thatdjb(otherwise there are no solutions). Ifb=dcthen b=auc+mvcsox=ucis one solution. The general solution isx=uc+tm=d= (ub+tm)=d for arbitraryt2Z. Lemma 2.1.7.Each integerais congruent modulomto exactly one integer in the set f0;1;2;:::;m1g. More generally, letkbe a xed integer. Then every integer is congruent modulomto exactly one integer in the setfk;k+ 1;k+ 2;:::;k+m1g. Proof.The rst statement is a restatement of the division algorithm: writea=mq+rwith

0rm1; thenar(modm), and thisris unique.

The general statement follows since no two of themintegers in the set are congruent to each other modulom, since their dierence is less thanm; hence they have distinct remainders on division bym, and so are congruent to0;1;2;:::;m1in some order. Denition 2.1.8.Takingk= 0, we obtain the system ofleast non-negative residues mod- ulom:f0;1;2;:::;m1g. Takingk=[(m1)=2]gives the system ofleast residues modulom; whenmis odd this isf0;1;2;:::;(m1)=2g, while whenmis even we in- cludem=2but notm=2. Any set ofmintegers representing allmresidue classes modulom is called aresidue system modulom. For example, whenm= 7the least non-negative residues aref0;1;2;3;4;5;6gand the least residues aref3;2;1;0;1;2;3g; form= 8we have least nonnegative residues f0;1;2;3;4;5;6;7gand least residuesf3;2;1;0;1;2;3;4g.

2.2.The structure ofZ=mZ.

Denition 2.2.1.Thering of integers modulomis the quotient ringZ=mZ. We will denote the group of units ofZ=mZbyUm, and its order by'(m). The function':N!Nis called

Euler's totient functionorEuler's phi function.

SometimesZ=mZis denotedZm; however there is a con

ict of notation here, since for primepthe notationZpis used to denote a dierent ring important in number theory, the ring ofp-adic integers.We will therefore not use this abbreviation! Informally we may identifyZ=mZwith the setf0;1;2;:::;m1g, though the elements ofZ=mZare not integers but \integers modulom": elements of the quotient ringZ=mZ. To be strictly correct, one should use the notationa,b,:::for integers anda,b,:::for their residues inZ=mZ. Then one hasa=b(inZ=mZ) iab(modm)(inZ), and Z=mZ=f0;1;2;:::;m1g. For simplicity we will not do this but use the same notation for an integer and its residue inZ=mZ. SoZ=mZis a nite ring withmelements, and its unit groupUmis a nite group under the operation of \multiplication modulom". Proposition 2.2.2.Leta2Z=mZ. Thena2Um(that is,ais invertible modulom) if and only ifgcd(a;m) = 1. Remark:Note that ifaa0(modm)thengcd(a;m) = gcd(a0;m), sincea0=a+kmfor somek. Hence the quantitygcd(a;m)only depends on the residue ofamodulom. Proof.ais invertible inZ=mZi the congruenceax1 (modm)has a solution, which is igcd(a;m) = 1.

16 J. E. CREMONA

We may use the Extended Euclidean Algorithm to detect whether or notais invertible modulom, and also to nd its inversea0if so, since if(x;y)is a solution toax+my= 1then ax1 (modm)so we may takea0=x. For example,gcd(4;13) = 1with4
1013
3 = 1, so the inverse of4modulo13is10. Here is a complete table of inverses modulo13: a0 1 2 3 4 5 6 7 8 9 10 11 12 a

0- 1 7 9 10 8 11 2 5 3 4 6 12

It follows that'(m), the order ofUm, is equal to the number of residues modulomof integers which are coprime tom. This is often given as the denition of'(m).

Corollary 2.2.3.

'(m) =jfaj0am1andgcd(a;m) = 1gj: Denition 2.2.4.Areduced residue system modulomis a set of'(m)integers covering the residue classes inUm. Any set of'(m)integers which are all coprime tom, and no two of which are congruent modulom, form a reduced residue system. The \standard" one is faj0am1andgcd(a;m) = 1g: For example,U6=f1;5g,U7=f1;2;3;4;5;6gandU8=f1;3;5;7g, so that'(6) = 2, '(7) = 6and'(8) = 4. Here are the rst few values of'(m):m123456789101112131415 '(m)11224264641041268

Proposition 2.2.5.(1)'(m)is even form3;

(2)'(m) =m1if and only ifmis prime; (3)Letpbe a prime; then'(pe) =pe1(p1)fore1. Proof.(1)Umis a group of order'(m)and the element1has order2, unlessm= 1 orm= 2when11, so'(m)must be even by Lagrange's Theorem for nite groups. (2) If mis prime thengcd(a;m) = 1for allawith1am1, and conversely. (3) Let m=pewherepis prime. The only integersanotcoprime tomare the multiples ofp, which in the range0a < pearea=pbwith0b < pe1, so '(pe) =pepe1.  We will use this to obtain a general formula for'(m)after the Chinese Remainder Theorem below, which will reduce the determination of'(m)for generalmto the case of prime powers. Arithmetic modulomis much simpler whenmis prime, as the following result indicates. Theorem 2.2.6.Ifpis a prime thenZ=pZis a eld. Ifmis composite thenZ=mZis not a eld, and not even an integral domain. Proof.Letpbe prime. ThenZ=pZis a commutative ring in which every nonzero element is invertible, i.e. a eld. Ifmis composite thenm=abwith1< a;b < m. Thenab0 (modm)whilea;b60 (modm), soZ=mZis not an integral domain. Notation:To emphasize its eld structure,Z=pZis also denotedFp, and the multiplicative groupUpis then denotedFp. It has orderp1, and is cyclic (see Theorem 2.6.1 below).

2.3.Euler's, Fermat's and Wilson's Theorems.SinceUmis a nite multiplicative group

of order'(m)we immediately have the following as a consequence of Lagrange's Theorem for nite groups. Theorem 2.3.1.(a)Euler's Theorem:Letmbe a positive integer andaan integer coprime tom. Then a '(m)1 (modm): MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 17 (b)Fermat's Little Theorem:Letpbe a prime andaan integer not divisible byp. Then a p11 (modp); moreover, for every integerawe have a pa(modp): Proof.The rst follows directly from Lagrange's Theorem for nite groups, sincea2Um which has order'(m). The second is a special case since'(p) =p1. The last follows from this, since it is clearly true whenpjaas then both sides are0. Fermat's Little Theorem can be used as a primality test. Letnbe an odd integer which one suspects to be a prime; if2n161 (modn)thennis certainly not prime. Note that this has been proved without exhibiting a factorization ofn. On the other hand, if2n11 (modn)it does not prove thatnis prime! For example this holds withn= 1729 = 7
13
19. Such a number is called a pseudoprime to base2. By using a combination of so-called bases (as here we used the base2) one can develop much stronger \probabilistic primality tests". Corollary 2.3.2.InFp[X]the polynomialXpXfactorizes as a product ofplinear factors: X pX=Y a2Fp(Xa)inFp[X]: Proof.By Fermat's Little Theorem, allpelementsa2Fpare roots ofXpX, from which the result follows by polynomial algebra. Corollary 2.3.3.[Wilson's Theorem] Letpbe a prime. Then (p1)! 1 (modp): Proof.Compare the constant term on both sides of the factorization (inFp[X]):Xp11 =Q a2Fp(Xa). This gives 1(1)p1(p1)! (modp); so(p1)!(1)p 1 (modp). Remark:The converse to Wilson's Theorem also holds; in fact, for composite integersm greater than4we have(m1)!0 (modm)(exercise). But this is not useful as a primality test, since there is no way to compute the residue of(m1)! (modm)quickly. Example: Takep= 13. Then(p1)! = 12! = 479001600 = 13
368462771. A better way of seeing this is to write

12!1
12
(2
7)
(3
9)
(4
10)
(5
8)
(6
11)12 1 (mod 13):

A similar trick, pairing each residue apart from1with its inverse, may be used to prove Wilson's Theorem directly. This works because1are the only residues modulo a prime which are their own inverse: Proposition 2.3.4.Letpbe a prime. Then the only solutions tox21 (modp)are x 1. Proof.Clearly1are solutions. SinceFpis a eld, the quadratic equationX2= 1has at most two solutions inFp, so there are no more solutions. Alternatively, ifxis a solution thenpjx21 = (x1)(x+ 1), so eitherpj(x1)or pj(x+ 1), sox 1 (modp).

18 J. E. CREMONA

Example:Letm=F5= 232+ 1 = 4294967297. Check thatx= 1366885067satises x

21 (modm). This proves thatmis not prime. In fact,m=abwherea= 671 =

gcd(m;x1)andb= 6700417 = gcd(m;x+ 1). Many modern factorization methods are based on this idea. Of course, one needs ecient ways to nd solutions other than1to the congruencex21 (modm)wheremis the (odd) composite number being factorized. There are several of these, which collectively go by the name of \quadratic sieve" methods.

2.4.Some Applications.

Proposition 2.4.1.Letpbe an odd prime. Then the congruencex2 1 (modp)has a solution if and only ifp1 (mod 4). Proof.Ifx=asatisesa2 1 (modp)thena41 (modp), and soahas order exactly4in the multiplicative groupFpof orderp1, so by Lagrange's Theorem4j(p1). If4j(p1)then the polynomialXp11is divisible byX41and hence byX2+1. But X p11factorizes inFp[X]as a product of thep1linear factorsXafora2Fp. Hence X

2+ 1is a product of two linear factors, soX2+ 1 = (Xa)(X+a)wherea2+ 1 = 0

(inFp) so the congruencex2 1 (modp)has solutionsa. There are many other ways of proving the preceding Proposition. One is to use the fact thatFpis cyclic (Theorem 2.6.1), hence has elements of orderdfor alldj(p1), and an elementaof order4satisesa4= 1,a26= 1, soa2=1. Alternatively, from Wilson's

Theorem one can show that for all oddp,

(((p1)=2)!)2 (1)(p1)=2(modp); so whenp1 (mod 4)the numbera= ((p1)=2)!satisesa2 1 (modp). As a corollary we can prove the result used earlier, that a prime of the form4k+ 1may be written as a sum of two squares. Theorem 2.4.2.Letpbe a prime such thatp1 (mod 4). Then there exist integersa andbsuch thatp=a2+b2. Proof.We give two proofs here. The rst uses the fact that the ringZ[i]of Gaussian Integers is a UFD, while the second is more elementary. A third proof will be given in Chapter 4 (see Theorem 4.2.2). All start from the existence of an integercsuch thatc2 1 (modp). First proof. InZ[i]we havepj(c2+1) = (ci)(c+i), butpdoes not divide either factor ci. Hencepis not a prime inZ[i], sop=with,2Z[i]nonunits. Taking norms givesp2=N()N(), soN() =N() =p. Writing=a+biwitha;b2Zwe have p=a2+b2as required. Second proof. Letk= [pp], sok2< p <(k+ 1)2. The set

S=f(x;y)j0xk;0ykg

contains(k+ 1)2> ppairs of integers, so there must exist two distinct pairs with the same residue ofx+cy(modp), sayx1+y1cx2+y2cwith(x1;y1)6= (x2;y2). Seta=jx1x2j andb=jy1y2j. Then on the one hand,0< a2+b22k2<2p, and on the other hand fromx1+y1cx2+y2c(modp)we havea2= (x1x2)2c2(y1y2)2c2b2 b2 (modp), soa2+b2is a multiple ofp. Hencea2+b2=p. RemarksThe rst proof can be made constructive: givencsatisfyingc2 1 (modp), it is not hard to show that the elementa+bi= gcd(c+i;p)inZ[i]satisesa2+b2=p, so a single application of the Euclidean algorithm inZ[i]gives a solution. The rst proof also shows that the solution is essentially unique, up to permutingaandb and changing their signs. This follows from the fact that the factorization ofpinZ[i]as p=with=a+biis unique up to permuting the factors and multiplying them by units. We nish this section with some more applications to the distribution of primes. MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 19 Proposition 2.4.3.(a)There are innitely many primesp1 (mod 4). (b)There are innitely many primesp3 (mod 4).

Proof.For part (b) we refer to the exercises.

We know that odd prime divisorspof numbers of the formn2+1satisfyp1 (mod 4), since the congruencex2 1 (modp)has the solutionx=n. (Or directly,nhas order4 in the groupUp, so by Lagrange4j(p1).) Now ifp1,p2,:::,pkare primes, every prime divisor of(2p1p2:::pk)2+ 1is congruent to1 (mod 4), and is distinct from all thepi, so the number of primes1 (mod 4)cannot be nite. Similarly, odd prime divisors ofn4+ 1are1 (mod 8)and there are therefore innitely many of those; odd prime divisors ofn8+ 1are1 (mod 16)so there are innitely many of those; and so on. Next we have

Proposition 2.4.4.Letqbe an odd prime.

(a)Letpbe a prime divisor off(n) =nq1+nq2+


+n+ 1. Then eitherp=qor p1 (modq). (b)There are innitely many primesp1 (modq). Proof.(a) Since(n1)f(n) =nq1we havepjnq1, sonq1 (modp). So the order ofninUpdividesq, so is either1orq. If the order is1thenn1 (modp)so0f(n)1 + 1 +


+ 1q(modp)so p=q. If the order isqthen by Lagrange,qj(p1)sop1 (modq). (b) All prime divisorspoff(qp1p2:::pk)satisfyp1 (modq)and are distinct from all thepi, so the number of primes1 (modq)cannot be nite. Usingcyclotomic polynomials(for example,f(n)above) one can show that there are innitely many primesp1 (modm)for anym. More generallyDirichlet's Theorem on primes in arithmetic progressionsstates that there are innitely many primespa(modm) wheneveraandmare coprime: the general proof uses complex analysis!

2.5.The Chinese Remainder Theorem or CRT.

Proposition 2.5.1.[Chinese Remainder Theorem for simultaneous congruences] Letm;n2 Nbe coprime. Then for every pair of integersa;bthe simultaneous congruences xa(modm)(2.5.1) xb(modn) have a solution which is unique modulomn. More generally, ifd= gcd(m;n)then the congruences (2.5.1) have a solution if and only ifab(modd), and the solution (when it exists) is unique modulo lcm(m;n) =mn=d. Proof.Writex=a+myto satisfy the rst congruence; the second then becomesa+myb (modn)ormyba(modn), which by Proposition 2.1.6 has a solution if and only if dj(ba)whered= gcd(m;n). Uniqueness:yis unique modulon=d, sox=a+myis unique modulomn=d. To nd the solution in the coprime case, write1 =mu+nv. Then we have the solution x=mub+nvasincenv1 (modm);0 (modn)whilemu0 (modm);1 (modn). Example:Letm= 13,n= 17. Then1 = gcd(13;17) = 5251so the solution for general a;bisx52b51a(mod 221).

20 J. E. CREMONA

The CRT says that there is a bijection between pairs(amodm;bmodn)and single residue classes(cmodmn)whenm;nare coprime. This bijection is in fact a ring isomor- phism: Theorem 2.5.2.[Chinese Remainder Theorem, algebraic form] Letm;n2Nbe coprime.

Then we have the isomorphism of rings

Z=mnZ=Z=mZZ=nZ:

Restricting to units on both sides, we have the isomorphism of groups U mn=UmUn: Proof.MapZ!Z=mZZ=nZbyc7!(cmodm; cmodn). This is a ring homomor- phism, which is surjective by the previous Proposition, and has kernelmZ\nZ=mnZ(the last equality becausegcd(m;n) = 1). The rst result follows by the Isomorphism Theorem for ring homomorphisms. In the correspondence(a;b)$cwe haveac(modm)andbc(modn), so gcd(c;mn) = 1()gcd(c;m) = gcd(c;n) = 1()gcd(a;m) = gcd(b;n) = 1, which gives the last bijection. Moreover, from the ring isomorphism we get an isomorphism of the groups of units, soUmn=U(Z=mnZ)=U(Z=mZZ=nZ)=U(Z=mZ)U(Z=nZ) = U mUn. Both forms of the CRT extend to several modulim1,m2,:::,mkprovided that they are pairwisecoprime. The second part of the proposition has the following important corollary: 'is amultiplicative function. Proposition 2.5.3.Letm;n2Nbe coprime. Then'(mn) ='(m)'(n).

Proof.'(mn) =jUmnj=jUmUnj=jUmj
jUnj='(m)'(n).

Corollary 2.5.4.Letm2Nhave prime factorization

m=kY i=1p eii where thepiare distinct primes andei1. Then '(m) =kY i=1p ei1 i(pi1) =mkY i=1 11p i :

Proof.By multiplicativity we have'(m) =Qk

i=1'(peii), and'(peii) =pei1 i(pi1)by Proposition 2.2.5. The last part is just a rearrangement of the product; it has the merit that the exponents of the prime divisors ofmdo not appear explicitly. Examples:(1).'(168) ='(8)'(3)'(7)(splitting168into prime powers)= (84)(3

1)(71) = 4
2
6 = 48. Alternatively,'(168) = 168
112

113
117
=

168
12

23
67 = 48. (2).'(100) ='(4)'(25) = 2
20 = 40.

One more property of'(m)will be useful later.

Proposition 2.5.5.Letm2N. ThenP

djm'(d) =m. The sum here is over all positive divisors ofm. For example, whenm= 12we have

12 ='(1) +'(2) +'(3) +'(4) +'(6) +'(12)

= 1 + 1 + 2 + 2 + 2 + 4: MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 21 Proof.Consider themfractionsk=mfor0km1. Reduced to lowest terms they becomea=dwheredjm,0ad1, andgcd(a;d) = 1. So there are'(d)fractions with denominatordfor each divisordofm, giving the total as stated. Applications of CRT:The CRT says that congruences to two coprime moduli are, in a sense, independent. Solving a general congruence to a general modulus reduces to solving it modulo prime powers, and then using CRT to \glue" the separate solutions together. For example: solvex21 (mod 91). Since91 = 7
13we rst solve separately modulo7 and modulo13, givingx 1 (mod 7)andx 1 (mod 13)by an earlier proposition since7and13are prime. This gives four possibilities modulo91: (+1 mod 7;+1 mod 13)$(+1 mod 91) (+1 mod 7;1 mod 13)$(27 mod 91) (1 mod 7;+1 mod 13)$(+27 mod 91) (1 mod 7;1 mod 13)$(1 mod 91) So the solutions arex 1 (mod 91)andx 27 (mod 91). To solve the second and third we use the method given above: write1 = 7u+ 13v= 1413, then(a;b) = (1;1) maps tomub+nva= 14b13a= 14(1)13(1) 27 (mod 91). Systematic study of various types of congruence now follows the following pattern. First work modulo primes; this is easiest sinceZ=pZis a eld. Then somehow go from primes to prime powers. The process here (called \Hensel lifting") is rather like taking successive decimal approximations to an ordinary equation, and we will come back to this at the end of the module, in Chapter 5 onp-adic numbers. Finally, use the CRT to \glue" together the information from the separate prime powers.

2.6.The structure ofUm.The most important result here is that for primep, the multi-

plicative groupUp(=Fp) is cyclic. Theorem 2.6.1.Letpbe a prime. Then the groupUp=Fpis cyclic. Proof.Everya2Fphas multiplicative orderdfor somedj(p1)and so is a root ofXd1 modulop. Conversely ifdj(p1)thenXd1jXp11(as polynomials); since the latter factors intop1distinct linear factors inFp[X], so doesXd1for eachdj(p1). So for eachdj(p1)there are exactlydroots ofXd1inFp. For eachnj(p1)the roots ofXn1have orderdfor somedjn, and conversely every element of orderdwhich dividesnis a root ofXn1. Let (d)be the number of elements of orderd. The previous statement shows thatP djn (d) =nfor allnj(p1). We prove that (n) ='(n)for allnj(p1)by induction, starting with (1) = 1 ='(1)since only a= 1has order1. If true for alld < nthen (n) =nX djn;d22 J. E. CREMONA Corollary 2.6.3.Letpbe a prime. Thenphas a primitive root, and the number of incon- gruent primitive roots modulopis'(p1). More generally, for everydj(p1)there are '(d)integers (incongruent modulop) with orderdmodulop. Ifmhas a primitive root then there are'('(m))incongruent primitive roots modulom. Example:Letp= 13. Since'(p1) ='(12) = 4there are4primitive roots modulo13. One is2, since the successive powers of2modulo13are1;2;4;8;3;6;1;:::. The others are the powers2kwheregcd(k;12) = 1: takingk= 1;5;7;11gives the primitive roots

2;256;2711;2117 (mod 13).

As an application of primitive roots, we may give a simple proof of a result proved earlier, that whenp1 (mod 4)then the congruencex2 1 (modp)has a solution. For letg be a primitive root modulop, and seta=g(p1)=4. Thena2g(p1)=261 (modp), but a

4=gp11 (modp), from which it follows thata2 1 (modp).

Theorem 2.6.4.Primitive roots modulomexist if and only ifm= 1;2;4,peor2pewhere pis an odd prime ande1. Proof.1is a primitive root modulo1and2since'(1) ='(2) = 1, and3(or1) is a primitive root modulo4. The integers excluded from the above list are the higher powers of2, andm=n1n2with gcd(n1;n2) = 1andn1,n23. Higher powers of2do not have primitive roots since '(2e) = 2e1, but induction shows that for all odd integersawe havea2e21 (mod 2e). Ifm=n1n2withgcd(n1;n2) = 1andn1,n23then both'(ni)are even; for alla2Um we then have a 12 '(m)a12 '(n1)'(n2)a'(n1)
12 '(n2)1 (modn1); sincegcd(a;n1) = 1, and similarlya12 '(m)1 (modn2), so by the Chinese Remainder

Theorem we havea12

'(m)1 (modm)for alla2Um, so no element ofUmhas order as big as'(m). Now we show that primitive roots exist form=peandm= 2pewherepis an odd prime. Letgbe a primitive root modulop, and consider the orderdofgmodulop2. By Lagrange we havedj'(p2) =p(p1), andgd1 (modp2) =)gd1 (modp) =)p1jd, so eitherd=p1ord=p(p1). Ifgp11 (modp2)then replacegbyg1=g+p, which is still a primitive root modulop, and satisesgp1

1= (g+p)p1gp1+p(p1)gp2

1pgp261 (modp2). So we may assume thatgp161 (modp2), and thengis a

primitive root modulop2as well as modulop. This samegis now a primitive root modulopefor alle1. Proceeding by induction, the order ofgmodulopedivides'(pe) =pe1(p1)and is a multiple of'(pe1) =pe2(p1) so either equalspe2(p1)orpe1(p1). However, fromgp1= 1+kpwithp6 jkit follows by induction that(gp1)pe21 +kpe161 (modpe)for alle2, so the order ofg modulopeis in factpe1(p1) ='(pe). Finally ifm= 2pewithpan odd prime, note that'(2pe) ='(2)'(pe) ='(pe). Letgbe any primitive root modulopewhich is also odd (replacegbyg+peif necessary). Thengis a primitive root modulo2pe.

Now ifmis odd, with prime factorizationm=Qk

i=1peii, it follows that the groupUmis isomorphic to the product of cyclic groups of orderpei1 i(pi1)for1ik. We have not determined the structure ofU2efore3; it turns out that while not cyclic, it is almost so: fore3,U2eis isomorphic to the product of cyclic groups of order2 (generated by1) and order2e2(generated by5). MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 23

3.Quadratic Reciprocity

In this section we will study quadratic congruences to prime moduli. Whenpis an odd prime, then any quadratic congruenceax2+bx+c0 (modp)(withp6 ja) may be reduced by completing the square to the simpler congruencey2d(modp), whered=b24ac andy= 2ax+b. So solving quadratic congruences reduces to the problem of taking square roots.

3.1.Quadratic Residues and Nonresidues.

Denition 3.1.1.Letpbe an odd prime andaan integer not divisible byp. We say thata is aquadratic residueofpwhenx2a(modp)has at least one solution, and aquadratic nonresidueotherwise. Note that whenais a quadratic residue withb2a(modp)then the congruencex2a (modp)has exactly two solutions, namelyx b. For these are both solutions; they are incongruent modulopsinceb b=)2b0 =)b0 =)a0. (Here we used thatp6= 2.) Lastly, there are no more solutions sincepjx2a=)pjx2b2=) pj(xb)(x+b) =)pj(xb)orpj(x+b). We can nd the quadratic residues modulopby reducingb2modulopfor1b(p1)=2. The other squares will repeat these (in reverse order), since(pb)2b2(modp). It follows that exactly half the nonzero residues are quadratic residues and the other half quadratic nonresidues. Examples:p= 11: the quadratic residues modulo11are: 1

2;22;32;42;521;4;9;5;31;4;2;5;3

while the quadratic nonresidues are2;6;7;8;102;5;4;3;1. p= 13: the quadratic residues modulo13are: 1

2;22;32;42;52;621;4;9;3;12;101;4;4;3;1;3

while the quadratic nonresidues are2,5,6. The reason for the patterns we see here will become apparent later. Another way to see that exactly half the nonzero residues are quadratic residues is to use primitive roots. Letgbe a primitive root modulop. Then the nonzero residues aregkfor

0kp2and every integer not divisible bypis congruent togkfor somekin this

range. The quadratic residues are thegkfor evenk: that is, the powers ofg2. For example whenp= 13we may takeg= 2, sog2= 4with successive powers

1;4;3;12;9;10 (mod 13). These are the quadratic residues; to get the quadratic nonresidues

multiply them byg= 2to get the odd powers2;8;6;11;5;7 (mod 13).

3.2.Legendre Symbols and Euler's Criterion.

Denition 3.2.1.TheLegendre Symbolap

 is dened as follows:  ap  =8 < :+1ifp6 jaandx2a(modp)has a solution 1ifp6 jaandx2a(modp)does not have a solution

0ifpja

In all cases, the number of (incongruent) solutions tox2a(modp)is1 +ap  .

Proposition 3.2.2.Letpbe an odd prime.

(a)ab(modp) =)ap  =bp  .

24 J. E. CREMONA

(b)Euler's Criterion:ap  a(p1)=2(modp). (c) 1p  = (1)(p1)=2=+1ifp1 (mod 4) 1ifp3 (mod 4). (d) abp  =ap  bp  .

Proof.(a) is obvious from Denition 3.2.1.

(b) This is clear whenpjasince then both sides are congruent to0. So supposep6 ja. First we use a primitive rootg. Note thatg(p1)=2 1 (modp), sinceh=g(p1)=2 satisesh21buth61 (modp), soh 1 (modp). Writingagkwe have a (p1)=2gk(p1)=2(1)kwhich is+1ikis even which is iais a quadratic residue. Here is a direct proof not using primitive roots. Ifap  = 1thenab2for someb, and thena(p1)=2bp11 (modp)by Fermat. Ifap  =1then consider the statement of Wilson's Theorem, that(p1)! 1 (modp). In the product pair ox1;x2with

1x1< x2p1whenx1x2a(modp). Noxis paired with itself sincex2a

(modp)has no solutions, so we get1a(p1)=2(modp)as required. (c) This is a special case of (b); we also proved it earlier (Proposition 2.4.1). (d) First we haveabp  (ab)(p1)=2a(p1)=2b(p1)=2ap  bp  (modp). Now both sides are inf1;0;1gso being congruent modulopthey must be equal (sincep > 2).

Corollary 3.2.3.Letpbe an odd prime.

Ifp1 (mod 4)thenap

 =ap  for alla.

Ifp3 (mod 4)thenap

 =ap  for alla.

Proof.This follows fromap

 =1p  ap  and the evaluation of1p  . If we start to ask questions such as \for which primespis2a quadratic residue?" then we are led to one of the most famous results in elementary number theory. Experimental evidence for small primes easily convinces one that the answer is \primes congruent to1 (mod 8)":2p  = +1forp= 7;17;23;31;41;47;71;::: 2p  =1forp= 3;5;11;13;19;29;37;43;:::

More generally, the value of

ap  for xedaand variableponly depends on the residue of pmodulo4a. This is one form of Gauss's famous Law of Quadratic Reciprocity.

3.3.The Law of Quadratic Reciprocity.

Proposition 3.3.1.[Gauss's Lemma] Letpbe an odd prime andaan integer not divisible byp. Thenap  = (1)s, wheresis the number of integersiwith0< i < p=2for which the least residue ofaiis negative. MA257: INTRODUCTION TO NUMBER THEORY LECTURE NOTES 2018 25 Proof.Let(n)denote the least residue ofnmodulop; recall that this means that(n)n (modp)andj(n)j< p=2. We need to count the number ofifor which(ai)<0. Now fj(ai)j j0< i < p=2g=fij0< i < p=2g since the left side is a subset of the right, and has no repeats since (ai) =(aj) =)ai aj=)i j(modp) =)i=j; sincep < ij < p. Hence(1)sQ iiQ i(ai)Q iaia(p1)=2PwhereP= ((p1)=2)!. Cancelling the common factorPgivesa(p1)=2(1)sand hence the result by Euler's criterion. Example:Takep= 13anda= 11; then we reduce11;22;33;44;55;66modulo13to 2;4;6;5;3;1. As expected by the proof of the Proposition, these are, up to sign, the integers between1and6. There are3minus signs, so1113  = (1)3=1. Ifp= 13anda= 10then we reduce10;20;30;40;50;60to3;6;4;1;2;5with four negative values, so1013  = (1)4= 1. Indeed,62= 3610 (mod 13). Corollary 3.3.2.Assume thata >0, and seta0=aifais even,a0=a1ifais odd.

Thenap

 = (1)swhere s=a 0X k=1[(kp)=(2a)]:

Proof.By Gauss's Lemma,ap

 = (1)swheresis the total number of integersiin all the intervals(kp=2a;(k+1)p=2a)foroddk= 1;3;


< a. But ifx < yandx;y =2Zthen the number of integers betweenxandyis[y][x], so is congruent to[x] + [y] (mod 2).

Example:Takep= 13anda= 11, soa0= 10. Then1113

 = (1)swheres= [13=22]+ [26=22]+[39=22]+[52=22]+[65=22]+[78=22]+[91=22]+[104=22]+[117=22]+[130=22]

0 + (1 + 1) + (2 + 2) + 3 + (4 + 4) + (5 + 5)1 (mod 2), so1113

 =1. We can use Corollary 3.3.2 to Gauss's Lemma to evaluate 2p  forallodd primesp.

Proposition 3.3.3.Letpbe an odd prime. Then2p

 = (1)(p21)=8=+1ifp 1 (mod 8); 1ifp 3 (mod 8).

Proof.By Corollary 3.3.2 we have2p

 = (1)swheres= [p=4] + [p=2], whose parity depends onp(mod 8).

Ifp= 8r+ 1thens2r+ 4r0.

Ifp= 8r+ 3thens2r+ (4r+ 1)1.

Ifp= 8r+ 5thens(2r+ 1) + (4r+ 2)1.

Ifp= 8r+ 7thens(2r+ 1) + (4r+ 3)0.

The result follows if we note that(p21)=8is even whenp 1 (mod 8)and is odd whenp 3 (mod 8).

26 J. E. CREMONA

More generally, we can deduce that in general the value of ap  only depends onp (mod 4a), our rst form ofquadratic reciprocity: although th

Politique de confidentialité -Privacy policy