Math Fundamentals18 sections · 814 units
Open in Course

GCD Properties

Useful identities

1.1. gcd(a, 0) = a for any a > 0.

2.2. gcd(a, b) = gcd(b, a). Order does not matter.

3.3. gcd(a, b) = gcd(a - b, b) if a > b. This is a slower version of the Euclidean algorithm.

4.4. If d = gcd(a, b), then gcd(a/d, b/d) = 1. Dividing by GCD makes numbers coprime.