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.

Apply Fermat's infinite descent to prove the case n equals four of Fermat's last theorem. Use Pythagorean triples and the fact that a triangle's area cannot be a square.

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 congruences as a foundational tool in number theory and cryptography, using clock models to prove divisibility results and Fermat's little theorem through concrete examples.

Explore modular arithmetic: addition, subtraction, and multiplication under modulo N, with A ≡ B mod N and C ≡ D mod N implying A+C ≡ B+D and AC ≡ BD.

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.

Explore Fermat's little theorem in congruence with primes, tracing its origins in perfect numbers, Euclid's form, Mersenne primes, and Fermat numbers, and set up for Part II proof.

Explore Fermat's little theorem (part 2) with prime p, proving that for any a not divisible by p, a^(p-1) ≡ 1 mod p, and include the case a ≡ 0 mod p.

Discover Euler's approach to Fermat's little theorem, binomial expansions, and the sigma function, then derive that even perfect numbers fit the Euclidean form using multiplicativity.

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).

Euler's proof equates D(N) with O(N): the number of ways N can be written as a sum of distinct integers and as a sum of odd integers via infinite products.

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 the Chinese remainder theorem by solving a system of congruences using the extended Euclidean algorithm, constructing unique solutions modulo the product of moduli, and implementing the method in Python.

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.