Transcription of 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.
2 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.) 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 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?
4 7. Is there a fast algorithm for factoring large integers?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.
5 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. 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
6 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. 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.
7 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.
8 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. 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.
9 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. ByTrichotomy, eitherd < nord=nord > n. We will show that thed > ncaseis not possible.
10 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.
