Subject: Re: gcd
Date: Mon, 26 May 1997 07:32:48 -0400
From: Alexander Bogomolny


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

|Reply| |Up|

Copyright © 1996-2018 Alexander Bogomolny