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?
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.
Are you familiar with continued fractions?
Originally Posted by JimmyT
(That is the most direct method).