Math 453 Elementary Number Theory Definitions and Theorems Class Notes Spring 2011 A J Hildebrand Version 5 4 2011 Contents About these notes 3 1 Divisibility and Factorization 4 1 1 Divisibility 4 1 2 Primes 4 1 3 The greatest common divisor 5 1 4 The least common multiple 6 1 5 The Fundamental Theorem of Arithmetic 6 1 6 Primes in arithmetic progressions 8 2 Congruences 9 2 1 Definitions and basic properties applications 9 2 2 Linear congruences in one variable 10 2 3 The Chinese Remainder Theorem 10 2 4 Wilson s Theorem 11 2 5 Fermat s Theorem 11 2 6 Euler s Theorem 12 3 Arithmetic functions 13 3 1 Some notational conventions 13 3 2 Multiplicative arithmetic functions 13 3 3 The Euler phi function and the Carmichael Conjecture 14 3 4 The number of divisors functions 15 3 5 The sum of divisors functions and perfect numbers 15 3 6 The Moebius function and the Moebius inversion formula 16 3 7 Algebraic theory of arithmetic function 17 1 Math 453 Definitions and Theorems 3 8 5 4 2011 A J Hildebrand Arithmetic Functions Summary Table 4 Quadratic residues 18 19 4 1 Quadratic residues and nonresidues 19 4 2 The Legendre symbol 19 4 3 The law of quadratic reciprocity 20 5 Primitive roots 21 5 1 The order of an integer 21 5 2 Primitive roots 21 5 3 The Primitive Root Theorem 22 6 Continued fractions 23 6 1 Definitions and notations 23 6 2 Convergence of infinite continued fractions 23 6 3 Properties of Convergents 24 6 4 Expansions of real numbers into continued fractions 25 7 Topics in Computational Number Theory 26 7 1 Some Basic Concepts 26 7 2 Primality Tests 26 7 3 The RSA Encryption Scheme 28 2 Math 453 Definitions and Theorems 5 4 2011 A J Hildebrand About these notes One purpose of these notes is to serve as a handy reference for homework problems and especiallly for proof problems The definitions given here e g of divisibility are the authoritative definitions and you should use those definitions in proofs The results stated here are those you are free to use and refer to in proofs in general anything else e g a theorem you might have learned in high school is not allowed Another purpose is to serve as a cheat review sheet when preparing for exams The definitions and theorems contained in these notes are those you need to know in exams Finally the notes may be useful as a quick reference or refresher on elementary number theory for those taking more advanced number theory classes e g analytic or algebraic number theory The notes are loosely based on the Strayer text though the material covered is pretty standard and can be found in minor variations in most undergraduate level number theory texts The chapters correspond to those in Strayer but I have made a few small changes in the subdvision of the chapters The definitions and results can all be found in some form in Strayer but the numbering is different and I have made some small rearrangements for example combining several lemmas into one proposition demoting a theorem in Strayer to a proposition etc The goal in doing this was to streamline the presentation by having several layers of results with a clear delineation between the various types of results Theorems Those are the key results usually with descriptive names attached e g Fundamental Theorem of Arithmetic These results typically have more difficult proofs often well above homework level Starred theorems Results whose statement you should know but whose proof is beyond the scope of an undergraduate number theory course are indicated by an asterisk A typical example is the Prime Number Theorem Propositions A proposition typically collects some simple but very useful properties of a concept The proofs are generally on the easy side and many but not all are at a level that would be reasonable to ask for in an exam Corollaries A corollary is attached to a particular theorem or proposition and presents a simple consequence of the theorem or restates the theorem in a special case The derivation of a corollary from the corresponding theorem is usually easy and often immediate Lemmas A lemma is an auxiliary result that is needed usually for the proof of a theorem Lemmas are rarely of interest in their own right and therefore in general not worth memorizing in contrast to the other theorem like structures Since I do not include the proofs here I have generally avoided stating lemmas that arise in those proofs If a result that is stated as Lemma in Strayer is important in its own right and worthy of memorizing I have elevated it to the status of a Proposition or Theorem 3 Math 453 Definitions and Theorems 1 5 4 2011 A J Hildebrand Divisibility and Factorization 1 1 Divisibility Definition 1 1 Divisibility Let a b Z We say that a divides b equivalently a is a divisor of b or b is divisible by a or a is a factor of b if there exists c Z such that b ac We write a b if a divides b and a b if a does not divide b Proposition 1 2 Elementary properties of divisibility i Transitivity Let a b c Z If a b and b c then a c ii Linear combinations Let a b c Z If a b and a c then a bn cm for any n m Z In particular if a b and a c then a b c and a b c iii Size of divisors Let a b Z with b 6 0 If a b then a b In particular any positive divisor a of a positive integer b must fall in the interval 1 a b iv Divisibility and ratios Let a b Z with a 6 0 Then a b holds if and only if b a Z Definition 1 3 Greatest integer function For any x R the greatest integer function x is defined as the greatest integer m satisfying m x An alternative notation for x is bxc the floor function Theorem 1 4 Division Algorithm Given a b Z with b 0 there exist unique q r Z such that a qb r and 0 r b Moreover q and r are given by the formulas q a b and r a a b b 1 2 Primes Definition 1 5 Primes and composite numbers Let n N with n 1 Then n is called a prime if its only positive divisors are 1 and n it is called composite otherwise Equivalently n is composite if it can be written in the form n ab with a b Z and 1 a n and hence also 1 b n and n is prime otherwise Remark The number 1 is not classified in this manner i e 1 is neither prime nor composite Proposition 1 6 Existence of prime factors Let n N with n 1 Then n has at least one prime factor possibly n …