Elementary Number Theory
Contents
1. 2091 e a2 fees e nans an e f x glo where g is some error term polynomial This should be familiar to you If e 4 0 then dividing both sides by e and letting e 0 gives us the limit definition of the derivative f Theorem 3 6 Hensel Let f be a polynomial with integer coefficients Suppose there exist k N and zp Z such that f x 0 mod p and f x 0 mod p Then there exists p41 E Z such that k 1 k mod p and f x2x 1 0 mod p t ie k 1 is a lift of x to a solution of f modulo p t Explicitly if y Z reduces to the multiplicative inverse of f x modulo p then 48 C41 Tk f xe ye mod p i e the analogue of the Newton formula holds Proof that x exists First there exists y such that f x y 1 mod p by Exercise 15 Let Ek f rk Yk If 2 41 Z satisfies 48 then 2 1 k mod p because e 0 mod p To show that f p41 0 mod p 1 use 47 to expand 49 f te 1 fur Ek fun Enf ae Ek g 51 for some polynomial g Since e 0 mod p reducing modulo p gives 50 f wn41 f ve 1 ex mod p But p f a and p 1 ex so p f k 1 ex Therefore f k 1 0 mod p Proof that any lift of xj must satisfy 48 Suppose amp 41 E Z satisfies 74 1 k mod p and f k 1 0 mod p t We can write f x pap and k41 k p dy for s2. is pa e where l e 1 68 ale 2 e 2 4 e gt 3 3 Using Theorem 3 4 give a formula for the number of residual solutions to z 1 mod m in terms of the unique prime factorization of m 4 Show that if a o m Z mZ satisfy x5 a mod m then the general solution to x a mod m is x xoy where y m Z mZ satisfies y 1 mod m 5 Using part 4 show that the formula obtained in part 3 stays the same if we replace x 1 with x a for any a Z mZ that yields at least one solution for x 23 References H G H Hardy A Mathematician s Apology 1940 JJ G A Jones amp J M Jones Elementary Number Theory Springer Verlag 1998 24
3. R2 are rings then we say that a map f Ry gt Ra is a ring homomorphism or ring morphism iff 22 f a 6 f a f b 23 f ab f a f b 24 ni L i e f preserves both the addition and the multiplication operations and preserves unity We say that f is a ring isomorphism iff it is a bijective ring homomorphism In this case we write Ri Ro Exercise 11 Let R Ra be rings and consider R x Ra under the ring structure described in part 5 of Exercise 10 Show that the projection map Ri x Ra gt Ri that sends 21 12 21 is a ring homomorphism 2 6 October 2 1 Divisors Let a b Z As you know well we say that b divides a and write b a iff there exists q Z such that a bg In this case we also say that b is a divisor of a and that a is a multiple of b For example according to this definition 1 divides everything and everything divides 0 Theorem 2 1 Division Algorithm For all a b N there exist q r Z such that 25 a bq r and0 lt r lt b We say that q is the quotient and r is the remainder upon long dividing a by b Proof By Cor 5 to the well ordering principle there is a largest multiple of b that is less than or equal to a We can write it as bq for some q Z It remains to show that r a bq satisfies r lt a Indeed if this were not true then we would have b q 1 lt bq r a contradicting the definition of bq If a b N then the greatest common divi
4. 12 3 13 October 3 1 Rings of Residues Modulo m If you need a refresher on groups and rings please take a look at 1 3 1 and 1 3 2 Let m N In Example 1 2 we defined an equivalence relation on Z by setting 32 a b modm gt m a b We say that integers that are equivalent under this relation are congruent modulo m For any given integer a the residue class of a modulo m is its equivalence class under i e the set 33 la a mZ Jfa mq q Z We write Z mZ to denote the set of residue classes modulo m Explicitly 34 Z mZ a m 0 lt a lt m In this setting 9 becomes a map Z gt Z mZ called reduction modulo m Proposition 3 1 For allm N the set Z mZ forms a commutative ring under the addition la b m a b and the multiplication a m b m ab m In particular reduction modulo m is a surjective ring homomorphism Exercise 15 Most Important 1 Justify the preceding proposition to yourself Now that we know Z mZ is a ring we can make the following definition If a Z then a is invertible modulo m iff a m is a unit of Z m2Z i e there exists an integer b Z such that ab 1 mod m 2 Using B zout prove that if gcd a m 1 then a is invertible modulo m 3 Prove that if gcd a m gt 1 then there exists c Z such that c 0 mod m but ac 0 mod m Hint Consider m gcd a m 4 Deduce from part 3 that if gcd a m gt 1 then a is not invertible modulo m H
5. Xorz Y The complement of Y in X is the set 3 XXY f2E X x Y The empty set or nullset is the set that contains no elements which is denoted Y The notation FX means the number of elements of X i e the cardinality of X 1 1 2 Functions Let f X gt Y be a map We say that X is the domain of f and Y is the codomain or range of f If AC X then the image of A under f is the set 4 f A f a a A CY If BC Y then the preimage of B under f is the set 5 f B x X f x B If y Y then mathematicians write f y in place of f 1 y and refer to this set as the preimage of y under f We say that f is injective or an injection iff it sends any pair of distinct elements of X to distinct elements of Y In other words f is injective if and only if for all 71 72 X we have that f 11 f x2 implies x xy We say that f is surjective or a surjection iff f X Y i e every element of Y takes the form f x for some x X Super Useful Fact If X Y are finite of the same cardinality and f X Y is any function then f is injective gt f is surjective Here is another way of thinking about injectivity and surjectivity 6 f is injective lt gt the preimage of any element of Y contains at most one element 7 fis surjective lt gt the preimage of any element of Y contains at least one element We say that f is bijective or a bijection iff it is both injecti
6. of prime numbers and this factorization knows everything about the divisibility properties of the number The theorem that says this is for good reason often called the Fundamental Theorem of Arithmetic Theorem 2 3 Unique Prime Factorization Let p lt po lt be the ascending sequence of prime numbers Then every natural number n can be expressed in the form 29 II i gt 1 for some sequence 1 2 of nonnegative integers only finitely many of which are nonzero Moreover this sequence is uniquely determined by n Proof of the existence of the factorization Consider the set of counterexamples i e the set of all natural numbers that cannot be expressed as a product of primes If is nonempty then it contains a minimal element m We know m can t be prime because a prime is certainly a product of primes So m must be composite The set D of divisors of m that are strictly between 1 and m is nonempty So D has a minimal element p If p is not prime then there is a divisor of p strictly between 1 and p which will also be a divisor of m contradicting the minimality of p Thus p is prime Since m m p is less than m it is a product of primes But now m m p is also a product of primes a contradiction Therefore is empty 11 Remark 2 4 I cherish the above proof because when I was learning elementary number theory I discovered it on my own after learning about the well orde
7. to the result referring to it as the Aureum Theorema or Golden Theorem In the course of his lifetime he published six proofs and wrote down two more Theorem 5 4 Quadratic Reciprocity Let p q be distinct odd primes Then o QO In addition 65 te 22 Proof Stop by my office hours to see a panoply of cool proofs The quadratic reciprocity law gives us an extremely efficient way to compute whether an odd prime p is a quadratic residue modulo a larger prime q Indeed it implies OREO and the value of 4 depends only on the residue class of q modulo p hence on the remainder upon long dividing q by p This remainder might no longer be prime but the Legendre symbol is totally multiplicative so we can break the remainder up into individual primes and compute the Legendre symbols of those etc In short we have Legendre s Algorithm Let p lt q be odd primes To compute 2 compute the prime factorization q qf of the remainder upon long dividing q by p then compute the right hand side of 0 ON i 1 Exercise 29 Compute the Legendre symbol 3 Exercise 30 Here we count and find the solutions of a quadratic congruence in an arbitrary modulus m E N not necessarily prime 1 Show that if p is an odd prime and e N then the number of residual solutions to x mod p is 2 cf Exercise 24 3 2 Show that if e N then the number of residual solutions to z 1 mod 2
8. Compendious Book on Calculation by Completion and Balancing by al Khwarizmi during the zenith of the Abbasid Caliphate This is the book that introduced the idea of solving the equation for x But I would say that abstract algebra really begins with the invention of zero What do I mean by this Abstract algebra is about introducing seemingly useless structural abstractions into mathematics that pay back their worth enormously as more and more theory accumulates around them until their naturality and simplicity can finally be fully appreciated The number 0 was such a concept If we attribute the discovery of 0 to the Indian mathematician Pingala circa 200 BCE then abstract algebra would predate elementary algebra To be fair the notion of an indeterminate variable x was also a revolutionary advance But The Compendious Book seems to have focused on establishing the methods for solving linear and quadratic equations in x rather than cultivating their abstraction in the way that say Galois did centuries later The distinction is quite fine and difficult to communicate We here summarize the most important algebraic structures for this course We will return to them in closer detail in subsections 3 1 and 4 2 1 3 1 Groups A group consists of a set G and a function G x G gt G written a b gt a b and called its law or operation such that the following hold 1 Associativity a x b c a x b x c for a
9. Elementary Number Theory Minh Tam Trinh after Ng Bao Chau University of Chicago Fall 2015 Contents 0 1 Preface 27 September LL Backotound ea da Fae Reese do ort ee BO he aa A Ie A es een ee ee enone a eae a avd Ss ets ee PS 1 1 2 Functions os a oa a AAA eR ER RR Shae ne RE RE ES 1 1 3 Equivalence Relations 0 0 0000 eee ee 1 1 4 Factoring and Series 2 ee 1 2 Classical Proof Techniques 2 0 e 1 2 1 Contradiction s s bi aaia ee 1252 ri ATAN 1 3 Abstract Algebra a s errega ee 131 GfOUps cierra de 1 3 2 Rings and Fields ooo sa sv be we eee os as 6 October Delt Diyisors ir A RR E A Bek a aa a A a a 22 Prime Factorization oceania a a aa 13 October 3 1 Rings of Residues Modulo m e 3 2 Linear Congruences 2 2 ee ee ee 3 3 The Newton Hensel Method e 20 October 4 1 Arithmetic Functions 4 2 Unit Groups Modulom e 27 October 5 1 Criteria for Quadratic Residues a 5 2 Quadratic Congruences oaoa ee O Preface This collection of notes summarizes the first half of the Math 175 course at the University of Chicago in the Fall 2015 quarter Written very hastily it has yet to be proofread carefully All mistakes are attributable to the author not to the instructor The names we give to mathematical objects and theorems may differ from those in JJ The section numbers roughly correspo
10. Using part 4 show that a product of QNR s modulo p is a QR modulo p Tricky Deduce that the Legendre symbol of conductor p is totally multiplicative Unit Groups Modulo m Let G be a finite abelian group with identity e If x G then we write x to denote the composition of k copies of x under the operation of G The order of x is the smallest natural number k such that x e Exercise 25 Euler Fermat Let m N Recall from 1 3 2 that the unit group Z mZ is a finite abelian group under the operation of multiplication Recall from Exercise 15 that it consists of the residue classes a for precisely those a that are relatively prime to m 1 Show that if G is a finite group and g G is fixed then the multiplication by g map x gt gx is a bijection from G to itself Hint What is the inverse 19 2 Setting G Z mZ deduce that if g Z mZ is fixed and 21 T m are all the elements of Z mZ then 57 FO is the same sequence of elements as 58 E pany but in a different order 3 Deduce that g is the identity of Z mZ Hint Using the two sequences in part 2 write the product of all the elements of Z mZ in two different ways Since every element of the group has an inverse you ll be able to cancel a certain term 4 Euler s Theorem Deduce that if a is relatively prime to m then a 1 mod m 5 Fermat s Little Theorem Deduce that if p is prime and pfa then a 1 mo
11. d p The theorems of Euler and Fermat concluding the previous exercise are special cases of Lagrange s Theorem on the orders of subgroups in finite groups Theorem 4 1 Lagrange If G is a finite group and H is a subgroup of G then H divides HG To see why Lagrange s Theorem implies Euler s Let a be relatively prime to m The residues modulo m of the integer powers of a are precisely 1 a a a where is the order of a We see that they form a subgroup of Z mZ By Lagrange we deduce that divides Z mZ m Therefore a a 1 mod m Let G be a group We say that G is cyclic iff all of its elements can be written as powers of a fixed element Such an element is called a generator or primitive root of G For example Z under addition is a cyclic group because each integer is an additive power i e a multiple of 1 This example also shows that there can be multiple generators for a cyclic group Every integer is also a multiple of 1 so 1 are both generators for Z in fact the only generators Another example is Z mZ under addition for any m N Exercise 26 Show that the additive group Z mZ x Z nZ is cyclic if and only if ged m n 1 Hint The Chinese Remainder Theorem Exercise 27 Important Do this exercise without looking at the theorems below For which natural numbers m lt 12 is the unit group Z mZ cyclic Can you give a generator of each such group Exerc
12. dentity of G and if a H then a H Actually the second follows from the first and third Exercise 7 1 Find all the subgroups of Z Hint To get you started 0 is a subgroup 2 Show that Z x Z contains subgroups that do not take the form H x H for some H Ho C Z If G1 G2 are groups then we say that a map f Gi gt G2 is a group homomorphism or group morphism iff 17 F ab f a f b for all a b G1 Intuitively f is a homomorphism iff it sends the operation of G onto that of G2 When it is it necessarily sends the identity of G to that of G2 We say that f is a group isomorphism iff it is a bijective group homomorphism In this case we write G1 Go Exercise 8 Consider the groups formed by Z and R under addition Which of the following are group homomorphisms Of those that do which are isomorphisms 1 The translation map ta Z Z defined by ta n n a where a Z is fixed 2 The scaling map ma Z gt Z defined by m n an where a Z is fixed 3 The scaling map Ma R gt R defined by ma x ax where a R is fixed 4 The map R gt Ryo that sends x e where the operation on Ro x ER x gt 0 is multiplication 1 3 2 Rings and Fields A ring consists of a set R and functions x Rx R gt R where is called its addition and x is called its multiplication such that 1 R forms an abelian group under Its identity under is called the additiv
13. e identity and denoted 0 2 x is associative meaning a x b x c a x b x c for all a b c R 3 There exists an element 1 R called the multiplicative identity or unity such that axl a 1xa for all a R 4 The distributive identities 18 ax b c axb axc 19 b c xa bxa cxa hold for all a b c R In this course all rings will be commutative meaning the multiplication is commutative 4 axb bxa for all a be R Note that the elements of R almost form an abelian group under x The only obstacle is that not every element may have an inverse with respect to x Exercise 9 1 Show that if R is a ring then 0 x a 0 for every a R Hint 0 0 0 2 Deduce that if R is nontrivial meaning 0 1 then 0 cannot have an inverse We say that an element a R is a unit iff it has an inverse b R with respect to x i e a x b 1 We write R for the set of units of R Then by construction R forms an abelian group under x called the unit group of R We say that R is a field iff RX R 0 Exercise 10 Check that the following objects form rings Which of them form fields 1 Z 2 Q 3 R 4 The set R t of polynomials in t with real coefficients 5 Ry x Ro where Ri Re are rings under the addition 20 a1 a2 b1 b2 a1 b1 as ba and the multiplication 21 a1 a2 x by b2 ay x by a2 x ba Henceforth we drop the x notation and write ab in place of a x b If R
14. icates that 37 Up m vp n lt vp a But gcd m n 1 so for all p at least one of v m vp n equals 0 We deduce that 38 Up mn Up m vp n lt Up a for all p meaning mn a as needed Corollary 3 3 Ifn n N are pairwise coprime then the map 39 Z m1 n 32 gt 2 n Z i l that sends d n n nz 3 n is a ring isomorphism Proof Induct on r using the fact that ged n1 n 1 Ny gcd gcd n Nr 2 Nr 1 Nr Exercise 18 If N is any set of natural numbers then we define gcd N to be the largest d N such that d n for all n N We say that the elements of N are jointly coprime iff gcd N 1 Show that if the elements of N are pairwise coprime then they are jointly coprime but that the converse is not true Corollary 3 4 Let f be a polynomial with integer coefficients and for all n N let cy be the number of residue classes x modulo n such that f x 0 mod n If ni n EN are pairwise coprime then Cn n Cn Cn Exercise 19 Systems of Linear Congruences Let m1 m E N be pairwise coprime and let a b Z for 1 lt i lt r In this exercise we show how to find all integers x such that 40 aj b mod m for all i i e how to solve a system of r simultaneous linear congruences modulo pairwise coprime moduli We do this in two parts 1 Local Solution To solve 40 for a single index i In what follow
15. int Suppose ab 1 and consider abc where c is the element from part 3 5 Deduce that the unit group modulo m is 35 Z mZ a m 0 lt a lt m such that ged a m 1 6 Deduce that Z pZ is a field if and only if p is prime In light of part 6 professional number theorists will often write F in place of Z pZ with F standing for field 3 2 Linear Congruences Professor Ng had an amusing story about the apocrypha behind the Chinese Remainder Theorem 13 Exercise 16 Show that a group homomorphism f Gi gt Ga is injective if and only if f x being the identity of G implies x being the identity of G Hint If a b Gi and ey is the identity of G4 then a b if and only if ab e1 where b7 is the inverse of G4 Exercise 17 Show that in general if n N then the map a y gt a is a surjective ring homomorphism Z NZ gt Z nZ Theorem 3 2 Chinese Remainder If m n N are coprime then the map 36 Z mn Z gt Z mZ x Z nZ that sends a mn gt 4 m a n is a ring isomorphism Proof The map is at least a ring homomorphism by Exercise 17 so it remains to check its bijectivity Since both the domain and the codomain have mn elements it suffices by the Super Useful Fact 1 1 2 to prove that the map is injective By Exercise 16 it suffices to show that if a Z satisfies both a 0 mod m and a 0 mod n then it satisfies a 0 mod mn For all prime p Exercise 13 1 ind
16. ise 28 Important While Z mZ forms an abelian group under multiplication Z mZ forms an abelian group under addition being a ring Show that the following maps are uniquely defined group homomorphisms Which are isomorphisms 1 The map Z 4Z gt Z 2Z x Z 2Z that sends 1 4 gt 1 2 1 2 2 The map Z 6Z gt Z 2Z x Z 3Z that sends 1 gt 1 2 1 3 3 The map Z 6Z gt Z 2Z that sends 5 gt 1 2 4 The map Z 7Z gt Z 6Z that sends 3 7 gt 2 6 20 5 The map Z 7Z gt Z 6Z that sends 3 7 gt lL 6 The map Z 12Z gt Z 2Z x Z 2Z that sends 3 12 gt 1 2 0 2 and 5 12 gt O 2 1 2 Theorem 4 2 Structure of Finite Abelian Groups Every finite abelian group is isomorphic to a group of the form 59 Z mZx x Z n Z for some r N and ny n EN Proof See any decent textbook on abstract algebra The power of the following theorem only becomes evident once you remember that the structure of Z mZ is multiplicative cf Cor 3 5 to the Chinese Remainder Theorem Theorem 4 3 Structure of Unit Groups Let p be prime and let e N Then 0 p 2 e 1 60 Z p Z 4 Z 2Z x Z 2 Z p 2 e gt 2 Z p 1Z x Z p 1 Z p odd Proof Interesting but not essential See JJ 6 3 6 4 Corollary 4 4 If p is odd then Z p Z Z p p Z a cyclic group 21 5 27 October 5 1 Criteria for Quadratic Residues Lemma 5 1 Wilson If p is
17. le 1 2 Fix m N Then we can define an equivalence relation on Z by setting a b if and only if m divides a b The corresponding family of subsets of Z is 10 0 mZ 1 mZ m 1 mZ where a mZ denotes the set of integers of the form a mq for some q Z For this particular equivalence relation it is conventional to write 11 a b mod m to mean a b We will revisit this example in 3 1 1 1 4 Factoring and Series Exercise 1 Let x y be indeterminates and let k N 1 How do you factor a 1 2 How do you factor x y 3 How do you factor x 1 for odd k What goes wrong with this pattern for even k Exercise 2 1 Suppose x is an indeterminate Expand 1 a 2a 1 2 2 Using part 1 deduce that if x is a real number and x lt 1 then 12 ltaota 2 converges to a real number as n oo What is this number in terms of xz Exercise 3 1 Prove that 1 1 1 1 1 tes 4 gt 13 m4 1 242 2n 1 2 for all nonnegative integers n You don t need induction 2 Deduce that the harmonic series 14 ie ou ie 20 38 n diverges as n gt co This argument was discovered by Nicole Oresme a French natural philosopher of the late medieval era 1 2 Classical Proof Techniques I use the word classical in the conservative Western sense of known to the intellectual scene of the ancient Greeks 1 2 1 Contradiction I think everyone in the class unders
18. ll a b c G 2 Identity There exists an element e G called the identity such that a e a e x a for all a G 3 Inversion For every a G there exists an element b called the inverse of a such that axb e bxa We say that a group is abelian iff it furthermore satisfies 4 Commutativity a x b b x a for all a b G Exercise 6 Which of the following form groups Of those that do which form abelian groups 1 Z under addition 2 R under addition R under multiplication RA 0 under multiplication 1 1 under multiplication a na e w Gy X G2 where G is a group with the operation under the operation x defined by 15 a1 a2 b1 b2 a1 1 b1 a2 2 bo 7 The set of pairs a1 a2 E R x R such that a 4 0 under the operation x defined by 16 a1 2 b1 b2 arbi a1b2 a2 When the operation is unambiguous from the context mathematicians often drop the x symbol and write ab in place of a x b However if the operation is conventionally referred to as addition like in parts 1 and 2 of the preceding exercise then they always keep the symbol to denote the operation to avoid confusion with multiplication If G is a group then a subgroup of G is a subset H C G that forms a group in its own right with the same operation and identity element This means three things H is closed under the operation i e a b H implies ab H and H contains the i
19. nce every integer is a Z linear combination of a and b 10 Proof Set ao a1 a b in the notation of Exercise 12 Assume without loss of generality that ao gt a The algorithm produces sequences of numbers az and gy that satisfy 26 for all k and such that 28 ao gt 41 gt gt Gn gcd a b for some n The k n 1 case of 26 says 4n 2 Gn 1Gn 1 An So we can express a as a Z linear combination of aj 1 n 2 In general we can express az41 as a Z linear combination of ak 4 1 SO by inductively substituting these expressions back up the ladder we can express an gcd a b as a Zlinear combination of ag a and a b If a b N then the least common multiple lem of a b is the smallest m N such that a m and b m It is denoted lem a b 2 2 Prime Factorization Recall cf 1 3 2 that the units of Z are the integers that have multiplicative inverses that are also integers Hence they are 1 and 1 Let n gt 2 We say that n is prime iff its only positive divisors are 1 and itself We say that n is composite otherwise By construction then Z consists of four kinds of numbers 1 The additive identity 0 2 The units 1 3 The numbers p where p N is prime 4 The numbers n where n N is composite We will find that the primes are the building blocks of the nonzero non unit integers Any such number factors uniquely as a product
20. nd to weeks of the quarter Throughout we use the following conventions N 1 2 3 the set of natural numbers Z 0 1 2 the set of integers Q a b a b Z and b 0 the set of rational numbers R the set of real numbers This course is about the algebraic relationships that exist between integers or more poetically the patterns and symmetries hidden within Z and Q To students Please do not feel as though these notes can only be read front to back They were written to be a user s manual not a narrative 1 27 September 1 1 Background Although everyone enrolled is required to have taken a previous course in proof based mathematics I wanted to review the standard toolbox of notations and techniques you should know I am doing this because of the wide range of backgrounds that seem to be present among the students 1 1 1 Sets The notation x X is to be read x is an element of the set X If P is a property of elements of S then the notation x X x satisfies P means the set of all elements x X such that x satisfies P If X Y are sets then the notation X C Y is to be read X is a subset of Y The product of X and Y is the set X x Y whose elements are ordered pairs x y such that x X and y Y If X Y are both subsets of another set Z then we define their intersection to be 1 XNY 4 2 Z 2 Xand Y and their union to be 2 XUY 42 Z 2
21. ny N are pairwise coprime then the map 44 Z m 1 2 gt Z n 2 i 1 that sends d n n gt n n ts a group isomorphism 3 3 The Newton Hensel Method In calculus Newton s method is an algorithm to approximate the zero of a smooth function f R gt R Namely one first guesses a nearby approximation x then if f is sufficiently well behaved the actual zero will be lim zg where 45 Troi Ep f we f 21 15 for all k The number theorist Kurt Hensel discovered an analogous method to solve polynomial congruences more efficiently when the modulus is a large prime power p Namely one starts with a solution to f 0 modulo p then lifts it to a solution or solutions modulo p then lifts those to solutions modulo p and so on using a formula similar to Newton s Like Newton s method the lifting step can fail if f is not well behaved The difference is that while Newton s method only gives a unique xz at the kth step Hensel s method allows the possibility that in going from say p to p there might be multiple lifts of a given solution In what follows let us recall for the reader that if f is a polynomial with real coefficients say f t ao a1t ant then its formal derivative with respect to t is 46 f 6 a 2agt nant For all z R we find that 47 f a e f x ao alx anla e a09 Faye anr q
22. ome aj p E Z Now using 47 51 0 f k fur 0004 f Ek par p r f a mod p from which 0 az k f k mod p Rearranging we obtain 6 axyx mod p from which p 6 f ar yx mod p 1 The result follows 16 Exercise 20 Suppose instead that in the notation of Theorem 3 6 we have f a 0 mod p but f z 0 mod p as well Show that 1 If f a 0 mod p 1 then f x pt8 0 mod p t for all 6 Z i e rx has p distinct lifts to solutions of f modulo p This is what we meant by Hensel s method allowing the possibility of multiple lifts from p to p 2 If f 2x 0 mod p t then f a p d 0 mod p for all Z i e xy does not lift to any solution of f modulo p This is what we meant by Hensel s method failing when f is not sufficiently well behaved Exercise 21 1 Find all z Z such that xz 1 0 mod 11 2 Using part 1 find all x such that z 1 0 mod 112 17 4 20 October 4 1 Arithmetic Functions An arithmetic function is just a function from N into R or even more generally into the complex numbers C Equivalently it can be pictured as an infinite sequence in R or C indexed by the natural numbers We say that an arithmetic function f N gt R is multiplicative iff for all coprime m n N we have 52 f mn f m f n We say that f is totally multiplicative iff 52 holds even without
23. prime then p 1 1 mod p Proof Every element of Z pZ has a distinct inverse except for the elements 1 and 1 By pairing together the elements that do have distinct inverses we find that they cancel out in the product over all elements of Z pZ so that we re left with 1 1 p 1 p il Proposition 5 2 Euler s Criterion If p is prime and p a then 2 a F mod p Proof There are p 1 residues modulo p and Wilson s Lemma says that their combined product is 1 If a is a QNR then the residue class 2 will always be distinct from the residue class a p 2 so pairing up these classes we find that the product over all elements of Z pZ is also equal to a 2292 pol 61 aisa QNR a 1 mod p If a is a QR then a b mod p for some b Z so by Fermat s Little Theorem a4 0 bP 1 mod p Pi 62 aisa QR a 1 mod p The proof is complete Proposition 5 3 Gauss s Lemma Let p be an odd prime If pi a then 63 5 ya N M1 where M n np Prl p 1 n 2 p Proof This is Theorem 7 9 in JJ 5 2 Quadratic Congruences The law of quadratic reciprocity was known to Euler but astonishingly he was not able to prove it Gauss apparently discovered the first proof around the age of 19 it was published in his monumental Disquisitiones Arithmeticae He attached great personal significance
24. ring principle On the other hand I find the justification of the uniqueness of the factorization to be tedious and not especially enlightening so I ve omitted it If n N and pis a prime then we write v n to denote the exponent for p in the prime factorization of n Exercise 13 1 Convince yourself that b a if and only if vp b lt vp a for all prime p 2 Convince yourself that v ged a b min vp a vp b What is the analogous statement for lem a b 3 From part 2 deduce that gcd a b lem a b ab for all a b N 4 From part 2 deduce a criterion for the coprimality of a and b in terms of the values vp a and up b Corollary 2 5 Euclid There are infinitely many primes Proof Suppose there are only finitely many primes say p lt lt pr Let 30 N pipo Pr 1 Then no prime divides N so the exponents in the prime factorization of N must all be zero But now N 1 whereas each p is larger than 1 a contradiction Proof of Euler Suppose there are only finitely many primes Then by unique prime factorization we can check that CoO 1 1 31 IEDR A 1 1 p Em where the left hand side converges because it is a finite product But the right hand side diverges by Exercise 3 a contradiction Exercise 14 Show that there are infinitely many primes of the form 64 5 where k Z Hint Look at 2I lrer p 1 where p is the set of primes of the form 6k 5
25. s let d gcd a m 14 a Using B zout prove that a x b mod m has a solution in x if and only if d divides b b Check that if d bi then 41 aix b mod m gt a d c b d mod m d In other words after replacing m a b with m d a d b d we reduce to solving 40 in the case where gcd a m 1 c Check that if gcd a m 1 then 40 has a unique solution Hint Exercise 15 2 2 Global Solution Having solved 40 for individual indices it remains to show that if we can construct 1 r Z such that 42 QT bi mod mi then we can construct x Z such that x x mod m as this x will solve 40 a Let M m m m Convince yourself that we can find N N such that M N 1 mod mi for all 2 b Convince yourself that x x M N rM N is the fellow you want 3 Practice a Find all x Z such that 15x 21 mod 24 b Find all x Z such that x 1 mod 3 x 2 mod 4 x 3 mod 5 x 4 mod 7 simultaneously The Chinese Remainder Theorem has a multiplicative analogue for unit groups To explain it observe that if f Ry gt Rg is a ring homomorphism then f restricts to a group homomorphism f R gt R In particular if f is bijective then the same is true of its inverse so if f is a ring isomorphism then f is a group isomorphism By this argument Cor 3 3 implies Corollary 3 5 Ifn
26. sor gcd of a b is the largest d N such that d a and d b It is denoted gcd a b We say that a and b are coprime or relatively prime iff gcd a b 1 i e the only positive common divisor of a and b is 1 Exercise 12 In this exercise we demonstrate that there s a fast algorithm to compute the gcd of any two natural numbers a b 1 Prove that if a b q r Z such that a bq r then the common divisors of a and b are precisely the common divisors of b and r 2 Deduce that if a b r gt 1 and a bq r then gcd a b gcd b r Part 2 implies Euclidean Algorithm If we want to compute the gcd of two numbers a b N where a gt b then we can replace a with b and replace b with the remainder upon long dividing a by b as long as this remainder is nonzero In practice it looks like this 3 Let ay as N where ay gt aj For k N let q and azy1 be defined inductively as the quotient and remainder respectively upon long dividing az 1 by ax 26 Ak 1 AkQk 0Ok 1 Then gcd ao a1 gcd a1 a2 gcd n_ 1 Gn Gn where an is the last nonzero term in the sequence ay gt a gt which does in fact eventually reach zero by the well ordering principle 4 Using part 3 compute gcd ao a1 for ay a1 2771 1360 3003 770 Theorem 2 2 B zout For all a b N there exist x y Z such that 27 ax by gcd a b In particular if a and b are coprime then 1 and he
27. tands how this works so this is the only thing I want to mention about it RJeductio ad absurdum which Euclid loved so much is one of a mathematician s finest weapons It is a far finer gambit than any chess gambit a chess player may offer the sacrifice of a pawn or even a piece but a mathematician offers the game G H Hardy in A Mathematician s Apology Disclaimer I disagree strongly with a number of other things Hardy says in that book On the other hand Hardy was in a very melancholic state of mind when he wrote it 1 2 2 Induction In the first week we proved that the principle of induction and the well ordering principle can be deduced from each other Anyway both are true Principle of Induction If P n means property P holds for the natural number n then to prove P n for all n N it suffices to prove the following two statements lIn this document induction always means strong induction 1 Base case P 1 holds 2 Inductive step Given any n N if P m holds for all m lt n then P n holds Exercise 4 Prove by induction that 13 2 n n n 2 for all n N Well Ordering Principle Every nonempty subset of N contains a smallest element Exercise 5 Using the well ordering principle show that every nonempty subset of N that is bounded above has a largest element 1 3 Abstract Algebra Traditionally the subject of algebra began with the writing of The
28. the Legendre symbol of a over p or a on p In Exercise 24 we ll show that it is totally multiplicative as a function of a 18 Exercise 22 Use unique prime factorization to do the following 1 2 Prove that oj is multiplicative for all k gt 0 You might need parts 4 and 5 of the next exercise Convince yourself that a multiplicative arithmetic function is determined by its behavior on prime powers As a special case a totally multiplicative function is determined by its behavior on primes Exercise 23 Important 1 2 What is y p for prime p What is p for prime p and arbitrary k N Using the multiplicativity of y deduce a formula for y n in terms of the unique prime factorization of n What is og p for prime p What is o p prime p and arbitrary N Using the multiplicativity of og deduce formulae for co n and o1 n in terms of the unique prime factorization of n Exercise 24 Important Let p be a prime We write F Z pZ 1 4 2 Show that a product of QR s modulo p is a QR modulo p Deduce that the set of QR s modulo p forms a subgroup of Z pZ Show that the product of a QR and a QNR modulo p is a QNR modulo p Show that if p gt 3 then the homomorphism F gt F that sends x gt x is 2 to 1 i e every element in the image has exactly 2 elements in its preimage Using part 3 deduce that there are as many nonzero QR s as QNR s modulo p
29. the assumption that m and n are coprime In general we really only ever care about arithmetic functions when they re multiplicative or totally multiplicative Example 4 1 Here is a bestiary of multplicative arithmetic functions in number theory 1 The constant function that sends every natural number to 1 2 The Euler totient function p defined by 53 p n Ha EeN a lt mn and gcd a n 1 By Exercise 15 54 y n Z n2 so y is multiplicative by Cor 3 3 of the Chinese Remainder Theorem It is not totally multiplicative because p 4 2 but p 2 1 3 Fix k gt 0 The kth power divisor function op is defined by 55 on n y d n where the sum runs over positive divisors of n For example co computes the number of positive divisors of n whereas 0 computes their sum For this reason go is called the divisor counting function whereas cg is called simply the divisor function and alternatively denoted o 4 Fix a prime p If a Z then we say that a is a quadratic residue QR modulo p if a b mod p for some b Z and we say that a is a quadratic non residue QNR modulo p otherwise We define the Legendre symbol of conductor p to be the function 5 such that 1 a 0 and a is a QR modulo p 56 5 lt 1 a 0and ais a QNR modulo p P 0 a 0 modp Despite the awful notation 2 does not mean the rational number a p When we discuss the Legendre symbol in person we usually pronounce 2 as
30. ve and surjective If f is bijective then every element y Y has a unique preimage in X so we can define the inverse of f to be the map f Y gt X that sends y to this unique preimage As we see above the notation f7 is used in several slightly different ways This is an example of what s called abuse of notation Certain abuses of notation are tolerated in mathematical writing because they have proven more convenient than harmful 1 1 3 Equivalence Relations If X is a set then to give an equivalence relation on X is to give a family of pairwise disjoint subsets called equivalence classes whose union is X Example 1 1 This one was suggested by Professor Ng Let Monday be the set of all Mondays in human history and let Tuesday Sunday be defined similarly Then 8 Monday Tuesday Sunday gives an equivalence relation on the set of dates in human history because each calendar date has a unique day name Oftentimes when working with equivalence relations we introduce a symbol like or or to indicate that two elements of X belong to the same equvalence class Naturally we say that such elements are equivalent We write X or an analogous notation to denote the set of equivalence classes There is a natural map 9 X gt X that sends every element x X to the unique equivalence class containing x We often denote this class by 1 so that x y is equivalent to z y by definition Examp
Download Pdf Manuals
Related Search