GCD, the Euclidean algorithm, and modular arithmetic
The greatest common divisor and arithmetic with remainders are the everyday tools of number theory and of computer algorithms.
Greatest common divisor
\(\gcd(a, b)\) is the largest integer dividing both. \(\gcd(48, 18) = 6\). Two numbers are coprime if their gcd is 1. The least common multiple satisfies \(\gcd(a, b)\cdot\text{lcm}(a, b) = ab\), so \(\text{lcm}(48, 18) = \frac{864}{6} = 144\).
\gcd(a,b)\cdot\mathrm{lcm}(a,b) = abThe Euclidean algorithm
Replace \((a, b)\) by \((b, a \bmod b)\) until the remainder is 0; the last nonzero remainder is the gcd. For 252 and 105: \(252 = 2 \cdot 105 + 42\), \(105 = 2 \cdot 42 + 21\), \(42 = 2 \cdot 21 + 0\), so \(\gcd = 21\). It is one of the oldest algorithms still in use, and very fast.
\gcd(a,b) = \gcd(b,\ a \bmod b)Bezout's identity
There are integers \(x\) and \(y\) with \(ax + by = \gcd(a, b)\). Running the Euclidean algorithm backwards finds them: for 252 and 105, \(21 = 105 - 2 \cdot 42 = 105 - 2(252 - 2 \cdot 105) = 5 \cdot 105 - 2 \cdot 252\). This extended Euclidean algorithm computes modular inverses.
Modular arithmetic
In arithmetic modulo \(n\), we keep only remainders. Addition and multiplication work on remainders: \((a + b) \bmod n\) and \((ab) \bmod n\) can be computed from \(a \bmod n\) and \(b \bmod n\). So the last digit of \(7^{100}\) can be found by working mod 10 without computing the huge number.
Modular inverses
The inverse of \(a\) mod \(n\) is a number \(a^{-1}\) with \(aa^{-1} \equiv 1 \pmod{n}\). It exists exactly when \(\gcd(a, n) = 1\). The inverse of 3 mod 7 is 5, since \(15 = 2 \cdot 7 + 1\). Inverses let us 'divide' in modular arithmetic and solve congruences like \(3x \equiv 4 \pmod 7\): \(x \equiv 4 \cdot 5 = 20 \equiv 6\).
Fast modular exponentiation
To compute \(a^k \bmod n\) for huge \(k\), square repeatedly: \(a, a^2, a^4, a^8, \ldots\), reducing mod \(n\) each time, then multiply the powers matching the binary digits of \(k\). This takes about \(\log_2 k\) steps, which makes cryptography with 2048-bit numbers practical.
Fermat's little theorem
If \(p\) is prime and \(p \nmid a\), then \(a^{p-1} \equiv 1 \pmod p\). For example, \(3^6 = 729 = 104 \cdot 7 + 1\). This theorem underlies primality tests and the correctness proof of RSA encryption.
a^{p-1} \equiv 1 \pmod pWorked example: last digits
Find the last digit of \(3^{2026}\). Powers of 3 mod 10 cycle: 3, 9, 7, 1, then repeat with period 4. Since \(2026 = 4 \cdot 506 + 2\), the last digit matches \(3^2 = 9\). Spotting cycles is a common modular trick.
Key takeaways
The gcd is found quickly by the Euclidean algorithm, and Bezout's identity expresses it as a combination. Modular arithmetic works with remainders; inverses exist when the gcd is 1. Fast exponentiation and Fermat's little theorem make huge modular calculations practical.
Flashcard
Greatest common divisor
Check your understanding
What is gcd(84, 36)?