A Friendly Introduction to Number Theory

A Friendly Introduction to Number Theory is an introductory undergraduate text designed to entice non-math majors into learning some mathematics, while at the same time teaching them how to think mathematically. The exposition is informal, with a wealth of numerical examples that are analyzed for patterns and used to make conjectures. Only then are theorems proved, with the emphasis on methods of proof rather than on specific results. Starting with nothing more than basic high school algebra, the reader is gradually led to the point of producing their own conjectures and proofs, as well as getting some glimpses at the frontiers of current mathematical research.

Instructors : To receive an evaluation copy of A Friendly Introduction to Number Theory , send an email request to:
Evan St Cyr at Pearson.
Please include your title and full mailing address.

Click on the links for the following material.

• Table of Contents, Preface, and Introduction
• Chapters 1–6
  • Chapter 1: What Is Number Theory?
  • Chapter 2: Pythagorean Triples
  • Chapter 3: Pythagorean Triples and the Unit Circle
  • Chapter 4: Sums of Higher Powers and Fermat's Last Theorem
  • Chapter 5: Divisibility and the Greatest Common Divisor
  • Chapter 6: Linear Equations and the Greatest Common Divisor
  • Chapter 47: The Topsy-Turvy World of Continued Fractions
  • Chapter 48: Continued Fractions and Pell's Equation
  • Chapter 49: Generating Functions
  • Chapter 50: Sums of Powers
  • Appendix A: Factorization of Small Composite Integers
  • Appendix B: A List of primes
  • Exercise 18.4
  • Exercise 18.7
  • Exercise 19.8
  • Exercise 22.7

  Errata for the 4th edition. (Errata for the 3rd edition is also available.)

  • There is a new chapter on mathematical induction (Chapter 26).
  • Some material on proof by contradiction has been moved forward to Chapter 8. It is used in the proof that a polynomial of degree d has at most d roots modulo p . This fact is then used in place of primitive roots as a tool to prove Euler's quadratic residue formula in Chapter 21. (In earlier editions, primitive roots were used for this proof.)
  • The chapters on primitive roots (Chapters 28–29) have been moved to follow the chapters on quadratic reciprocity and sums of squares (Chapters 20–25). The rationale for this change is the author's experience that students find the Primitive Root Theorem to be among the most difficult in the book. The new order allows the instructor to cover quadratic reciprocity first, and to omit primitive roots entirely if desired.
  • Chapter 22 now includes a proof of part of quadratic reciprocity for Jacobi symbols, with the remaining parts included as exercises.
  • Quadratic reciprocity is now proved in full. The proofs for (-1| p ) and (2| p ) remain as before in Chapter 21, and there is a new chapter (Chapter 23) that gives Eisenstein's proof for ( p | q )( q | p ). Chapter 23 is significantly more difficult than the chapters that precede it, and it may be omitted without affecting the subsequent chapters.
  • As an application of primitive roots, Chapter 28 discusses the construction of Costas arrays.
  • Chapter 39 includes a proof that the period of the Fibonacci sequence modulo p divides p –1 when p is congruent to 1 or 4 modulo 5.
  • There are many new exercises scattered throughout the text.
  • A flowchart giving chapter dependencies is included on page ix.
  • Number theory is a vast and sprawling subject, and over the years this book has acquired many new chapters. In order to keep the length of this edition to a reasonable size, Chapters 47–50 have been removed from the printed version of the book. These omitted chapters are freely available by clicking the following link: Chapters 47–50. The online chapters are included in the index.

  To save time and eliminate typing errors, you can use this web page to copy and paste the numerical data for the following exercises.

  Exercise 18.4 Here are two longer messages to decode if you like to use computers.
  (a) You have been sent the following message:
  

  5272281348, 21089283929, 3117723025, 26844144908, 22890519533,
  26945939925, 27395704341, 2253724391, 1481682985, 2163791130,
  13583590307, 5838404872, 12165330281, 28372578777, 7536755222.

  It has been encoded using

  p = 187963, q = 163841, m = pq = 30796045883, and k = 48611.

  Decode the message.

  (b) You intercept the following message, which you know has been encoded using the modulus

  m = 956331992007843552652604425031376690367 and exponent k = 12398737.

  Break the code and decipher the message.

  821566670681253393182493050080875560504,
  87074173129046399720949786958511391052,
  552100909946781566365272088688468880029,
  491078995197839451033115784866534122828,
  172219665767314444215921020847762293421.

  Exercise 18.7 Write a computer program implementing one of the factorization methods that you studied in the previous exercise, such as Pollard's ρ method, Pollard's p -1 method, or the quadratic sieve. Use your program to factor the following numbers.
  (a) 47386483629775753
  (b) 1834729514979351371768185745442640443774091

  Exercise 19.8 Program the Rabin-Miller test with multiprecision integers and use it to investigate which of the following numbers are composite.
  (a) 155196355420821961
  (b) 155196355420821889
  (c) 285707540662569884530199015485750433489
  (d) 285707540662569884530199015485751094149

  Exercise 22.7 For this exercise, use the ElGamal cryptosystem described in Exercise 22.6.
  (a) Bob wants to use Alice's public key a = 22695 for the prime p = 163841 and base g = 3 to send her the message m = 39828. He chooses to use the random number r = 129381. Compute the encrypted message ( e 1 , e 2 ) he should send to Alice.
  (b) Suppose that Bob sends the same message to Alice, but he chooses a different value for r . Will the encrypted message be the same?
  (c) Alice has chosen the secret key k = 278374 for the prime p = 380803 and the base g = 2. She receives a message (consisting of three message blocks)

  (61745, 206881), (255836, 314674), (108147, 350768)

  from Bob. Decrypt the message and convert it to letters using the number-to-letter conversion table in Chapter 18.

  • The Prime Number Page: Lots of interesting facts about prime numbers.
  • GIMPS: The Great Internet Mersenne Prime Search.
  • The Number Theory Web: A treasure trove of links to people, articles, and news related to number theory. Aimed mainly towards professional mathematicians, but there is something for everyone here.

  No book is ever free from error or incapable of being improved. I would be delighted to receive comments, good or bad, and corrections from my readers. You can send mail to me at