Elementary Number Theory - Joshua

1 Elementary Number TheoryA revision by Jim Hefferon, St Michael s College, 2003-Decof notes by W. Edwin Clark, University of South Florida, 2002-DecLATEX source compiled on January 5, 2004 by Jim restriction claimed by W. Edwin 2002: Copyleftmeans thatunrestricted redistribution and modification are permitted, provided that all copiesand derivatives retain the same permissions. Specifically no commerical use of thesenotes or any revisions thereof is permitted. iiPrefaceMathematics is the queen of sciences andarithmetic the queen of mathematicsCarl Friedrich GaussNumber Theory , known to Gauss as arithmetic, studies the properties of theintegers:.. 3, 2, 1,0,1,2,3.. Although the integers are familiar, andtheir properties might therefore seem simple, it is instead a very deep example, here are some problems in Number Theory that remain unsolved.(Recall that aprime numberis an integer greater than 1 whose only positivefactors are 1 and the Number itself.)

2 Note that these problems are simple tostate just because a topic is accessibile does not mean that it is (Goldbach s Conjecture) Is every even integern >2 the sum of two primes?2. (Twin Prime Conjecture) Are there are infinitely many twin primes?(Twin primesdiffer by 2, like 11 and 13.)3. Are there infinitely many primes of the formn2+ 1? Of the form 2n 1?(Ones of this form areMersenne primes.) Of the form 22n+ 1? (TheseareFermat primes.)4. Are there infinitely many primes whose digits are all 1 s? (Numbers ofthis form arerepunits.)5. Are there infinitely many perfect numbers? (An integer isperfectif it isthe sum of its proper divisors; 6 is perfect because 1 + 2 + 3 = 6.)6. (3n+ 1 Conjecture) Consider the functionfdefined by:f(n) = 3n+ 1ifnis odd andf(n) =n/2 ifnis even. Does the sequence of iteratesf(n), f(f(n)), f(f(f(n))), ..always contain 1, no matter what startingvaluenis used?7. Is there a fast algorithm for factoring large integers?

3 So the subject is not simple. However it is accessible, and cautionIn some areas a person needs to learn by starting from first princi-ples. The first course in Calculus is like that; students learn limits first to avoidgetting nutty ideas aboutnxn 1, But other areas are best mastered by divingright this book you dive into mathematical arguments. Number Theory is rightfor this in part because of its always keep in mind the caution: do not underestimate the will find this subject hard, albiet require only Calculus I. Even that requirement is not strict(limits come up, as do the rules of logarithm manipultion), so the main purposeof the prerequisite is that we expect that with it comes a certain amount ofmathematical maturity, including familiarity with basic set Theory and somefunction resourcesThe Internet contains much interesting and current infor-mation about Number Theory ; see the Bibliography. The websites by ChrisCaldwell [2] and by Eric Weisstein [13] are especially good.

4 To see what is goingon at the frontier of the subject, you may take a look at some recent issues oftheJournal of Number Theorywhich you will find in any university Divisibility12 Prime Numbers33 Division54 Greatest Common Divisor75 Bezout s Lemma96 The Euclidean Algorithm137 The Fundamental Theorem158 Distribution of Primes199 Fermat Primes and Mersenne Primes2110 The Functions and 2511 Perfect Numbers and Mersenne Primes2912 Congruences3113 Divisibility Tests3514 More Properties of Congruences3715 Residue Classes4116 Zmand Complete Residue Systems4317 Addition and Multiplication inZm4518 The Group of Units47vviCONTENTS19 The Chinese Remainder Theorem5120 Fermat s Little Theorem5321 Probabilistic Primality Tests5522 Representations in Other Bases5723 Computation ofaNmodm5924 Public Key Cryptosystems63A Proof by Induction67B Axioms forZ69C Some Properties ofR71 Chapter 1 DivisibilityIn this book, all numbers are integers, unless specified otherwise.

5 Thus in thenext definition,d,n, andkare DefinitionThe numberddividesthe numbernif there is aksuch thatn=dk. (Alternate terms are:dis adivisorofn, ordis afactorofn, ornisamultipleofd.) This relationship betweendandnis symbolizedd|n. Thesymbold-nmeans thatddoes not that the symbold|nis different from the fraction symbold/n. Itis also different fromn/dbecaused|nis either true or false, whilen/dis arational Theorem (Divisibility Properties)For all numbersn,m, andd,(1)d|0(2) 0|n= n= 0(3) 1|n(4)(Reflexivity property)n|n(5)n|1 = n= 1 orn= 1(6)(Transitivity property)d|nandn|m= d|m(7)(Multiplication property)d|n= ad|an(8)(Cancellation property)ad|ananda6= 0 = d|n(9)(Linearity property)d|nandd|m= d|an+bmfor allaandb(10)(Comparison property)Ifdandnare positive andd|nthend the first item, takek= 0. For the second, if 0|nthenn= 0 k= next item holds because we can takenas thekin the definition. Re-flexivity is similar:n=n 1 shows that it holds. The next property followsimmediately from Basic Axiom 3 forZ, from the first Transitivity, assume thed|nand thatn|m.

