Programming challenges

Elementary Number Theory
A revision by Jim Hefferon, St Michael’s College, 2003-Dec of notes by W. Edwin Clark, University of South Florida, 2002-Dec

A L TEX source compiled on January 5, 2004 by Jim Hefferon, jim@joshua.smcvt.edu.

License restriction claimed by W. Edwin Clark. Copyleft 2002: “Copyleft means that unrestricted redistribution and modification are permitted, provided that allcopies and derivatives retain the same permissions. Specifically no commerical use of these notes or any revisions thereof is permitted.”

ii

Preface
Mathematics is the queen of sciences and arithmetic the queen of mathematics Carl Friedrich Gauss

Number theory, known to Gauss as “arithmetic,” studies the properties of the integers: . . . − 3, −2, −1, 0, 1, 2, 3 . . . . Although theintegers are familiar, and their properties might therefore seem simple, it is instead a very deep subject. For example, here are some problems in number theory that remain unsolved. (Recall that a prime number is an integer greater than 1 whose only positive factors are 1 and the number itself.) Note that these problems are simple to state — just because a topic is accessibile does not mean that itis easy. 1. (Goldbach’s Conjecture) Is every even integer n > 2 the sum of two primes? 2. (Twin Prime Conjecture) Are there are infinitely many twin primes? (Twin primes differ by 2, like 11 and 13.) 3. Are there infinitely many primes of the form n2 + 1? Of the form 2n − 1? n (Ones of this form are Mersenne primes.) Of the form 22 + 1? (These are Fermat primes.) 4. Are there infinitely many primeswhose digits are all 1’s? (Numbers of this form are repunits.) 5. Are there infinitely many perfect numbers? (An integer is perfect if it is the sum of its proper divisors; 6 is perfect because 1 + 2 + 3 = 6.) 6. (3n + 1 Conjecture) Consider the function f defined by: f (n) = 3n + 1 if n is odd and f (n) = n/2 if n is even. Does the sequence of iterates f (n), f (f (n)), f (f (f (n))), . . . alwayscontain 1, no matter what starting value n is used? 7. Is there a fast algorithm for factoring large integers? So the subject is not simple. However it is accessible, and beautiful. iii

iv

PREFACE

A caution In some areas a person needs to learn by starting from first principles. The first course in Calculus is like that; students learn limits first to avoid getting nutty ideas about nxn−1 ,But other areas are best mastered by diving right in. In this book you dive into mathematical arguments. Number Theory is right for this in part because of its accessibility. But always keep in mind the caution: do not underestimate the material. You will find this subject hard, albiet rewarding. Prerequisites We require only Calculus I. Even that requirement is not strict (limits come up, as do therules of logarithm manipultion), so the main purpose of the prerequisite is that we expect that with it comes a certain amount of mathematical maturity, including familiarity with basic set theory and some function facts. Other resources The Internet contains much interesting and current information about number theory; see the Bibliography. The websites by Chris Caldwell [2] and by EricWeisstein [13] are especially good. To see what is going on at the frontier of the subject, you may take a look at some recent issues of the Journal of Number Theory which you will find in any university library.

Contents
Preface 1 Divisibility 2 Prime Numbers 3 Division 4 Greatest Common Divisor 5 Bezout’s Lemma 6 The Euclidean Algorithm 7 The Fundamental Theorem 8 Distribution of Primes 9 FermatPrimes and Mersenne Primes 10 The Functions σ and τ 11 Perfect Numbers and Mersenne Primes 12 Congruences 13 Divisibility Tests 14 More Properties of Congruences 15 Residue Classes 16 Zm and Complete Residue Systems 17 Addition and Multiplication in Zm 18 The Group of Units v iii 1 3 5 7 9 13 15 19 21 25 29 31 35 37 41 43 45 47

vi 19 The Chinese Remainder Theorem 20 Fermat’s Little Theorem 21...