# Greatest Common Divisor

Back to Math-CS

Integer d > 0 is the Greatest common divisor of a and b, d = gcd(a,b), iff

1. `d|a and d|b` (divisor)
2. `for c|a and c|b, then c ≤ d` (greatest)

### GCD With Remainder

For a = bq + r, then gcd(a,b) = gcd(b,r)

Very useful for calculating GCDs, and proving values of GCDs. Repeated use becomes Euclidean Algorithm.

1. show that for d = gcd(a,b), d|b and d|r
• d|b by definition, r = qb - a. By DIC, d|(qb-a) => d|r
2. show that for all c|b, c|r, c ≤ d.
• by DIC, c | b(q) + r(1), a = bq+r so c|a
• now c|a and c|b, since gcd(a,b)=d, by definition, c ≤ d

### GCD Characterization Theorem (GCD CT)

If d is a common divisor of a and b and ax + by = d has an integer solution, then d=gcd(a,b)

This shows that any combination of a and b can only be equal to multiples of the gcd.

### Extended Euclidean Algorithm (EEA)

If d = gcd(a,b), then there exist x,y s.t. ax + by = d

Useful for rewriting gcds in equations

a and b are coprime if gcd(a,b)=1. If c|(a•b), then c|a or c|b

If p is prime, and p|ab, then p|a or p|b

#### GCD of One

gcd(a,b)=1 iff there exists x and y with ax + by = 1

GCD CT for d = 1.

#### Division by GCD

if d = gcd(a,b) then gcd(a/d, b/d) = 1

If this wasn't the case, then there would be a larger common divisor than d

### Primes

An integer p > 1 is prime iff its only divisors are 1 and p.

#### Infinitely Many Primes

By induction, there are infinitely many primes.

#### Fundamental Theorem of Arithmetic (UFT)

Every integer can be uniquely expressed as a product of primes.