13.1 Divisibility and the Division Algorithm

For integers a ≠ 0 and b, a divides b (written a | b) iff b = a·c for some integer c. Properties: if a | b and a | c then a | (bx + cy) for all integers x, y (divisibility passes to linear combinations); if a | b and b | c then a | c (transitivity).

Division algorithm: for any integer a and positive integer d there exist unique q and r with

a = d·q + r, 0 ≤ r < d.

The remainder is never negative: for a = −17, d = 5, write −17 = 5·(−4) + 3, so r = 3 (not −2). Programming-language % operators differ on negatives — C/Java give -17 % 5 = -2 while Python gives 3; the mathematical convention matches Python. This trips up hash-function implementations constantly.

13.2 Primes and the Fundamental Theorem of Arithmetic

A prime is an integer p > 1 whose only positive divisors are 1 and p; integers > 1 that are not prime are composite. (1 is neither.) Fundamental Theorem of Arithmetic: every integer n > 1 factors into primes uniquely up to order — e.g., 360 = 2^3 · 3^2 · 5.

• Trial division: if n is composite, it has a prime divisor ≤ √n. To test 97: √97 ≈ 9.8, check 2, 3, 5, 7 — none divide → 97 is prime. Only 4 divisions instead of 95.
• Sieve of Eratosthenes: to list primes ≤ n, repeatedly strike multiples of each surviving prime up to √n; costs O(n log log n) and is the standard way to precompute primes.
• Infinitude of primes (Euclid): given any finite list p1, ..., pk, the number N = p1·p2···pk + 1 leaves remainder 1 on division by every pi, so its prime factors are new — no finite list is complete. ∎

13.3 GCD, LCM, and Coprimality

gcd(a, b) = largest d dividing both; lcm(a, b) = smallest positive common multiple. Via prime factorizations, gcd takes the minimum exponent of each prime and lcm the maximum, which yields the fundamental identity:

gcd(a, b) · lcm(a, b) = a·b (for positive a, b).

Integers with gcd(a, b) = 1 are coprime (e.g., 8 and 15). Factoring is expensive for large numbers, so real systems compute gcd with Euclid's algorithm instead.

13.4 Worked Example 1 — Euclid's Algorithm

Theorem: gcd(a, b) = gcd(b, a mod b), because any common divisor of a and b also divides a − qb = r, and conversely. Iterate until the remainder is 0.

Compute gcd(252, 198):

252 = 1 · 198 + 54
198 = 3 · 54  + 36
 54 = 1 · 36  + 18
 36 = 2 · 18  + 0    →  gcd(252, 198) = 18

Then lcm(252, 198) = 252·198/18 = 49,896/18 = 2,772. Euclid's algorithm runs in O(log min(a, b)) divisions — Lamé's theorem says the worst case is consecutive Fibonacci numbers, tying Unit 3 back in.

13.5 Worked Example 2 — Extended Euclid (Bézout's Identity)

Bézout: gcd(a, b) is expressible as a·s + b·t for some integers s, t. Back-substitute through the table above to express 18 in terms of 252 and 198:

18 = 54 − 1·36
   = 54 − 1·(198 − 3·54)        = 4·54 − 1·198
   = 4·(252 − 1·198) − 1·198    = 4·252 − 5·198

Verify: 4·252 − 5·198 = 1008 − 990 = 18 ✔. So s = 4, t = −5. This is not a curiosity: when gcd(a, m) = 1, Bézout gives a·s + m·t = 1, i.e., a·s ≡ 1 (mod m) — s is the modular inverse of a, the key step in solving congruences and in RSA key generation (next lesson).

13.6 Common Mistakes & CS Applications

• Declaring 1 prime, or forgetting gcd(0, n) = n.
• Producing negative remainders in the division algorithm (r must satisfy 0 ≤ r < d).
• Computing lcm by factoring when lcm(a, b) = a·b/gcd(a, b) is one Euclid run — and computing a·b/gcd as (a/gcd)·b avoids integer overflow.
• Applications: gcd reduces fractions in exact-arithmetic libraries; hash tables use prime table sizes so that keys with common factors still spread across buckets; coprime step sizes guarantee full-cycle probing in double hashing; RSA needs two large primes and Bézout coefficients; lcm schedules periodic tasks (when do two timers of period 12 ms and 18 ms fire together? every lcm = 36 ms).

🎯 Exam Focus

1. State and prove the division algorithm's uniqueness claim (both q and r are unique).
2. Using Euclid's algorithm, find gcd(4147, 10672), and lcm(4147, 10672).
3. Find integers s and t with 252s + 198t = 18. Are they unique? Explain.
4. Prove that √p is irrational for every prime p (generalize the √2 proof using unique factorization).
5. Prove: if a | c, b | c and gcd(a, b) = 1, then ab | c.
6. Show that gcd(F(n+1), F(n)) = 1 for consecutive Fibonacci numbers, and explain why they are Euclid's worst case.