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?
September 29th 2006, 01:54 PM
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.
September 30th 2006, 03:40 PM
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).