Introduction to Number Theory
Introduction to Number Theory MATH 3240
Popular in Course
Popular in Mathematics (M)
verified elite notetaker
This 38 page Class Notes was uploaded by Mary Veum on Thursday September 17, 2015. The Class Notes belongs to MATH 3240 at University of Connecticut taught by Keith Conrad in Fall. Since its upload, it has received 24 views. For similar materials see /class/205818/math-3240-university-of-connecticut in Mathematics (M) at University of Connecticut.
Reviews for Introduction to Number Theory
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
SQUARES MODULO p 11 KEITH CONRAD For a whole year this theorem tormented me and absorbed my greatest e orts until at last I obtained a proof Gauss 1 INTRODUCTION For a prime p in Z1 and an integer a7 the Legendre symbol is 17 ifaEDmodpt 0modp7 lt9 71 ifa as D modp p 0 ifaEOmodp Since the Legendre symbol is multiplicative in a that is7 737 7 its evaluation is reduced to the case when a 71 or a is a prime number In part 17 we computed and Here we will prove the main law of quadratic reciprocity 711 1239q 12 for distinct odd primes p and q 2 BACKGROUND TO PROVINO THE MAIN LAW COUNTING SOLUTIONS Our proof of the main law is due to V A Lebesgue 1838 Lebesgue s proof of the main law is based on counting the number of points on the mod p unit hypersphere77 21 m z zi21modp in Actually7 only odd n and n 2 will be important for us we used n 2 in part I to compute It will be convenient to work with equations in Zp rather than congruences in Z7 principally because we will be introducing changes of variables that are simpler to describe within Zp Thus we will view 21 as the equation z m zi1 directly in Zp Since 2 1 has two solutions in Zp7 the number of solutions when n 1 is 2 The next result7 concerning n 27 was proved in part 1 Lemma 21 Fora E Zp V 7 i 7 i a 07 ltzygt m e zltpgtz2 y2 a p 3 f 7P17 Zfa0 De nition 22 For an odd prime p7 let Nnpm1mn E z mi 1 1 2 KEITH CONRAD We have found NLP and N247 For n 2 37 we will nd a recursion connecting N p to n72p When trying to solve the equation z x zi71zi71 with M E Zp7 let m1 an be chosen arbitrarily There are 19 2 such choices that can be made To solve for mnA and zn amounts to writing 1 7 z 7 7 mg as a sum of two squares7 and Lemma 21 tells us the number of ways to write an element of Zp as a sum of two squares depends only on whether or not the element is 0 Taking into account the formula in Lemma 217 NW7 Ww 6 Zp2 i 902 yz 17 90f i mi 90372 1zn26Zp p7 5 19 3 191 Both summation terms contain p 7 and the second summation term contains an addi Z 73 tional 1p Thus for any integer n 2 37 7 lt 1 72 zfzn21 71 1 7 M lt7gtgtlt P P 71 22 p 1 pNTkZJ 7pniz Equation 22 is a crucial formula It provides a recursion for the sequence N p linking any members that are two terms apart We will focus on N p for odd 71 Since N1p 27 by 22 N342 292 290729 2 U 39B H 6 a A 31H v 1 Z 02 V39s l 6 J ll 6 p A 1 v A 6 02 A l 61H v 6 7 l 6 02 v SQUARES MODULO p 11 3 Doing this one more time 71 N7p p6 ltgt pN5p 7295 6 1 5 3 5 p i 19 29 729 P 71 7 lt7 P We collect all these formulas for NW7 in Table 1 Using the data in Table 1 it is not hard to conjecture the next result Theorem 23 For odd n 2 1 1 T n Nnp Pnil l p 21 19 Proof Use 22 and induction the inductive step goes from n to n 2 D The reader is invited to use 22 to get a formula for Nmp when n is even following the same methods as we used when n is odd The case of even 71 gt 2 will turn out not to be necessary to prove the main law of quadratic reciprocity so we omit it Remark 24 There is a geometric interpretation for part of Theorem 23 The number Nmp counts the solutions to a single equation in n dimensional space over Zp and the dominant term in its formula for p xed and 71 large is pn l A single equation in 71 variables is one constraint so intuitively its solution space has dimension 7171 Compare with Euclidean space where the solution set of 2 y2 22 1 in R3 is a sphere which is a surface and thus locally looks 2 dimensional 2 3 7 1 The standard 71 7 1 dimensional space Zp 1 has size pn l and ipm l in Theorem 23 is much smaller than p 1 for large n so to a rst approximation the n 7 1 dimensional hypersurface77 EL1 in has about as many points as the standard n71 dimensional space Zp 1 3 PROOF OF THE MAIN LAW We will use Theorem 23 to prove the main law of quadratic reciprocity In Theorem 23 let n q be an odd prime number 7 p That is we look at N 7 ltz1zqgt 6 WW 20 2571 4 KEITH CONRAD By Theorem 2 3 This is an exact formula for the number of solutions to z z 1 in Zp Reducing the formula for N 7 modulo q pq 1 becomes 1 and 19 becomes 17 31 N 2171L2139LE1 mod q Now we will compute qumodq by a wholly different method and compare to 31 The number N 7 counts solutions over Zp to the polynomial equation x 1 2 1 in q variables The polynomial z 1 1 mg is symmetric in its q variables Therefore the solution set counted by N 7 is closed under cyclic shifts if 12 zq is a solution so is 2 3 ml and so on All solutions have q coordinates and q is prime so either a solution has no cyclic shifts besides itself all z are equal or it has q cyclic shifts Therefore solutions where the coordinates are not all equal come in disjoint collections of size q By counting N 7 mod q only the solutions with all coordinates equal matter in the counting so N 7 E m E Zp qmz 1 mod q How many solutions z are there to qmz 1 in Zp lf q is a square in Zp then there are two solutions If q is a nonsquare then there are no solutions In both cases the number of solutions is 1 Comparing this to 31 we obtain 3 17 1 71p 3 21 g mod q q p Subtracting 1 from both sides 321 Both sides of this congruence are i1 so being congruent modulo q gt 2 implies they are equal integers 1 2 2 q p This is the main law of quadratic reciprocity Remark 31 We used N 7 for prime q in the proof ofthe main law of quadratic reciprocity But the proof of the formula for Nmp odd n in Theorem 23 used induction on n and therefore would not have worked if at that point we only let n be prime THE GAUSSIAN INTEGERS KEITH CONRAD Since the work of Gauss7 number theorists have been interested in analogues of Z where concepts from arithmetic can also be developed The example we will look at in this handout is the Gaussian integers abiab E Z Excluding the last two sections of the handout7 the topics we will study are extensions of common properties of the integers Here is what we will cover in each section 1 the norm on Z 2 divisibility in Zi the division theorem in the Euclidean algorithm Bezout s theorem in unique factorization in modular arithmetic in applications of to the arithmetic of Z primes in AAAAAAAA 3 4 5 6 7 8 9 1 THE NORM ln Z7 size is measured by the absolute value In Zi7 we use the norm De nition 11 For 04 a bi E Zi7 its norm is the product Na 046 a bia 7 bi a2 b2 For example7 N2 1 7i 22 72 53 For m E Z7 Nm m2 ln particular7 N1 1 Thinking about a bi as a complex number7 its norm is the square of its usual absolute value la bil a b2 Na bi a2 b2 la bilz The reason we prefer to deal with norms on instead of absolute values on is that norms are integers rather than square roots7 and the divisibility properties of norms in Z will provide important information about divisibility properties in This is based on the following algebraic property of the norm Theorem 12 The norm is multiplicative for 04 and B in Zi Noz Na Proof Write oz a bi and B 0 di Then 043 aci bd ad bci We now compute Na NW and Noz NW NW a2 202 d2 a02 ad2 M2 5 02 1 2 KEITH CONRAD and Nam ac 7 bd2 ad be2 ac2 7 2abcd bd2 ad2 2abcd be2 ac2 1 but2 1 ad2 1 bc2 The two results agree so Noz Na N D As a rst application of Theorem 12 we determine the Gaussian integers which have mul tiplicative inverses in The idea is to apply norms to reduce the question to invertibility in Z Corollary 13 The only Gaussian integers which are invertible in are i1 and ii Proof It is easy to see i1 and ii have inverses in Zi 1 and 71 are their own inverse and i and 7i are inverses of each other For the converse direction suppose oz 6 is invertible say 043 1 for some 3 E We want to show 04 E i1ii Taking the norm of both sides of the equation 043 1 we nd Na NW 1 This is an equation in Z so we know Na i1 Since the norm doesn t take negative values Na 1 Writing 04 a bi we have a2 b2 1 and the integral solutions to this give us the four values 04 i1 ii D lnvertible elements are called units The units of Z are i1 The units of are i1 and ii Knowing a Gaussian integer up to multiplication by a unit is analogous to knowing an integer up to its sign While there is no such thing as inequalities on Gaussian integers we can talk about inequalities on their norms In particular induction on the norm not on the Gaussian integer itself is a technique to bear in mind if you want to prove something by induction in We will use induction on the norm to prove unique factorization Theorems 64 and 66 The norm of every Gaussian integer is a non negative integer but it is not true that every non negative integer is a norm Indeed the norms are the integers of the form a2 1 b2 and not every positive integer is a sum of two squares Examples include 3 7 11 15 19 and 21 No Gaussian integer has norm equal to these values 2 DIVISIBILITY Divisibility in is de ned in the natural way we say 3 divides oz and write 310 if 04 y for some 39y E In this case we call 3 a divisor or a factor of 04 Example 21 Since 14 7 3i 4 5i17 2i 4 1 5i divides 14 7 3i Example 22 Does 4 5il14 1 3i We can do the division by taking a ratio and rationalizing the denominator 14 3i 14 3i4 7 5i 7 717 582 71 584 45 45i475i 41 41 41 This is not in Zi the real and imaginary parts are 7141 and 75841 which are not integers Therefore 4 1 5i does not divide 14 1 3i in Theorem 23 A Gaussian integer oz a bi is divisible by an ordinary integer c if and only if cla and clb in Z THE GAUSSIAN INTEGERS 3 Proof To say cla bi in is the same as a bi Cm for some mn E Z and that is equivalent to a cm and b on or cla and clb Taking b 0 in Theorem 23 tells us divisibility between ordinary integers does not change when working in Zi for ac E Z cla in if and only if cla in Z However this does not mean other aspects in Z stay the same For instance we will see later that some primes in Z factor in The multiplicativity of the norm turns divisibility relations in into divisibility rela tions in the more familiar setting of Z as follows Theorem 24 For 043 in Zli if lo in then N lNa in Z Proof Write Oz y for 39y E Taking the norm of both sides we have Na NB N39y This equation is in Z so it shows N l Na in Z Corollary 25 A Gaussian integer has even norm if and only if it is a multiple of 1 i DH Proof Since N1 i 2 any multiple of 1i has even norm Conversely suppose m ni has even norm Then m2 n2 E 0 mod 2 By taking cases we see this means m and n are both even or both odd In short m E n mod 2 We want to write m ni 1 1 vi for some 741 6 Z This is the same as mniuEvuvi The solution here is a nEm2 and v nm2 These are integers since m E n mod 2 Thus 1 Example 26 The norm of 1 1 3i is 10 and 1 3i 1 Example 27 Since 1 Ei has norm 2 it must be a multiple of 1 i lndeed 1Ei Ei1 Theorem 24 is useful as a quick way of showing one Gaussian integer does not divide another check the corresponding norm divisibility is not true in Z For example if 3 7il10 1 3i in Zi then taking norms 581109 in Z but that isn t true Therefore 3 1 7i does not divide 10 1 3i in Turning a divisibility problem in into one in Z has an obvious appeal since we are more comfortable with divisibility in Z However Theorem 24 only says norm divisibility in Z follows from divisibility in The converse is usually false Consider Oz 14 1 3i and B 4 1 5i While NB 41 and Na 205 41 5 so N l Na in Z we saw in Example 22 that 4 1 5i does not divide 14 3i The foolproof method of verifying divisibility in is testing if the ratio is in after rationalizing the denominator as we did in Example 22 The norm divisibility check in Z is a necessary condition for divisibility in when it fails so does divisibility in Zi but it is not sufficient ln Z if lml then m in so m and n are unit multiples of each other The corresponding statement in is false if Na NB it is not generally true that 04 and B are unit multiples of each other Consider 4 1 5i and 4 E 5i Both have norm 41 but the unit multiples of 4 1 5i are 45i E4E5i E54i 5E4i The number 4 E Si is not on this list so 4 1 5i and 4 E 5i are not unit multiples We will see later Example 45 that 4 1 5i and 4 E 5i are even relatively prime in In short taking the norm in is a more drastic step than removing a sign on an integer 4 KEITH CONRAD 3 THE DIVISION THEOREM One reason we will be able to transfer a lot of results from Z to is the following analogue of division with remainder in Z Theorem 31 Division Theorem For 043 6 with B 74 0 there are yp E such that 04 y 1 p and Np lt In fact we can choose p so Np 12 The numbers 39y and p are the quotient and remainder and the remainder is bounded in size according to its norm by the size of the divisor 3 Before we prove Theorem 31 we note there is a subtlety in trying to calculate 39y and p This is best understood by working through an example Example 32 Let Oz 27 7 23 and B 8 i The norm of B is 65 We want to write 04 y p where Np lt 65 The idea is to consider the ratio 043 and rationalize the denominator 31 g 7 of 7 277 232 872 71937 2112 39 B 33 65 65 39 Since 19365 2969 and 721165 73246 we replace each fraction with its greatest integer and try 39y 2 7 42 However a7 274i77i and using p 7 7i is a bad idea N7 72 98 is larger than N 65 The usefulness of a division theorem is the smaller remainder Therefore our choice of 39y and p is not desirable This is the subtlety referred to before we started our example To correct our approach we have to think more carefully about the way we replace 19365 2969 and 721165 73246 with nearby integers Notice that 19365 and 721165 are each closer to the integer to their right rather than to their left That is 19365 is closer to 3 than to 2 and 721165 is closer to 73 than to 74 Let s use the closest integer rather than the greatest integer try 39y 3 7 32 Then a 7 53 7 3i 72 and 722 has norm less than NB 65 So we use 39y 3 7 3i and p 72 Choosing the nearest integer rather than the greatest integer could also be done in Z For instance 349 377 is closer to 4 than to 3 In terms of a division with remainder equation this corresponds to preferring 34 9 4 7 2 over 34 9 3 7 The remainder in the rst equation is negative but it is smaller in absolute value What we have found here is a modi ed division theorem in Z Usually for integers a and b with b 74 O the division theorem in Z says take bq to be the multiple of b which is nearest to a from the left bq a lt bq 1 Then set r a 7 bq so r 2 0 since bq a and r lt lb since bq and bq 1 are lb integers apart and a will be closer to bq than bq 1 is In the modi ed division theorem take for bq the multiple of b which is closest to a rather than just closest to a from the left Computationally the q in the modi ed division theorem is the closest integer to ab which may lie to the right of ab rather than to its left An integer is no more than 12lbl away from a multiple of b in either direction so THE GAUSSIAN INTEGERS 5 la 7 bql 12lbl Write r a 7 bq so a bq r with M 12lbl In the usual division theorem the remainder is nonnegative and bounded above by We have shrunken the upper bound at the cost of possibly making the remainder negative Sometimes a might land right in the middle between two multiples of b in which case the quotient and remainder are not unique 69 if a 27 and b 6 then a is right in the middle between 41 and 5b 27643 276573 Thus we get two choices of r either 3 or 73 The usual division theorem in Z has a unique quotient and remainder but the modi ed version gives up on uniqueness This might seem like a calamity but it s exactly what we need to prove the division theorem in Theorem 31 which is what we turn to next The proof is mostly a translation of the correct part of Example 32 into general algebraic terms After the proof we will give further examples Proof We have 043 6 with 3 34 0 and we want to construct yp E such that a m p where W lt12 NW Write 7 7 04 043 043 m m B 7 637 3 N3 where we set 043 m m Divide m and n by N3 using the modi ed division theorem in Z m NB n 717 n NBm T2 where ql and qg are in Z and 0 g 71 m 12N3 Then 5 7 NWMi T1 NBMZ Tz 7 N3 T1 Tzi N3 Set 39y q1 qgi this will be our desired quotient so after a little algebra the above equation becomes 7 T1 Tg i 32 a 7 By B We will show N047339y 12 N3 so using p 047339y will settle the division theorem Take norms of both sides of 32 and use N3 N3 to get r r Feeding the estimates 0 g 71 m g 12 N3 into the right side 14N 2 14N 2 1 l 3 N6 2 M q1q2i Na 5V 5 Example 33 Let 04 11 104 and 3 4 2 Then N3 17 We compute g 754294 6 W 17 39 6 KEITH CONRAD Since 5417 317 and 2917 170weuse39y 32i why7 Then a7 39y 17i7 so we set p 17i Note Np 2 12N Example 34 Let oz 41 24i and B 117 2i Then NB 125 and 04 043 7 403 346i 3 7 125 7 125 Since 403125 3224 and 346125 27687 we use 39y 3 1 3i why and nd 04 7 By 2 7 3i Set p 2 7 3i and compare Np with N There is one interesting difference between the division theorem in and the usual division theorem in Z the quotient and remainder are not unique in Example 35 Let oz 37 1 2i and B 11 2i7 so NB 125 If you carry out the algorithm for division in as it was developed above7 you will be led to a 3474i However7 it is also true that a 37i 27i The remainder in both cases has norm less than 125 in fact7 less than 1252 Example 36 The reader may not be impressed by the previous example7 since only the rst outcome would actually come out of our division algorithm in We now give an example where the division algorithm itself allows for two different outcomes Let oz 18i and B 2 7 4i Then 047 043 i 7302Oi7 3 Nm 20 2 239 Since 732 lies right in the middle between 72 and 717 we can use 39y 71i or 39y 72 i Using the rst choice7 we obtain a 71i712i Using the second choice7 a 72i172i That division in lacks uniqueness in the quotient and remainder does not seriously limit the usefulness of division lndeed7 back in Z7 the uniqueness of the quotient and remainder for the usual division theorem is irrelevant for many important applications such as Euclid s algorithm All those applications will carry over to Zi7 with essentially the same proofs 4 THE EUCLIDEAN ALGORITHM We begin by de ning greatest common divisors in De nition 41 For non zero oz and B in Zi7 a greatest common divisor of oz and B is a common divisor with maximal norm This is analogous to the usual de nition of greatest common divisor in Z7 except the concept is not pinned down as a speci c number If 6 is a greatest common divisor of oz and B so are at least its unit multiples 767w and 7i6 Perhaps there are other greatest common divisors we just don t know yet We will nd out in Corollary 47 We can speak about a greatest common divisor7 but not the greatest common divisor A similar THE GAUSSIAN INTEGERS 7 technicality would occur in Z if we de ned the greatest common divisor as a common divisor with largest absolute value rather than the largest positive common divisor There is no analogue of positivity in at least not in this course so we are stuck with the concept of greatest common divisor always ambiguous at least by a unit multiple De nition 42 When 04 and B only have unit factors in common we call them relatively prime Theorem 43 Euclid s algorithm Let 043 6 be non zero Recursively apply the division theorem starting with this pair and make the divisor and remainder in one equation the new dividend and divisor in the next provided the remainder is not zero a 5 71 m Np1 lt NW 6 p1v2 p2 NP2 lt NP1 p1 P2 Y3 p3 NP3 lt NW The last non zero remainder is divisible by all common divisors ofa and and is itself a common divisor so it is a greatest common divisor ofa and Proof The proof is identical to the usual proof that Euclid s algorithm works in Z We brie y summarize the argument Reasoning from the rst equation down shows every common divisor of oz and B divides the last non zero remainder Conversely reasoning from the nal equation up shows the last non zero remainder which is in the second to last equation is a common divisor of oz and 3 Therefore this last non zero remainder is a common divisor which is divisible by all the others Thus it must have maximal norm among the common divisors so it is a greatest common divisor Example 44 We compute a greatest common divisor of oz 32 9i and B 4 11i Details involved in carrying out the division theorem in each step of Euclid s algorithm are omitted The reader could work them out as more practice with the division theorem We nd 32 9i 4 11i2 7 2i 2 7 5i 411i 275i72i37i 275i 37i17i 7i 3 7i 7i1 3i 0 The last non zero remainder is 7i so 04 and B only have unit factors in common They are relatively prime Notice that unlike in Z when two Gaussian integers are relatively prime we do not necessarily obtain 1 as the last non zero remainder Rather we just obtain some unit as the last non zero remainder Example 45 We show 4 5i and 4 7 5i which are conjugates are relatively prime in Zi 45i 475ii717i 475i 717i747i 717i 7i1i0 The last non zero remainder is a unit so we are done 8 KEITH CONRAD Example 46 Here s an example where the greatest common divisor is not a unit Let a113i and 18i Then 113i 18i17i274i 18i 274i71i712i 274i 712i720 so a greatest common divisor of oz and B is 71 1 2i We could proceed in a different way in the second equation which we already met in Example 36 and get a different last non zero remainder 113i 18i17i274i 18i 274i72i172i 274i 172i20 Therefore 1 7 2i is also a greatest common divisor Our two different answers are not inconsistent a greatest common divisor is de ned at best only up to a unit multiple anyway and 71 2i and 17 2i are unit multiples of each other 71 2i 7117 2i ln Example 46 note Na 130 and NW 65 which have greatest common divisor 5 We found 04 and B have a greatest common divisor 71 1 2i which has norm 5 ls it always true that a greatest common divisor of oz and B has norm equal to Na NB No Consider Example 45 where 04 and B are relatively prime but they have the same norm A greatest common divisor ofa and 3 always has norm dividing Na N but equal ity need not hold However there is a case when it must Suppose NozN 1 Then any common divisor of oz and B has norm dividing 1 so its norm must be 1 and thus the common divisor is a unit We see that Gaussian integers with relatively prime norm have to be relatively prime themselves Again the converse is false as 4 j 5i shows For instance returning to Example 44 we compute N32 1 9i 1105 5 13 17 and N4 11i 137 a prime which are relatively prime Since the norms are relatively prime in Z 32 1 9i and 4 11i are relatively prime in We could have avoided Euclid s algorithm in in this case by using it in Z on the norms rst But in general one needs Euclid s algorithm in in order to compute greatest common divisors in The following corollary of Euclid s algorithm in shows that a greatest common divisor in is ambiguous only by a unit multiple That is the built in unit ambiguity is the only one that actually occurs Corollary 47 For non zero oz and B in Zi let 6 be a greatest common divisor produced by Euclid s algorithm Any greatest common divisor ofa and is a unit multiple of 6 Proof Let 6 be a greatest common divisor of oz and 3 From the proof of Euclid s algorithm 6 16 because 6 is a common divisor Write 6 6quoty so N03 NW NW 2 NW Since 6 is a greatest common divisor its norm is maximal among the norms of common divisors so the inequality N6 2 N6 has to be an equality That implies N39y 1 so 39y i1 or ii Thus 6 and 6 are unit multiples of each other D THE GAUSSIAN INTEGERS 9 5 BEZOUT S THEOREM ln Z Bezout s theorem says for any non zero a and b in Z that a b ax by for some z and y in Z found by back substitution in Euclid s algorithm The same idea works in and gives us Bezout s theorem there Theorem 51 Bezout s theorem Let 6 be any greatest common divisor of two non zero Gaussian integers oz and Then 6 04 1 y for some xy E Proof Being able to write 6 as a Zi combination of oz and B is unaffected by replacing 6 with a unit multiple For instance if we can do this for i6 then we multiply through by 7i to do it for 6 Thus by Corollary 47 we only need to give a proof for 6 a greatest common divisor coming from Euclid s algorithm For such 6 back substitution in Euclid s algorithm shows 6 is a Zi combination of oz and 3 Further details here are identical to the integer case and are left to the reader Corollary 52 The non zero Gaussian integers oz and B are relatively prime if and only if we can write 1 04 1 y for some z y E Proof If 04 and B are relatively prime then 1 is a greatest common divisor of oz and B so 1 om y for some zy E by Theorem 51 Conversely if 1 om y for some m y E Zi then any common divisor of oz and B is a divisor of 1 and thus is a unit That says 04 and B are relatively prime Example 53 We saw in Example 44 that 04 32 9i and B 4 11i are relatively prime since the last non zero remainder in Euclid s algorithm is 7i We can reverse the calculations in Example 44 to express 7i as a Zi combination of oz and B 7i 275i7 37i17i 275i7 7275i 2 7 5i1 72 7 lt2 7 5igtlt3igt 7 317i 7 a 7 32 7 2i3i 7 317i 7 a3i 7 37 5i To write 1 rather than 7i as a combination of oz and multiply by i 51 1a73 577i Example 54 In Example 45 we checked that 4 5i and 4 7 5i are relatively prime Using back substitution in Example 45 we obtain 4 7 5i 7 71 7 4 7 5i 7 4 5i 7 4 7 5ii74 4 5i4 4 7 5i17 4i and multiplying through by i gives 1 4 5i4i 4 7 5i4 72 i17i 1 7 7 17i 10 KEITH CONRAD Example 55 In Example 46 we saw 71 2 is a greatest common divisor of Oz 11 3 and B 1 8 Reversing the steps of Euclid s algorithm 712 18 7 274 71 1 8 7 11 3 7 1 8 17 71 11 3 1 7 1 8 1 1 7 71 11 3 1 7 1 8 1 2 a1 7 51 2 Example 56 Let Oz 10 7 91 and B 7 3 By Euclid s algorithm a B611 174 17 4 2 71 174 71 73 7 1 71 7117 0 so the last non zero remainder is 71 That tells us 04 and B are relatively prime Using back substitution 71 174 7 71 73 17 4 7 7 17 4 2 73 17 4 12 73 7 373 17 4 717 6 33 7 a 7 36 11 717 6 33 7 7 a717 6 6H6 11 717 6 3 7 239 a717 6 3757 46 We can negate to write 1 as a Z combination of Oz and B 52 1a16 57746 While the previous example shows 10 1 91 and 7 3 do not have a common factor in Z notice that their norms are N1O 91 8381 172 29 N7 3 58 2 29 so the norms of 10 91 and 73 have a common factor in Z We can understand how such phenomena relatively prime Gaussian integers have non relatively prime norms happen by exhibiting the prime factorizations77 of 10 7 91 and 7 3 without explaining how they are found however 53 10 91 17 4 4 2 7 3 1 7 2 Now we see why such examples are possible the factors 5 2 and 5 7 2 have the same norm namely 29 but they are relatively prime to each other All the usual consequences of Bezout s theorem over Z have analogues over Here are some of them Corollary 57 Let al 39y m w th Oz and relatz39uely prz39me Then al39y THE GAUSSIAN INTEGERS 11 Proof It s just like the integer proof but we write up the details anyway Set By om for some a in Since 04 and B are relatively prime we can solve the equation 1 04 1 y for some z y E Multiply both sides of the equation by 39y W V0495 v v 00 1 any 04 av Thus Oily D Corollary 58 If Oily and y in Zli with 04 and relatively prime then a l39y Proof Left to the reader It s just like the integer case B Corollary 59 For non zero 043 39y in Zli oz and B are each relatively prime to 39y if and only if 043 is relatively prime to 39y Proof Left to the reader It s just like the integer case B We close out this section with an extension to of several different characterizations of the greatest common divisor in Z The greatest common divisor of non zero integers a and b can be described in several ways the largest common divisor of a and b de nition the positive common divisor which all other common divisors divide the smallest positive value of am 1 by z y E Z the positive value of am by my E Z which divides all other values of am 1 by 90 y 6 Z The corresponding characterizations of greatest common divisors of two non zero Gauss ian integers oz and B are these 0 a common divisor of oz and B with maximal norm de nition 0 a common divisor which all other common divisors divide o a non zero value of 04 1 By z y E with smallest norm 0 a non zero value of 04 1 By z y E which divides all other values of 04 1 By 95 v 6 Zlil Verifying the equivalence of all four conditions is left to the interested reader It is completely analogous to the arguments used in the integer case Notice the switch from the to a when we pass from Z to Zi there are always four greatest common divisors ambiguous up to multiplication by any of the four units 6 UNIQUE FACTORIZATION We will de ne composite and prime Gaussian integers and then prove unique factoriza tion By Theorem 24 if 3104 then N lNa so 1 NW Na when 04 7 0 Which divisors of 04 have norm 1 or Na7 Lemma 61 For 04 7 0 any divisor ofa whose norm is 1 or Na is a unit or is a unit multiple of oz 12 KEITH CONRAD Proof If 6 04 and NB 1 then B is i1 or ii If 6 04 and NB Na consider the complementary divisor 39y where 04 y Taking norms of both sides and cancelling the common value Na we see N39y 1 so 39y is i1 or ii Therefore 6 has to be ia or iioz D Lemma 61 is not saying the only Gaussian integers whose norm is Na are ia and iia For instance 1 1 8i and 4 1 7i both have norm 65 and neither is a unit multiple of the other What Lemma 61 is saying is that the only Gaussian integers which divide oz and have norm equal to Na are ia and iia When Na gt 1 there are always eight obvious factors of 04 i1 ii ia and iia We call these the trivial factors of 04 They are analogous to the four trivial factors i1 and in of any integer n with gt 1 Any other factor of 04 is called non trivial By Lemma 61 the non trivial factors of 04 are the factors with norm strictly between 1 and Na De nition 62 Let 04 be a Gaussian integer with Na gt 1 We call 04 composite if it has a non trivial factor If 04 only has trivial factors we call 04 prime Writing 04 y the condition 1 lt NB lt Na is equivalent to NB gt 1 and N39y gt 1 We refer to any such factorization of a into a product of Gaussian integers with norm greater than 1 as a non trivial factorization Thus a composite Gaussian integer is one which admits a non trivial factorization For instance a trivial factorization of 7 i is i17 7i A non trivial factorization of 7 i is 1 7 2i1 1 3i A non trivial factorization of 5 is 1 2i1 7 2i How interesting 5 is prime in Z but it is composite in Even 2 is composite in Zi 2 1 7 However 3 is prime in Zi so some primes in Z stay prime in while others do not To show 3 is prime in Zi we argue by contradiction Assume it is composite and let a non trivial factorization be 3 043 Taking the norm of both sides 9 Na N Since the factorization is non trivial Na gt 1 and NB gt 1 Therefore Na 3 Writing 04 a bi we get a2 b2 3 There are no integers a and b satisfying that equation so we have a contradiction Thus 3 has only trivial factorizations in Zi so 3 is prime in ln Corollary 94 we will see any prime p in ZJr satisfying p E 3 mod 4 is prime in While we don t really need to construct primes explicitly in in order to prove unique factorization in Zi it is good to have some method of generating Gaussian primes if only to get a feel for what they look like by comparison with prime numbers The following test for primality in Zi using the norm provides a way to generate many Gaussian primes if we can recognize primes in Z Theorem 63 If the norm of a Gaussian integer is prime in Z then the Gaussian integer is prime in For example since N4 1 5i 41 4 1 Si is prime in Similarly 4 7 Si is prime as are 1ii 1i 2i 1i 3i 1i 4i 2 i 3i and 15 i 22i Compute each of their norms and check the result is a prime number Proof Let oz 6 have prime norm say p Na We will show 04 only has trivial factors that is its factors have norm 1 or Na only so 04 is prime in Consider any factorization of oz in Zi say 04 y Taking norms p NBN39y This is an equation in positive integers and p is prime in Z1 so either NB or N39y is 1 Therefore 6 or 39y is a unit so 04 does not admit nontrivial factors Thus 04 is prime D THE GAUSSIAN INTEGERS 13 The converse of Theorem 63 is false a Gaussian prime does not have to have prime norm For instance 3 has norm 9 but we saw 3 is prime in We have said enough about concrete Gaussian primes for now and turn our attention to unique factorization The existence of a prime factorization will be proved by a similar argument to the proof of prime factorization in Z First we will establish the existence of a prime factorization then we treat its uniqueness Theorem 64 Every 04 E with Na gt 1 is a product of primes in Proof We argue by induction on Na not by induction on 04 Suppose that Na 2 In other words 04 1 ii or 71 i Then 04 is prime by Theorem 63 Now assume n 2 3 and every Gaussian integer with norm greater than 1 and less than n is a product of primes We want to show every Gaussian integer with norm n is a product of primes If there are no Gaussian integers with norm n recall the end of Section 1 then there is nothing to prove So we may assume there are Gaussian integers with norm n Those which are prime are a product of primes in If we have a Gaussian integer 04 with norm n which is composite write a non trivial factorization of 04 as y where N N39y lt Na n By the inductive hypothesis 3 and 39y are products of primes in Therefore their product which is a is also a product of primes in We are done Having settled the existence of prime factorizations in Zi we aim for the uniqueness We start with a lemma which generalizes a familiar result about prime numbers in Z Lemma 65 Let 7139 be prime in For Gaussian integers 041 047 if wla1a2ar then 7139 divides some 04739 Proof We check the case r 2 The proof for larger r is a straightforward induction Let wlalag Suppose 7139 does not divide 041 This implies 7139 and 041 are relatively prime lndeed otherwise 7139 and 041 would have a non unit greatest common divisor which would have to be a unit multiple of 7139 since 7139 only has trivial factors as it is prime This would imply 7r divides 041 which is not the case Now that we know 7139 and 041 are relatively prime ag by Corollary 57 D We re now ready to prove unique factorization in However it is not quite what you may expect That is the following is false when s 7117127r 7r 17r 27r where the ms and 717 s are all prime in Zi r s and m 7139 after a suitable relabelling Well the r 3 part is true But there is no reason to expect we can match up the primes term by term Consider 5 1 2i17 2i 2 7i2 i The factors here are all prime in since their norms all equal the prime number 5 but the two primes in one factorization do not appear in the other Does this violate the idea of unique factorization No By allowing unit multiples we can make a match between the two factorizations 1 2i 2 7ii 17 2i 2 In fact the same phenomenon can happen in Z 6237273 14 KEITH CONRAD This is not an example of non unique factorization in Z since we can match the factors up to sign Sign issues are avoided in Z by focusing attention on positive integers and positive primes only As there is no positivity in at least in this course we are forced to allow ambiguity up to unit multiples in our prime factorizations This explains the role of units in unique factorization for Theorem 66 Unique Factorization Any 04 E with Na gt 1 has a unique factoriza tion into primes in the following sense If 0471112HunT711n2nS7 where the m s and 7139 s are prime in Zi 7r is a unit multiple of m then r s and after a suitable Tenumbering each Proof Theorem 64 shows each 04 E with Na gt 1 has a prime factorization When 04 is prime its prime factorization is obviously unique Now we show uniqueness in general by induction on Na The base case Na 2 has already been settled since such 04 s are prime Assume now that n 2 3 and every Gaussian integer with norm greater than 1 and less than n has a unique prime factorization We may assume there are Gaussian integers with norm n otherwise there is nothing to check and we only have to focus attention on composite 04 with norm n Consider two prime factorizations of 04 as in the statement of the theorem Since mla we can write 7r17r17r2 7139 By Lemma 65 7r1l7r for some j Relabelling we may suppose j 1 ie 7r1l7r 1 The only non unit factors of 7r 1 are unit multiples of 7H1 so 7r1 u39nquot1 for some unit u E i1ii The two factorizations of 04 now look like this oz u7r17r2 71 7r17r2 7rs We cancel 39Ir 1 on both sides and get 61 u7r27rr7r27r Call this common value 6 so NB Na N7r 1 lt Na Although u is a unit the product un39g on the left side of 61 is itself a prime so 61 gives two prime factorizations of B with r 7 1 primes on the left side and s 7 1 primes on the right side Since NB lt n the inductive hypothesis tells us 6 has unique factorization so r 7 1 s 7 1 thus r s and after suitable relabelling we have u7r2 and 7r 2 are unit multiples and mgr are unit multiples for i gt 2 Since u7r2 and 71quot2 are unit multiples 7r2 and 71quot2 are unit multiples so we see every 7139 is a unit multiple of 7139 and the proof is complete Knowing there is a prime factorization in the abstract is different from being able to exhibit one in practice For instance what is the prime factorization of 34i or 23191694i You have no experience factoring in Zi but you have factored in Z Let s use the norm function to let your experience in Z be the rst step in helping you factor in Our goal is not to prove a theorem about practical factoring in Zi but to illustrate the method through some examples Then you can try it out your own The key idea is this any factorization in implies a factorization in norms Indeed a 5y Na NW NW THE GAUSSIAN INTEGERS 15 We will try to use the conclusion to tell us something about the hypothesis use integer factorizations of the norm to suggest possible factors of the Gaussian integer For instance take 04 3 42 Its norm is 25 5 5 lf 3 7 4i factors a non trivial factor has to have norm 5 We know the Gaussian integers with norm 5 up to unit multiple they are 1 7 2i and 1 7 22 So we try the various possibilities 1 2i1 2239 73 4i 1 2i17 22 5 17 2i17 22 73 7 42 We recognize the last product as 704 so 3 7 42 717 2 17 2i 717 2i This is a prime factorization of 3 42 What about 2319 1694i lts norm is 8247397 whose prime factorization in Z is 8247397 17 29 16729 Let s look for the Gaussian integers with norm 17 29 and 16729 and then try multiplying them together to get 2319 1694i Gaussian factors of 17 29 and 16729 come from representations of each number as a sum of two squares 17 12 7 42 29 22 7 52 16729 402 71232 Admittedly that last equation was not found by hand These give us prime factorizations in Zi 17 1 4i17 4i 29 2 5i2 7 5i 16729 40 123i40 7123i The Gaussian integers here are prime since their norms are prime in Z Let s pick one factor from each product and multiply them together Happily the rst choice gives us what we want 1 42 2 5i40 1232 72319 7169422 Therefore the prime factorization of 2319 1694i is 2319 16942 71 42 2 5i40 1232 Except for the overall sign each factor on the right is prime in since its norm is prime in Z As an application of these ideas try to discover the prime factorizations in 53 on your own 7 MODULAR ARITHMETIC IN Z2 As in the integers congruences are de ned using divisibility De nition 71 For Gaussian integers 04 and 39y we write 04 E 3 mod 39y when 39yloz 7 3 Example 72 To check 1 7 12 E 2 7 i mod 3 i we subtract and divide 1712077271 717131 HA 3 2 3 2 The ratio is in Zi so the congruence holds 16 KEITH CONRAD Congruences in behave well under both addition and multiplication oonmod39y E mod39ygtoz Eo mod39y a Eo mod39y The details behind this are just like in Z and are left to the reader to check Since congruence modulo 0 means equality we usually assume the modulus is non zero A Gaussian integer can be reduced modulo 04 if 04 31 0 to get a congruent Gaussian integer with small norm by dividing by 04 and using the remainder Example 73 Let s compute 3 1 2i2 mod 4 2 Since 3 1 2i2 5 1 12 and 5 12i 4 1 3i 7 22 we have 3 1 2i2 E 722 mod 4 2 Example 74 To reduce 1 1 8i mod 2 7 42 we divide This was already done in Example 36 where we found more than one possibility 18i 2742 71i712i 18i 2742 71i172i Therefore 1 8i E 71 1 2i mod 2 7 4i and 1 8i E 17 2i mod 2 7 42 There is no reason to think 71 1 2i or 1 7 2i is the more correct reduction Both work There is a way to picture what modular arithmetic in means by plotting the mul tiples of a Gaussian integer in For example let s look at the Zi multiples of 1 22 Algebraically a general Zi multiple of 1 1 2i is 1 2im m 1 2im 1 225m m1 2i 7172 1 where m and n are in Z This is an integral combination of 1 1 2i and 72 i 1 In Figure 1 we plot 1 2i and 72 H as the vectors 12 and 721 in R2 FIGURE 1 1 22 and 72 2 The Zi multiples of 1 1 2i are the integral combinations of the two vectors in Figure 1 Forming all these combinations produces the picture in Figure 2 where the plane is tiled by squares having the Gaussian multiples of 1 1 2i as the vertices The signi cance of Figure 2 for modular arithmetic is that Gaussian integers are congruent modulo 1 2i precisely when they are located in the same relative positions within different squares of Figure 2 For example 2 1 3i and 4 7 3i are in the same relative position within their squares and their difference is a Gaussian multiple of 1 22 23z7473z 72iz 726jz1722 10102 22i E 12z 122 122172z 5 THE GAUSSIAN INTEGERS 17 Why are congruent Gaussian integers mod 1 22 in the same position within their respective squares Because each square shares its sides with four other squares and moving to these squares corresponds to adding 1 22 71 22 E2 1 i or 772 Moving from a position in any square to the same relative position in any other square is translation by a Gaussian multiple of 1 22 FIGURE 2 Zi multiples of 1 22 We can use Figure 2 to make a list of representatives for 22 use the Gaussian integers inside a square and one of its vertices All the vertices are Zi multiples of 1 22 so we should use only one of them Choosing the square with edges 1 22 and E2 1 i we get a list of 5 Gaussian integers 02 227114 71 22 Every Gaussian integer is congruent modulo 1 22 to exactly one of these For instance 2 32 E 71 22 mod 1 22 since 2 32 and 71 22 are in the same relative position in their respective squares Using instead the square with edges 1 22 and 2 E i we get the list 0121i22 and with this list we have 2 32 E 1 2 mod 1 22 There is nothing special about using the vertex 0 in our lists we could use any of the other vertices of the square in place of 0 for our list of representatives modulo 1 22 In fact there is nothing special about using points inside or on a single square We just need to use a set of points which lls out each relative position within all these squares For instance the numbers 0 1 2 3 4 could be used and with this list we have 2 32 E 3 mod 1 22 Let s look at the picture for modulus 2 22 In Figure 3 we plot the Zi multiples of 2 22 as vertices of squares Since 2 2im m 2 20m 2 20m m2 22 7172 22 18 KEITH CONRAD the Zi multiples of 2 1 2i are the integral combinations of 2 1 2i and 72 22 which form two edges of the heavyset square in Figure 3 FIGURE 3 Zi multiples of 2 1 2i What is a set of representatives for 2i Translating from one square to the same relative position in another square is the same as adding a Gaussian multiple of 2 22 so every Gaussian integer is congruent modulo 2 1 2i to a Gaussian integer inside or on one of the squares Points in the same relative position on opposite edges of a square are congruent since adding 2 1 2i or 72 1 2i takes us from one edge to another We didn t have to worry about this issue for modulus 1 1 2i because there were no Gaussian integers on the edges of squares in Figure 2 except for vertices Taking the edge identi cations into account a set of representatives for 2i is all the Gaussian integers inside a square and on two adjacent edges of the square with only one vertex counted Using the square with edges 2 2i and 72 22 we get the 8 representatives 0 2 22 32 712 1 22 12 712 For example 6 H E 3i mod 2 2i since 6 H and 3i are in the same relative position within their squares in Figure 3 Unlike in Figure 2 where ordinary integers can be used as representatives we can t represent 1 2i only using ordinary integers because Z only represents 4 of the 8 congruence classes mod 2 22 Figure 4 is a picture of The squares have vertices that are Zi multiples of 3 which all look like 3m m 3 71 3i where m and n are in Z A set of representatives for can be formed from the Gaussian integers inside and on the square with edges 3 and 32 Using two adjacent edges and just one of the vertices we have 9 representatives 0122 1i2i2i12i22i Finally in Figure 5 we draw one square for modulus 3 2 Its two edges with a vertex at 0 are the vectors 3i 31 and 3ii 713z 71 3 There are 10 representatives 9 in the square and one vertex Algebraic properties of modular arithmetic in Z carry over to practically word for word THE GAUSSIAN INTEGERS 19 FIGURE 4 ZM multiples of 3 FIGURE 5 Representatives for Theorem 75 If 7139 is prime in Zi then 043 E 0 mod 7139 if and only if 04 E 0 mod 7139 or B E 0 mod 7r Proof This is Lemma 65 with r 2 D 20 KEITH CONRAD Theorem 76 For 04 and B in with B E 0 om E 1mod is solvable if and only if 04 and B are relatively prime in If 04 and B are relatively prime then any linear congruence om E 39y mod 3 has a unique solution Proof To solve om E 1 mod 3 with z E amounts to solving 04 1 By 1 with z and y in Zi which is equivalent to relative primality of oz and B by Corollary 52 Once we can invert 04 mod 3 we can solve om E 39y mod 3 by multiplying both sides by the inverse of 04 mod B If there is going to be a solution this must be it and it does work D Example 77 Can we solve 1 8im E 1 mod 11 1 3i No since 1 1 8i and 11 1 3i have a common factor of E1 1 2i by Example 46 Example 78 Can we solve 7 3im E 1 mod 10 91i According to Example 56 7 1 3i and 10 91i are relatively prime although their norms are not so there is a solution Moreover by using Euclid s algorithm and back substitution we found in 52 that 7 3i57 7 46i 10 91 1 6i1 so a solution is z 57 E 46i The norm of 57 E 46i is less than the norm of the modulus 10 91i so there is no great incentive to reduce our solution further mod 10 91i Corollary 79 Let 7139 be a Gaussian prime Every 04 E 0 mod 7139 has a multiplicative inverse modulo 7139 and any polynomial congruence cam crklmnil clm co E 0 mod 7r where ci 6 and cm E 0 mod 7r has at most n solutions modulo 7r Proof Since 7139 is prime any 04 E 0 mod 7139 is relatively prime to 7139 and therefore 04 mod 7139 has a multiplicative inverse by Theorem 76 Thus is a eld so this corollary is a special case of the fact that polynomials have no more roots in a eld than their degree B When we allow Gaussian integers into our congruences does it change the meaning of congruences among ordinary integers That is if a b and c are in Z does the meaning of a E 1 mod c change when we think in Zi That is could integers which are incongruent modulo c in Z become congruent modulo c in Zi No Theorem 710 For ab and c in Z a E 1 mod c in Z if and only ifa E 1 mod c in Proof In terms of divisibility this is saying cla E b in Z ltgt claE b in Zli which is something we already checked in the paragraph after the proof of Theorem 23 divisibility between ordinary integers holds in Z if and only if it holds in D So far modular arithmetic in behaves just like in Z But things now will get tricky so pay attention One of the useful properties of modular arithmetic in Z is Fermat s little theorem For a prime p in Z1 if a E 0 mod p then a1 1 E 1 mod p Naively translating this result into the Gaussian integers using a Gaussian prime 7139 we get something like this if 04 E 0 mod 7139 then oquot1 E 1 mod 7139 7 If 7139 is not a positive integer then raising to the power 7139 E 1 doesn t mean anything in a congruence Well if you have had complex analysis you may know a way to do this but then you would also know the result is almost certainly not going to be in Zi so it s the wrong idea for us Moreover even when 7139 is a positive integer that is prime in the congruence oquot1 E 1 mod 7139 is usually wrong THE GAUSSIAN INTEGERS 21 Example 711 Let 7r 3 which is prime in Take 04 i Then oquotl i2 71 but 71 E 1 mod 3 so oquot1 E 1 mod 7139 Despite this setback there is a good Gaussian integer version of Fermat s little theorem The way to nd it is to go back to the proof of Fermat s little theorem and remind ourselves how a1 1 actually showed up in the proof It came from comparing two different sets of representatives for the non zero integers modulo p 1 2 p 7 1 and a 2a p 7 1a The two products of all the numbers in both cases have to be congruent modulo p and cancelling common terms on both sides of the congruence essentially a factor of p 7 1 leaves behind 1 E a1 1 mod p So the source of a1 1 comes from the fact that there are p71 non zero numbers modulo p It is the size of the set of non zero numbers modulo p which gave us the exponent in Fermat s little theorem There are p numbers in total modulo p and we take away 1 because we don t count 0 With this insight we get almost for free a Z il analogue Theorem 712 Let 7139 be a Gaussian prime and denote the number of Gaussian integers modulo 7139 by fa E 0 mod 7139 then a gt71 E 1 mod 7r Proof There is no natural complete set of representatives for Zi7r but we can use any complete set of representatives at all Denote it 3132 nr where we take 3 r 0 Since 04 is invertible modulo 7139 another complete set of representatives for is 04310432 413 The last term here is O Multiplying congruent numbers retains the congruence so let s multiply each set of non zero representatives together and compare Bi zm mma E 04510452 39045nw71mOdW 2 CWHMZ marl mod 7r Since the Bis here are non zero modulo 7139 why we can cancel them on both sides and we are left with 1 E a quot 1 mod 7139 D As soon as we try to test this result in an example we run into a problem We de ned n7r to be the size of but we never gave a working formula for this size For instance what is n3 Or to jazz things up n3 1 4i Example 713 Let s show there are 9 elements in 3 so n3 9 A Gaussian integer is divisible by 3 exactly when its real and imaginary parts are divisible by 3 Theorem 23 Therefore abiEcdimod3ltgtaEbmod3andcEdmod3 The real and imaginary parts have 3 possibilities modulo 3 so there is a total of 33 9 in congruent Gaussian integers modulo 3 We can even write down a nice set of representatives abi whereO ab 2 Since n3 9 Theorem 712 says that if 04 E 0 mod 3 then 048 E 1 mod 3 This works at 04 i unlike what we saw in Example 711 Using 04 1 i shows the exponent 8 is optimal 1 ik as 1 mod 3 for 1 g k lt 8 To make Theorem 712 really meaningful we want a formula for n7r in general In fact there is a nice formula for na even when 04 is not prime Theorem 714 fa 7 0 in Zi then nOi Na That is the size of ZiOi is Na 22 KEITH CONRAD There is an analogy with the absolute value on Z Zm ml when m 7 0 and now Na when 04 7 0 Our earlier lists of representatives for 2i7 2i7 Zi37 and are all consistent with this norm formula Perhaps we should point out why na is nite when 04 7 0 before we prove the formula for it Using division by 04 every Gaussian integer is congruent modulo oz to some Gaussian integer with norm less than Na There are only nitely many Gaussian integers with norm below a given bound7 so na is nite Before we prove Theorem 714 we establish a few lemmas about the n function Lemma 715 Ifm 7 0 in Z then nm m2 Proof The argument is the same as the case in 3 done in Example 713 D Lemma 716 fa 7 0 in then nE na Proof Congruences modulo oz and congruences modulo E can be converted into one another by conjugating all terms mEymodaltgtEEymodE Therefore a complete set of representatives modulo 04 becomes a complete set of represen tatives modulo 6 by conjugating the representatives7 so nE na The next lemma needs a bit more work Lemma 717 The function n is multiplicative if 04 and B are non zero in Zi then 7MB M60743 Proof Let a complete set of representatives for Zi a be m1 m2 zT and a complete set of representatives for be y17y27 y9 That is7 r na and s Given any 2 E Zi7 we have 2 E zl mod 04 for some i Then 27 at for some Gaussian integer t7 and t E yj mod 3 for some j Writing t yj 1 3w we have 2 m ayj 04310 E m ayj mod 043 Thus the is numbers xi ayj are a set of representatives for Zioz To show they are complete that is7 no repetitions7 suppose 71 z ayj E my 1 ayj mod 043 We want to show i i andj j Reducing both sides of 71 modulo 04 ml E my mod 04 Since the m s are a complete set of representatives modulo a this congruence must be equality zl my that is7 i i Then subtract the common zl on both sides of 71 and divide through the congruence including the modulus by 04 We are left with yj E yj mod 3 Since the y s are a complete set of representatives modulo 3 we have j j D We are ready to prove Theorem 714 All the real work has been put into the lemmas7 so the proof now will be a short and slick argument Proof By Lemma 7177 naE nanE By Lemma 7167 the right side is na2 At the same time7 since 046 Na is an integer7 Lemma 715 says naE Na2 Thus Na2 na2 Take positive square roots 1This shows Gaussian integers with norm less than Na ll up all congruence classes modulo 0 but there could be different remainders which are congruent7 unlike in Z7 so na is actually smaller than the number of these remainders THE GAUSSIAN INTEGERS 23 There are two points worth noting about this argument 1 While we proved na is a totally multiplicative function of 04 as a lemma we did not use this to reduce the problem of calculating na to the case of 717139 for prime 7139 Usually when we know something is multiplicative we take that as a clue to rst compute on primes then prime powers and then in general by prime factorization But the way multiplicativity of 71 got used in the proof of Theorem 714 completely sidestepped the special case of prime 04 Our derivation of the formula for na lets us count the size of Zia without giving a method of listing a complete set of representatives For instance 712 1 2i N2 1 2i 8 but this counting does not tell us a set of representatives for 1 2i it is not 0127 69 4 E 0mod 2 22 So the situation is unlike the integers where we know Zm lml because we actually made a list of representatives 0 1 2 lml 7 1 A to V With an exact formula for in hand let s reformulate Theorem 712 as a more honest analogue of Fermat s little theorem 72 a Omod7r WNWH E1mod7r Comparing this to ap 1 E 1 mod p we see more clearly from the Gaussian case that p was really playing two different roles in the integer case the modulus is p and the number of incongruent integers for that modulus is p The distinction between the modulus and the number of incongruent numbers in that modulus is more vivid in 72 where we see 7139 in one place and N7r in the other To formulate Euler s congruence in Zi we need the analogue of the Lp quCthH If you think about ltpm as the number of positive integers between 1 and m which are relatively prime to m the correct generalization to is not apparent But if you think about ltpm as the number of invertible integers modulo m then the generalization to is or should be immediate De nition 718 For non zero 04111 Zi set Lp04 Ziozx Example 719 When 04 7139 is prime every non zero Gaussian integer modulo 7139 is in vertible so 4p7r N7r 7 1 Notice the analogy to App p 7 1 When we work with this Lp fLHlCthH on Zi we need to be careful when the argument is in Z because the Gaussian LpquCthH may not agree with the integral LpquCthH For instance in Z we have 4p3 2 but in we have 4p3 8 That is Z3gtlt has 2 elements but Zi3gtlt has 8 elements This might seem strange didn t Theorem 710 tell us that congruences with a modulus in Z are the same in as in Z No Theorem 710 was about congruences in among ordinary integers to an ordinary integer modulus which leaves out a lot of congruences among all the Gaussian integers to that ordinary integer modulus Perhaps we should write Lpzm to distinguish the Gaussian LpfLHlCthH from the usual LpfLHlCthH which is now LpZ but nobody does this Euler s congruence for looks like its counterpart over Z using the Gaussian 4p function Theorem 720 If CW 1 m zm then MW E 1 mod 1 Proof This is left as an exercise in translating the proof over Z into this new setting D 24 KEITH CONRAD How do we compute 4pa7 Let s recall the Ap formulas in Z Wok pk lho 71 ab WOW if M 1 With these formulas ltpm can be computed from the prime factorization of m The analogous formulas for the Gaussian LpquCthH use norms in certain places but otherwise are identical to the counterpart in Z WW N7rk 1N7r 7 1 MW MQMB if m3 1 Example 721 What is 4p3 4i The Gaussian prime factorization is 3 4i 2 i2 Therefore 4p3 4i N2 iN2 71 5 4 20 Example 722 What is 4p57 The Gaussian prime factorization is 5 1 2i17 2i where 1 2i and 1 7 2i are relatively prime Therefore 4p5 4p1 2i4p1 7 2i N1 2i71N17 2i 7 1 16 8 APPLICATIONS OF Zi TO THE ARITHMETIC OF Z We are ready to give applications of the arithmetic of to properties of Z All these applications are connected with sums of two squares It is precisely the formula a2 b2 a bia 7 bi where a sum of two squares is on the left and a special type of factorization in is on the right that explains why is relevant to questions about sums of two squares in Z Our applications will address the following issues 0 a prime number that is a sum of two squares is so in essentially just one way 0 classi cation of primitive Pythagorean triples o the only integer solution to y2 3 7 1 is z y 10 0 systematically nding integers which are sums of two squares in more than one way Theorem 81 If a prime numberp is a sum of two squares then it is so in essentially just one way writing p a2 b2 the integers a and b are unique up to order and sign In particular the squares a2 and b2 are unique up to order Notice the theorem says nothing explicitly about It is a theorem about Z alone We will nd it very useful to use in the proof however Proof Let p a2 b2 with a b E Z Then in Zi p factors as p a bia 7 bi Since a bi and a 7 bi both have norm p which is prime in Z they are prime in Theorem 63 If there is a second representation p 02 12 then p c dic 7 di and c i di are prime in By unique factorization in Zi we must have abiucdi or abiuc7di for some unit u The only difference between c di and c 7 di is the sign of the coef cient of i and we are aiming to show that a and b are determined up to order and sign so there is no harm in treating only the case abi ucdi THE GAUSSIAN INTEGERS 25 lfu1thencaanddb lfuE1theneEaanddEb lfuithencb and d Ea If u Ei then c Eb and d a Thus 0 and at equal a and I up to order and sign D Theorem 81 is not saying that any integer which is a sum of two squares has only one representation in that form It is only referring to primes which are sums of two squares Two non primes which are a sum of two squares in more than one way are 50 52 52 12 72 and 65 12 82 42 72 We will nd more examples at the end of this section Some primes which can be written as sums of two squares necessarily uniquely are 2121251222132232171242292252 Example 82 The fth Fermat number 225 1 4294967297 is easily a sum of two squares 225 1 2162 12 Euler found it can be written as a sum of two squares in a different way 2162 12 622642 204492 This actually has an interesting consequence Fermat guessed that the fth Fermat number was a prime but the fact that it can be written as a sum of two squares in two different ways proves it is not prime without telling us what a nontrivial factor might be Euler did nd a nontrivial factor 641 225 1 641 6700417 Our next application of to ordinary arithmetic is the classi cation of Pythagorean triples which are integral solutions to the equation a2 b2 2 If any two of a b and c have a common prime factor it is also a factor of the third number why so its square appears in all terms Conversely multiplying both sides by a square rescales a b and c by the same amount Therefore we focus our attention on the Pythagorean triples a b c where they share no common factor equivalently a and I alone share no common factor Such triples are called primitive Examples of primitive Pythagorean triples include 34 5 51213 and 81517 but not 6810 We will use unique factorization in to obtain a formula for the primitive Pythagorean triples Before we give the formula let s make a few observations about primitive triples a b 0 Since there is no common factor among the three numbers at most one of them can be even why7 Could c be even If so then a and b are odd so a2 E 1 mod 8 and b2 E 1 mod 8 Then 02 a2 122 E 2 mod 8 But no number squares to 2 mod 8 Therefore 0 is odd Since a2 b2 is now known to be odd a and I do not have the same parity That is one of them is odd and the other is even Relabelling if necessary we may assume that a is odd and b is even With these preliminary observations out of the way we are ready for the main result Theorem 83 Every primitive Pythagorean triple a bc with a odd has the form am27n2 b2mn cm2n2 where m gt n gt 0 m n 1 and m E n mod 2 Conversely for any such choice ofm and n the above formula is a primitive Pythagorean triple Di erent choices ofm and it give di erent primitive triples We get 34 5 from m n 21 51213 from m n 3 2 and 15817 from m n 41 26 KEITH CONRAD Proof We write the equation a2 b2 02 in the form 81 abia7bi cc Our proof will have three steps 0 use the primitivity of the triple to show a bi and a 7 bi are relatively prime in Zi 0 use unique factorization in to show a bi is a square or i times a square in Zi 0 use the evenness of b to show a bi is a square in Zi and then read off the consequences First we show abi and aibi are relatively prime This is going to follow from a b 1 and 0 being odd Let 6 be a common divisor of a bi and a 7 bi in lt divides their sum and their difference 82 612a 61 Strictly 6 dividing the difference means 6l2bi but i is a unit so we can remove it Now we show 6 is relatively prime to 2 in Since 2 ii1i2 and 1i is prime this is equivalent to showing 6 is not divisible by 1 i By Corollary 25 1 if and only if N6 is even Because 62102 by 81 which implies N6Zlc4 and c4 is odd we see N6 is odd That tells us 1 i does not divide 6 Now that we know 6 is relatively prime to 2 in Zi 82 simpli es to 61a 61b Because a and b are relatively prime in Z they are also relatively prime in just solve am 1 by 1 in Z and then view the equation in Thus their only common divisors in are units so at last we see 6 is a unit In 81 we have a product of relatively prime Gaussian integers on the left and a perfect square on the right If you think about it the only way two relatively prime Gaussian integers can multiply to a square is if they are each squares After all think about how their prime factors can combine to give a square given that they are relatively prime and that has unique factorization Thus from 81 we must have abimni2 for some Gaussian integer m 1 mi Alas this reasoning is wrong Two relatively prime Gaussian integers can multiply to a square without either factor being a square In fact this possibility already can happen in 36 7479 Neither 74 nor 79 is a square in Z but their product is and they are relativey prime Ah the only sneaky thing here are the units Remember unique factorization always has an ambiguity due to units We tend to forget this in Z since we focus on factoring positive integers into positive factors and the only positive unit is 1 We can t forget about unitsl Very well we keep in mind the units in when looking at 81 Since the two factors on the left are relatively prime and their product is a square unique factorization in tells us each factor is itself a square up to unit multiple The units in are i1 and ii Since 71 is a perfect square it can be absorbed into any square factor by writing it as i2 Therefore we can say I lbim lni2 or 0Lbiimni2 THE GAUSSIAN INTEGERS 27 for some m 1 mi 6 Expanding these out and collecting real and imaginary parts we have a bi m2 7 n2 1 ani or a bi 72mnim2 7 n2i Now we appeal to our convention that a is odd and b is even The second choice makes a even so it is not correct We thus must have 83 a bi m ni2 so a bi is a perfect square after all The point is that we have now argued this correctly rather than incorrectly as before The derivation of 83 from unique factorizzation in is really the key step in this proof The remainder of the proof will be just a matter of careful bookkeeping ldentifying real and imaginary parts in 83 gives us am27n2 b2mn Therefore 02 a2 b2 m2 7 n22 1 47712712 m4 1 27712712 1 n4 m2 n22 Since 0 gt 0 we see that c m2 1 712 Since b gt O the formula for b shows m and n have the same sign they are both positive or both negative We can negate them both if necessary to assume m and n are positive without changing the values of a b or 0 Since a gt 0 we have m gt 71 Because a is odd m and n have different parities If m and n have a common factor then we get a common factor in a b and 0 Therefore primitivity of the triple a b 0 makes m and n relatively prime Now we show any triple m 7712 2mm m2 1 712 with m and 71 positive relatively prime of opposite parity and m gt n is a primitive Pythagorean triple Easily it is a Pythagorean triple Suppose it is not primitive Then some prime p divides each of m2 7 n2 2mm and m2 1 712 Since the rst term is odd p 344 2 Then from pl2mn we have either plm or pln lfplm then the relation m2 E n2 modp shows 712 E 0 mod p so pln We were supposing m n 1 so we have a contradiction That shows the triple is primitive lf instead pln then we get a contradiction in the same way as before just interchange the roles of m and 71 2 As for the triple being uniquely determined by m and n 83 tells us that the parameters m and n which describe the triple a b c are the coordinates of a square root of a bi As there are only two square roots which just differ by a sign the uniqueness falls out since we take m gt 0 and n gt 0 This proof tells us how to produce Pythagorean triples on demand take any Gaussian integer 04 with non zero real and imaginary parts and square it say 042 a bi Then la lb Na is a Pythagorean triple For example 1712i2 145408i and 172122 433 Therefore 145408433 is a Pythagorean triple check itl Moreover since 17 and 12 are relatively prime this triple is primitive The next application uses to show a perfect square in Z never comes right before a perfect cube except for the pair 0 and 1 Theorem 84 The only z y E Z satisfying yz m3 7 1 is m y 10 Although the cubes are spread out more thinly than the squares in Z it is not obvious why they couldn t come within one of each other many times 28 KEITH CONRAD By the way we know three examples where a cube precedes a square 71 and O 0 and 1 and 8 and 9 However this corresponds to the equation 3 y2 7 1 which is not the one we are studying Proof The integer pair z y 10 obviously ts the equation yz 3 71 We now show it is the only integral solution Write the equation in the form 353 yz 1 which has the factored form 84 903 y My 7 Z39 The same idea as in the proof of Theorem 83 suggests itself if the two factors on the right side are relatively prime in Zi then since their product is a cube each factor must be a cube up to unit multiple by unique factorization in Moreover since every unit is a cube 1 13 71 713 i 703 7i 23 it can be absorbed into the cube Thus provided we show y i and y 7i are relatively prime 84 tells us y i and y 7i are themselves cubes To see that y H and y 72 are relatively prime let 6 be a common divisor Then 6 divides their difference so 612i As 2i 1 i2 unique factorization in tells us that 6 is 1 1 2 or 1 i2 up to units If 6 is not a unit it is divisible by 1 2 so 1 Taking norms 2lz6 so z is even Then yz 1 z3 E 0 mod 8 so y2 E 71 mod 8 But 71 mod 8 is not a square We have a contradiction so 6 is a unit Now that we know y H and y 7i are relatively prime we must have as argued already y 2 m m3 for some m n E Z Expanding the cube and equating real and imaginary parts y m3 7 3771712 mm2 7 3712 1 3771271 7 n3 n3m2 7 712 The equation on the right tells us 71 i1 If n 1 then 1 3m2 7 1 so 3m2 2 which has no integer solution If n 71 then 1 73m2 7 1 so m 0 Therefore y 0 so m3y211 Thusz1 Remark 85 Using Zi in 1850 V A Lebesgue showed for all 1 2 2 that the equation yz zd 7 1 has no solution in nonzero integers z and y We end this section by returning to the theme connected to our rst application sums of two squares We saw that a prime is a sum of two squares in just one way But other numbers can be sums of two squares in more than one way such as 50 and 65 We now use arithmetic in to systematically construct integers that are sums of two squares in more than one way Consider the factorizations of 5 and 13 5 1 2i17 22 13 2 3i2 7 32 We can combine these factors in two ways 5 13 1 22 2 7 22 2 7 1 2i2 7 7 22 2 After some algebra this becomes 65 74 7i74 7 72 8 i8 ii THE GAUSSIAN INTEGERS 29 Thus 6542728212 Different representations of an integer as a sums of two squares in Z correspond to rear ranging prime factors in Zil As another example using 5 1 2i17 2i and 10 1 3i17 3i we can write down two different Gaussian integers with norm 50 1 2i1 3i 75 5i 1 2i17 3i 7 7i Taking the norm we nd 50 52 52 12 72 Let s nd an integer which is a sum of two squares in three different ways We use the primes 5 13 and 17 In Zi 5 1 2i17 2i 13 2 3i2 7 3i 17 1 4i17 4i Consider the following products 1 2i2 3i1 4i 732 7 9i 17 2i2 3i1 4i12 31i 1 2i2 7 3i1 4i 4 33i Their common norm is 5 13 17 1105 so 1105 92 322 12 312 42 332 Pursuing this theme further you can try your hand at systematically ie without having to guess constructing integers which are a sum of two squares in four ve or more different ways 9 PRIMES IN Zi Theorem 63 gave a sufficient condition for a Gaussian integer to be prime it has prime norm We saw also that this condition was not necessary 3 is prime but its norm is 9 which is not prime Our goal in this section is to classify the primes in Z We don t mean this in an absolute sense but rather in terms of the primes in Z Lemma 91 Let 7139 be a prime in For some prime p in Z 7rlp The point of this lemma is that it tells us we can get a handle on all Gaussian primes by factoring every prime in ZJr in the Gaussian integers each Gaussian prime is a factor of an ordinary prime Proof It is always the case that 7139 divides some positive integer namely its norm N7r 71 so 71quot N7r in Z Since N7r gt 1 we write N7r as a product of primes in Z1 NWP1p2pr Since 7rlN7r in Zi and 7139 is prime in Z i we must have why for some j by Lemma 65 30 KEITH CONRAD As noted already this lemma tells us the prime factors in of the primes in ZJr will give us all Gaussian primes Here are Gaussian prime factorizations of the rst three prime numbers 2 1i17i 3 3 5 12i17 2i For instance by unique factorization any other Gaussian prime factor of 5 is a unit multiple of 1 1 2i or 1 7 2i which gives one of the following numbers 12i 7172i 72i 27i 172i 712i 727i 2i Up to unit multiple these eight numbers are really just two numbers 1 1 2i and 1 7 2i Theorem 92 A prime p in ZJr is composite in if and only if it is a sum of two squares Thus any prime p in ZJr which is not a sum of two squares is not composite in Zi so it stays prime in Examples include 3 7 11 and 19 Proof If the prime p in ZJr is composite in Zi let a non trivial factorization be p 043 Then taking norms p2 Na NW Since the factorization ofp was nontrivial and p gt 0 we must have Na p Then writing 04 a bi the norm equation tells us p a2 1 b2 Conversely suppose a prime p in ZJr is a sum of two squares say p a2 1 b2 Then in we get the non trivial factorization p 7 a mm 7 In so p is composite in D The rst primes in ZJr which are sums of two squares are 2 5 13 17 and 29 2121251222132232171242292252 Therefore each of these prime numbers is composite in Zi eg 29 2 5i2 7 5i This is a Gaussian prime factorization since the factors have prime norm and thus are themselves prime in The factorization of 2 is special since its prime factors are unit multiples of each other 1 7i 7i1 In other words 2 41 i2 Corollary 93 If a prime p in ZJr is composite andp 7 2 then up to unit multiple p has exactly two Gaussian prime factors which are conjugate and have norm p Proof By Theorem 92 when p is composite we have pa2b2 abia7bi for some a b E Z Since a bi and a 7 bi have prime norm p they are prime in Could they be unit multiples We consider all four ways this could happen and show each one leads to a contradiction lfabi a7bi then b 0 andp a2 which is a contradiction lfabi 7a7bi then a 0 and we get a contradiction again lfabi ia7bi then b a andp a2717a2 2a2 but p 7 2 We have a contradiction The nal case when a bi 7ia 7 bi again implies the contradiction p 2a2 D Corollary 94 If a prime p in ZJr satis es p E 3 mod 4 then it is not a sum of two squares in Z and it stays prime in THE GAUSSIAN INTEGERS 31 Proof Once we show p is not a sum of two squares in Z it is prime in by Theorem 92 We consider the squares modulo 4 the only squares are 0 and 1 Adding them together modulo 4 gives us 0 0 0 11 0 or 0 1 and 2 1 1 We can t get 3 so any number which is E 3 mod 4 is not a sum of two squares in Z D We now know how 2 factors into Gaussian primes and how any prime p in ZJr with p E 3 mod 4 factors in it doesn t factor What about the primes p E 1mod 4 The rst such primes are 5 13 17 and 29 These are primes we saw earlier among the sums of two squares so they are all composite in by Theorem 92 and they factor into conjugate Gaussian primes by Theorem 93 ls every prime p E 1mod 4 a sum of two squares Numerical evidence suggests it is true so we make the Conjecture 95 For a prime p in Z the following conditions are equivalent 1 192 orpE1mod4 2 p a2 b2 for some 11 6 Z The easier condition to check in practice is The more interesting condition at least from the viewpoint of ordinary arithmetic is It is easy to see that 2 implies 1 if p a2 b2 for some a and b then p mod 4 is a sum of two squares The squares mod 4 are 0 and 1 so a sum of two squares mod 4 could be 0 1 or 2 Therefore p E 012 mod 4 The rst choice is impossible since p is prime and the third only happens for p 2 This argument may look familiar You already met it in the proof of Corollary 94 What about the proof that 1 implies 2 which is the more interesting direction any way It turns out to be convenient to insert an additional property in between them involving a polynomial modulo p Theorem 96 Letp be a prime in Z The following conditions are equivalent 1 192 orpE1mod4 2 the congruence m2 E E1 modp has a solution 3 pa2b2 for some 11 6 Z Proof We have already shown 3 implies To show 1 implies 2 we may take p 344 2 Consider the polynomial factorization 91 TPEl 1TP12 1TPE12 1 with mod p coef cients We are going to count roots of these polynomials modulo p Recall that a polynomial of degree d has no more than at roots modulo p By Fermat s little theorem the left side of 91 has pE1 different roots modulo p namely the non zero integers modulo p The rst polynomial on the right side of 91 has degree p E 12 so it has at most p E 12 roots modulo p Therefore the second polynomial T1 12 1 must have roots modulo p some integer 0 satis es Cp llZ E E1 mod p Since p E 1 mod 4 p E 12 is an even integer ifp 4k 1 1 then p E 12 2k Therefore ck2 E E1 mod p which proves To show 2 implies 3 we are going to show 2 implies p is composite in Then Theorem 92 says p is a sum of two squares View the congruence in 2 as a divisibility relation in Z When z2 E E1 mod p for some z E Z plx2 1 in Z Now consider this divisibility in Zi where we can factor 2 1 92 32 KEITH CONRAD To show p is composite in Zi we argue by contradiction If p is a Gaussian prime then by 92 plm or plm E in Therefore some Gaussian integer in ni satis es pm z ii but look at the imaginary part pn i1 This is impossible We have a contradiction which proves p is composite in Zi so p is a sum of two squares by Theorem Be sure you make note of the way we used the condition p E 1 mod 4 in the proof that 1 implies We can now summarize the factorization of primes in ZJr into Gaussian prime factors Theorem 97 Let p be a prime in Z The factorization ofp in is determined by p mod 4 i 2 1i17i 471 ii pr E 1 mod 4 then p 7r is a product of two conjugate primes 7r which are not unit multiples iii pr E 3 mod 4 then p stays prime in Proof Part i is a numerical check Part ii is a consequence of Corollary 93 and Theorem 96 Part iii is Corollary 94 Example 98 The prime 61 satis es 61 E 1mod 4 so 61 has two conjugate Gaussian prime factors coming from an expression of 61 as a sum of two squares Since 61 52 62 61 5 6i5 E 6i Combining the factorizations in Theorem 97 with Lemma 91 we now have a description of all the Gaussian primes in terms of the primes in Z1 Theorem 99 Euery prime in is a unit multiple of the following primes i 1i ii 7139 or f where N7r p is a prime in ZJr which is E 1 mod 4 iii p where p is a prime in ZJr with p E 3 mod 4 Proof Lemma 91 tells us any Gaussian prime is a factor of a prime in Z1 Theorem 97 and unique factorization in tell us how the primes in Z factor in up to unit multiple The Gaussian primes in parts i and ii of Theorem 99 have prime norm in Z while the primes occurring in part iii have norm p2 where p E 3 mod 4 Moreover when p E 3 mod 4 its unit multiples in are ip and ilp which have real or imaginary part 0 Thus although the converse to Theorem 63 is not strictly true we see it is true for the interesting Gaussian integers namely the ones with non zero real and imaginary part write 04 a bi and suppose a and b are both non zero in Z Then 04 is prime in if and only if Na is prime in Z Our classi cation of Gaussian primes tells us that a Gaussian prime has norm either p or p2 where p is the prime in ZJr which the Gaussian prime divides In particular any Gaussian prime other than 1i and its unit multiples has an odd norm Thus a Gaussian integer which is not divisible by 1i must have a norm which is odd so any Gaussian integer with an even norm must be divisible by 1 i This is something we already checked using simple algebra back in Corollary 25 But now we understand why it is true from a higher point of view in connection with unique factorization in Zi Corollary 25 is true because every Gaussian integer with norm greater than 1 is a product of Gaussian primes and 1i is the only Gaussian prime up to unit multiple with even norm THE GAUSSIAN INTEGERS 33 As an application of Theorem 97 we now classify all the positive integers which are sums of two squares Theorem 910 An integer greater than 1 is a sum of two squares exactly when any prime factor which is E 3 mod 4 occurs with even multiplicity Proof First we show any integer having even multiplicity at its prime factors which are E 3 mod 4 can be written as a sum of two squares We know sums of two squares are closed under multiplication view them as norms of Gaussian integers and use multiplicativity of the norm Any prime p E 1 mod 4 is a sum of two squares by Theorem 96 as is 2 While a prime p E 3 mod 4 is not a sum of two squares any even power of it is since an even power is itself a square Therefore a product of 2 primes E 1 mod 4 and even powers of primes E 3 mod 4 is a sum of two squares Now we treat the converse direction any n gt 1 which is a sum of two squares has even multiplicity at any prime factor which is E 3 mod 4 We argue by induction on n The result is true when n 2 as 2 is a sum of two squares and it has no prime factors that are E 3 mod 4 Assume a 2 3 n is a sum of two squares and the theorem has been checked for sums of two squares greater than 1 and less than a If n has no prime factors which are E 3 mod 4 then there is nothing to prove Thus we may assume a has a prime factor p with p E 3 mod 4 Write a a2 2 so pla2 b2 in Z In Zi we write this as 93 plabiaibi Since p E 3 mod 4 it is prime in Therefore from 93 we know pla bi or pla E bi in Both cases imply pla and plb in Z Why Write a pa and b pb for integers a and 19 Then n p2a2 HZ If n p2 we are done so we may suppose a gt p2 The integer n np2 a 2 132 is a sum of two squares and it is greater than 1 and less than a By our inductive hypothesis every prime factor of n which is E 3 mod 4 has even multiplicity Since the only difference between a and n is the even power p2 we conclude that every prime factor of n which is E 3 mod 4 has even multiplicity That ends the inductive step Example 911 The number 35 5 7 has a prime factor which is E 3 mod 4 namely 7 This factor appears with multiplicity 1 so 35 is not a sum of two squares Neither is 5k 7l for any odd exponent Z gt 0 But 5 72 245 is a sum of two squares 245 72 142 Theorem 910 describes the sums of two squares in terms of a condition on the prime factors which are E 3 mod 4 In particular applying the condition in the theorem to decide whether a is a sum of two squares requires that we factor n
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'