GCD Formula – Greatest Common Divisor Euclidean Algorithm
The complete GCD formula using the Euclidean algorithm: variable definitions, step-by-step method, and three fully worked examples.
Formula
The greatest common divisor of two positive integers a and b is computed by the Euclidean algorithm: replace (a, b) with (b, a mod b) repeatedly until the second argument is zero. The GCD is the final non-zero value.
Variables
| Symbol | Name | Description | Unit |
|---|---|---|---|
| a | First integer | A positive integer; the larger of the two initially (the algorithm works regardless of order) | — |
| b | Second integer | A positive integer; replaced by a mod b at each step | — |
| q | Quotient | q = ⌊a / b⌋, the integer quotient at each step | — |
| r | Remainder | r = a mod b = a − b × q; this becomes the new b at the next step | — |
| GCD | Greatest Common Divisor | The final non-zero remainder; the largest integer dividing both original inputs | — |
How to Use
- If b = 0, return a as the GCD.
- Compute the remainder: r = a mod b.
- Set a ← b and b ← r.
- Repeat from step 1.
Examples
1. GCD(48, 36)
Apply the Euclidean algorithm step by step.
| Step | a | b | a = b × q + r | Remainder r |
|---|---|---|---|---|
| 1 | 48 | 36 | 48 = 36 × 1 + 12 | 12 |
| 2 | 36 | 12 | 36 = 12 × 3 + 0 | 0 |
Verification: 48 ÷ 12 = 4, 36 ÷ 12 = 3. Both divide exactly. No larger divisor exists.
2. GCD(1071, 462)
A larger example to show multiple Euclidean steps.
| Step | a | b | a = b × q + r | Remainder r |
|---|---|---|---|---|
| 1 | 1071 | 462 | 1071 = 462 × 2 + 147 | 147 |
| 2 | 462 | 147 | 462 = 147 × 3 + 21 | 21 |
| 3 | 147 | 21 | 147 = 21 × 7 + 0 | 0 |
1071 = 3 × 357 = 3 × 3 × 7 × 17 = 3² × 7 × 17; 462 = 2 × 3 × 7 × 11. Shared factors: 3 × 7 = 21. ✓
3. GCD(360, 756) via prime factorization comparison
Show the prime factorization method as an alternative.
For each prime, take the minimum exponent:
| Prime | Exp in 360 | Exp in 756 | min |
|---|---|---|---|
| 2 | 3 | 2 | 2 |
| 3 | 2 | 3 | 2 |
| 5 | 1 | 0 | 0 |
| 7 | 0 | 1 | 0 |
Both methods give 36. The Euclidean algorithm is faster in practice; prime factorization is more visual for understanding why the answer is what it is.
Related pages
- Use the Calculator — Interactive calculator for this formula
- Read the Notes — Step-by-step explanation with worked examples