Unit 4 Summary

Math for CS · Axiom Academy

Summary Unit 4: Number Theory & Cryptography A complete review of divisibility, modular arithmetic, the great theorems of Fermat and Euler, the Chinese Remainder Theorem, and how they all power modern cryptography. 1. Foundations: Divisibility & Primes Number theory is the study of the integers. Everything in this unit is built on a single relation: does one integer divide another? Key properties of divisibility If and , then for any integers x, y . Primes and the Fundamental Theorem of Arithmetic A prime is an integer p > 1 whose only positive divisors are 1 and p . The famous theorem of Euclid states there are infinitely many primes. 2. The Greatest Common Divisor & Euclid's Algorithm The greatest common divisor is the largest positive integer dividing both a and b . We can compute it without factoring, using a process more than two thousand years old. If a = bq + r , then any common divisor of a and b also divides r , and vice versa. So , and the remainders strictly decrease, so the process terminates. For any integers a, b there exist integers x, y such that . By back-substitution through the Euclidean steps, you can construct x, y explicitly. This is how modular inverses are found. a and b are coprime when , equivalently when there exist x, y with ax + by = 1 . 3. Modular Arithmetic & Congruences Congruence is an equivalence relation that respects addition, subtraction, and multiplication. So is a ring.

This is the written version of the interactive lesson above. See the full Math for CS course.