Further Reading: Number Theory Foundations

Annotated pointers for going deeper into divisibility, primes, the Euclidean algorithm, and unique factorization. Start with the textbook sections, then follow whichever thread — proof technique, algorithms, or the road to cryptography — pulls hardest. All sources are Tier 1 (verified canonical) or Tier 2 (clearly attributed).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §4.1–4.4 The market-standard development of divisibility, primes, the Division Algorithm, gcd/lcm, the Euclidean algorithm, and the Fundamental Theorem of Arithmetic — in the same order as this chapter, with a deep, well-graded exercise bank. The place to go for additional drill problems.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), "Number Theory" chapters Freely available. The most CS-flavored treatment in print: gcd and the Euclidean algorithm are developed with an eye toward algorithms and cryptography from the start, and the "Pulverizer" is their name for the extended Euclidean algorithm you met in §22.5. The companion that matches this book's spirit most closely.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 4 ("Number Theory") Denser and more playful: divisibility, primes, factorial factorizations, and a famously thorough treatment of gcd identities. Rewards a second pass after you are comfortable with the basics.

On the algorithms (gcd, sieve, complexity)

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapter 31 ("Number-Theoretic Algorithms") The canonical algorithmic reference for this chapter's procedures: Euclid's algorithm, the extended Euclidean algorithm, and the $O(\log(\min(a,b)))$ running-time analysis (including the Fibonacci worst-case bound). Read §31.1–31.2 alongside §§22.4–22.5.

Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §4.5.2–4.5.3 (Vol. 2; the book cites Vol. 1 elsewhere.) The definitive deep dive on the Euclidean algorithm, including the precise analysis tying its worst case to consecutive Fibonacci numbers and the history of the algorithm. For when you want the complete story behind §22.4's complexity remark.

The road to cryptography

Katz & Lindell, Introduction to Modern Cryptography (3rd ed.), the number-theory background chapter The bridge from this chapter to RSA. It develops exactly the gcd/Bézout/modular-inverse machinery you built here and then uses it to define and analyze RSA — the destination of Part IV. Skim now for motivation; return after Chapter 23.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the number theory chapter Freely available. A gentle, well-illustrated alternative explanation of divisibility, the Euclidean algorithm, and unique factorization, with worked examples at a relaxed pace. A good second voice if any section here felt too fast.

Classic and historical

Euclid, Elements, Book VII (Propositions 1–2) and Book IX (Proposition 20) Freely available in translation. The original source: Book VII gives the Euclidean algorithm (Propositions 1–2), and Book IX, Proposition 20 is the infinitude-of-primes proof reproduced in §22.2. Reading the ancient phrasing makes vivid how little the core ideas have changed in 2,300 years. (Tier 2 — the canonical attribution is secure; specific proposition numbering varies slightly by edition.)

G. H. Hardy, A Mathematician's Apology (1940) Tier 2. The famous (and famously mistaken) declaration that number theory is "useless" — the remark the chapter's Overview rebuts. A short, beautifully written essay; read it to appreciate the irony that this "useless" subject now secures the internet.

Fun and exploration

The On-Line Encyclopedia of Integer Sequences (oeis.org): primes (A000040) and Euler totient (A000010) Tier 2 (community-maintained reference). Browse the prime sequence and the totient sequence (the $\phi(26) = 12$ you computed in Case Study 2 lives here). A rich source of "conjecture and test, then prove" material in the spirit of the exercises' Part F.

Suggested order

  1. Re-read §§22.1–22.6 here, then work Rosen §§4.1–4.4 exercises for drill.
  2. Read the MIT 6.042 number-theory chapter for the CS framing of gcd and the "Pulverizer."
  3. Read CLRS §31.1–31.2 for the algorithmic and complexity view (pair it with Exercise 22.33).
  4. Skim Katz & Lindell's background chapter to see where all of this is heading (RSA), then come back for Chapter 23.
  5. Save Concrete Mathematics Chapter 4 and Knuth Vol. 2 §4.5 for a deeper second pass.