Extended Euclids Algorithm for finding the greatest common denominator
@mathematics
I wanted to record an example to show an easy method that is insightful to me.
Example: What is the gcd of 1234 and 567
| n | m | div | rem |
|---|---|---|---|
| 1234 | 567 | 2 | 100 = 1234 - 2 * 567 |
| 567 | 100 | 5 | 67 = 567 - 100 * 5 |
| 100 | 67 | 1 | 33 = 100 - 67 * 1 |
| 67 | 33 | 2 | 1 = 67 - 2 * 33 |
| 33 | 1 | 0 | 33 = 33 - 33 * 1 |
gcd = 1