# Gcd

• Sep 29th 2006, 02:39 PM
JimmyT
Gcd
I was able to find the Greatest Common Divisor of two numbers by using the Euclidean Algorithm. But what is the easiest way to express this GCD as a linear combination in the form c=au+bv where c is the GCD of a,b?

For example, the gcd(56,72)=8. And the linear combination can be expressed as 8 = (56)4-(72)(3). What's the easiest way to actually find this combination without simply guessing?
• Sep 29th 2006, 02:54 PM
Plato
Easy is in the eyes of the doer. It really depends on what one prefers.
Personally I prefer to factor numbers into their prime factor form.
For example 144000=(2^7)(3^2)(5^3) and 68600=(2^3)(5^2)(7^3).
So gcd(144000, 68600 )=(2^3)(5^2).
Use the common primes with their least powers.
This method works with more than two numbers.
• Sep 30th 2006, 04:40 PM
ThePerfectHacker
Quote:

Originally Posted by JimmyT
I was able to find the Greatest Common Divisor of two numbers by using the Euclidean Algorithm.

Are you familiar with continued fractions?
(That is the most direct method).