Euclidean Algorithm
Example:
Find the GCD of 1386 and 322
For sake of illustrating the proof:
Using GCD WR and the division algorithm:
| Stage | Calculation | Change |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 |
We have
- At each step, we use the division algorithm, writing
with - Then we use GCD WR to deduce that
For applicative use:
| Explanation | |||
|---|---|---|---|
So the GCD is column