Number Theory and Cryptography

learn how to prove classic number theory patterns with induction, including sums of odd numbers equaling squares, triangle numbers, and Gauss’s algebraic and geometric proofs.

Explore the Euclidean algorithm for gcds, prove the Bézout identity, derive extended Euclidean coefficients, and apply Gauss lemma to show gcds are linear combinations of a and b.

Explore modular techniques, including casting out nines and the digit-sum test modulo nine. Apply the alternating-sum criterion modulo eleven and analyze equations with sums of squares modulo four.

Euler shows how to count representations of a positive integer as a sum of distinct positive integers via the infinite product P(X) = ∏ (1+X^k), with coefficients equal to D(n).

Learn when congruence cancellation works, using gcd and inverses to solve a x ≡ b (mod n) and linear congruences with the extended Euclidean algorithm.

Explore solving systems of linear congruences using direct elimination and the Euclidean algorithm, then apply the Chinese remainder theorem to derive all solutions, illustrated by a three-modulus horses problem.

Explore Euler's totient function, derive phi(n) from prime factorization, apply Euler's theorem to compute residues, and see the Chinese remainder theorem in action with practical examples.