Further Reading: Modular Arithmetic

Annotated pointers for going deeper. Start with the textbook sections to consolidate, then branch out as your interest (the algorithms, the cryptography, or the pure number theory) pulls you. All sources below are Tier-1 (canonical, verifiable) or clearly attributed Tier-2.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §4.1–4.4 The market-standard treatment of congruences, the Chinese Remainder Theorem, Fermat's little theorem, and Euler's theorem, with a deep, well-graded exercise bank. If you want more drill on solving linear congruences and CRT systems than this chapter provides, start here.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), "Number Theory" chapters Freely available. The most CS-flavored presentation in print: modular arithmetic is developed specifically as the substrate for cryptography, building straight to RSA with the same "why a programmer needs this" spirit as our chapter. The single best companion read for §§23.3–23.6.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 4 ("Number Theory") Congruences, the totient $\phi$, and Möbius inversion treated as working tools for manipulating sums and counting. Denser, but it rewards the effort and shows where the totient comes from rather than just asserting $\phi(pq) = (p-1)(q-1)$.

On the algorithms (inverses, CRT, fast exponentiation)

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapter 31 ("Number-Theoretic Algorithms") The canonical algorithmic reference for everything in this chapter: the extended Euclidean algorithm, modular inverses, solving modular linear equations, the CRT, and modular exponentiation by square-and-multiply — all with careful running-time analysis. Read §31.6 alongside our §23.5 to see the $O(\log e)$ bound proved formally.

Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.), §4.3.2 and §4.5.3 The deep reference on the residue number systems of Case Study 2 and on the analysis of the Euclidean algorithm. §4.3.2 develops modular (residue) arithmetic for fast multiprecision computation; consult it if the carry-free parallelism intrigued you.

On the cryptography (where this all goes)

Katz & Lindell, Introduction to Modern Cryptography (3rd ed.), the number-theory and RSA chapters The rigorous bridge from this chapter's mathematics to real public-key cryptography. It states exactly which number-theoretic assumptions RSA rests on (factoring, the RSA problem) and why Euler's theorem makes decryption correct — the formal version of our §23.6 closing paragraph. Read it before or alongside Chapter 25.

"New Directions in Cryptography" (Whitfield Diffie & Martin Hellman, IEEE Transactions on Information Theory, 1976) Tier 2 — foundational paper, widely available. The paper that introduced public-key cryptography and the trapdoor idea (§23.6's threshold concept). Short, historic, and surprisingly readable; skim it to see the moment the whole field began.

Visual and intuitive

Khan Academy, "Cryptography" unit (Journey into Cryptography) Free. Gentle, animated introductions to modular arithmetic, the Euclidean algorithm, and primality — good for a second, more visual pass over §§23.1–23.3 if the notation moved fast the first time.

3Blue1Brown, "Why do prime numbers make these spirals?" and related number-theory videos (YouTube) Free. Visual intuition for residues, coprimality, and the structure of $\mathbb{Z}_n$. Best watched after §23.1 to attach pictures to the residue-class idea.

A note on history

Sun Tzu's Mathematical Classic (孫子算經), 3rd–5th century CE Tier 2 — primary historical source, available in translation. The original statement of the remainder puzzle solved in §23.4. Worth a glance to see that the Chinese Remainder Theorem is genuinely two thousand years old, long predating the algebra we now use to prove it.

Suggested order

  1. Re-read §§23.1–23.6 here, then do Rosen §§4.1–4.4 exercises for drill on congruences and the CRT.
  2. Read the MIT 6.042 number-theory chapters for the CS-to-crypto framing.
  3. Read CLRS Chapter 31 (especially §31.6–31.7) to see the algorithms and their running times proved.
  4. If Case Study 2 hooked you, dip into Knuth Vol. 2 §4.3.2 on residue arithmetic.
  5. Save Katz & Lindell and the Diffie–Hellman paper for the run-up to Chapter 25, where you implement RSA.