6 Thenn=dk1andm=nk2for somek1, k2 Z. Substitute to getm=nk2= (dk1)k2. By theAssociative Property of Multiplication, (dk1)k2=d(k1k2), which shows 1. DIVISIBILITYM ultiplication also follows from associativity. Assume thatd|nso thatn=dk. Thenan=a(dk) = (ad)kshows thatad| Cancellation, assume thata6= 0 and thatad|an. Then there is aksuch thatan= (ad)k. We will show thatn=dk. Assume first thata >0. Bythe Trichotomy Property from the first Appendix, eithern > dkorn=dkorn < dk. Ifn > dkthen we have thatan > a(dk) = (ad)k, which contradicts thisparagraph s assumption thatan= (ad)k. Ifn < dkthenan < a(dk) = (ad)k,also contradicting the assumption. Thereforen=dk, and sod|n. Theargument for thea <0 case is verify Linearity, suppose thatd|nandd|mso thatn=dk1andm=dk2fork1, k2 Z. Thenan+bm=a(dk1) +b(dk2) =d(ak1+bk2) showsthatd|(an+bm).Finally, for Comparison, assume thatd, n >0 andd|n. Thenn=dkfor somek. Observe thatkis positive because the other two are positive.

7 ByTrichotomy, eitherd < nord=nord > n. We will show that thed > ncaseis not possible. Assume thatd > n. Thendk > nkfollows by one of the firstAppendix s Properties of Inequalities. But that givesn > nk, which means thatn 1> n kdespite that fact thatkis positive and so 1 k. This is impossiblebecause it violates the same Property of DefinitionAn integerniseven(or haseven parity) if it is divisible by 2and isodd(or is ofodd parity) LemmaRecall that|a|equalsaifa 0 and equals aifa <0.(1) Ifd|athen d|aandd| a.(2) Ifd|athend||a|(3) The largest positive integer that divides a nonzero numberais|a|. (1), ifd|athena=dkfor somek. It follows thata= ( d)( k)and since dand kare also integers, this shows that d|a. It also followsthat a= ( k)d, and sod| (2), suppose first thatais nonnegative. Then|a|=aand so ifd|athend||a|. Next suppose thatais negative. Since|a|= afor negativea, andsince (1) shows thatd| a, anddtherefore divides|a|.For (3), first note that|a|actually dividesa: in thea 0 case|a||abecausein this case|a|=aand we know thata|a, while in thea <0 case we have thata=|a|( 1), so that|a|is indeed a factor ofa.

8 We finish by showing that|a|is maximal among the divisors ofa. Suppose thatdis a positive Number thatdividesa. Thena=dkfor somek, and also a=d( k). Thusd||a|, whetherais positive or negative. So by the Comparison property of Theorem , wehave thatd |a|.qedChapter 2 Prime DefinitionAn integerp 2 isprimeif it has no positive divisors otherthan 1 and itself. An integer greater than or equal to 2 that is not prime that 1 is neither prime nor LemmaAn integern 2 is composite if and only if it has factorsaandbsuch that 1< a < nand 1< b < 2. The if direction is obvious. For only if , assume thatniscomposite. Then it has a positive integer factorasuch thata6= 1,a6=n. Thismeans that there is abwithn=ab. Sincenandaare positive, so isb. Hence1 aand 1 b. By Theorem ,a nandb n. Sincea6= 1 anda6=nwehave 1< a < n. Ifb= 1 thena=n, which is not possible, sob6= 1. Ifb=nthena= 1, which is also not possible. So 1< b < n, finishing this half of LemmaIfn >1 then there is a primepsuch thatp| the set of all integers greater than 1 that have no primedivisor.

9 We must show thatSis not empty then by the Well-Ordering Property it has a smallestmember; call itm. Nowm >1 and has no prime divisor. Thenmcannot beprime (as every Number is a divisor of itself). Hencemis composite. Thereforeby Lemma ,m=abwhere 1< a < mand 1< b < m. Since 1< a < m, thefactorais not a member ofS. Soamust have a prime divisorp. Thenp|aanda|m, so by Theorem ,p|m. This contradicts the assumption thatmhas no prime divisor. So the setSmust be Theorem (Euclid s Theorem)There are infinitely many , to get a contradiction, that there are only a finitely manyprimesp1= 2, p2= 3, .. , pn. Consider the numberN=p1p2 pn+ 2. PRIME NUMBERSS incep1 2, clearlyN 2. So by Lemma ,Nhas a prime divisorp. That prime must be one ofp1, .. , pnsince that list was assumed to beexhaustive. However, observe that the equationN=pi(p1p2 pi 1pi+1 pn) + 1along with 0 1< pishows by Lemma thatnis not divisible bypi. This isa contradiction; it follows that the assumption that there are only finitely manyprimes is not RemarkEucild s Theorem, and its proof, is often cited as an example ofthe beauty of TheoremIfn >1 is composite thennhas a prime divisorp >1 be composite.

10 Thenn=abwhere 1< a < nand 1< b < claim that at least one ofaorbis less than or equal to n. For if not thena > nandb > n, and hencen=ab > n n=n, which is , without loss of generality, thata n. Since 1< a, by Lemma is a primepsuch thatp|a. Hence, by Transitivity in Theorem , sincea|nwe havep|n. By Comparison in Theorem , sincep|awe havep a can use Theorem to help compute whether an integer is prime. Givenn >1, we need only try to divide it by all primesp n. If none of thesedividesnthennmust be ExampleConsider the Number 97. Note that 97< 100 = 10. Theprimes less than 10 are 2, 3, 5, and 7. None of these divides 97, and so 97 TheoremWhereaandb >0 are integers, there are integersqandr,called thequotientand theremainderon division ofabyb, satisfying these +r0 r < bFurther, those integers are that this result has two parts. One part is that the theorem says thereexists a quotient and remainder satisfying the conditions. The second part isthat the quotient, remainder pair are unique: no other pair of numbers satisfiesthose verify that for anyaandb >0 there exists an appropriate quotientand remainder we need only produce suitable numbers.