Date: Mon, 26 May 1997 07:32:48 -0400
From: Alexander Bogomolny
Ronald:
gcd stands for the "Greatest Common Divisor". Given any two integers n and m, gcd(n,m) is the largest number that divides both of them.
gcd(48, 42) = 6
gcd(100, 300) = 100
gcd(100, 325) = 25
There is the famous Euclid's algorithm for finding gcd of any two integers. It's based on the following observation: let n > m. Write
n = p*m + q.
Then any divisor of m and n also divides q. Also, any divisor of m and q also divides n. Therefore, gcd(n,m) = gcd(m,q). You can continue:
m = r*q + s and gcd(m,q) = gcd(q,s).
What's imporatnt is that m > q > s. So that sooner or later the process got to stop. The last term thus obtained will be exactly gcd(n,m).
Best regards,
Alexander Bogomolny
| 41169742 |
