Find g := gcd(389,222) and a,b belongs to Z such that g = a.389 + b.222.
ive got 389 = 1*222 +167
then 222= 1*167 +55
167= 3*55 +2
55= 27*2 +1
2= 2*1
and hence 1 = GCD of (389,222)
but im not sure how you work out the a,b values??
okay ive got the answer as 2*389-3.5*222 but i done it with trial an error with random numbers, don't no the actual formula
To find the greatest common divisor (gcd) of two numbers, you can use the Euclidean algorithm. This algorithm involves repeatedly subtracting multiples of the smaller number from the larger number until you obtain a result of 0.
Let's use the Euclidean algorithm to find the gcd(389, 222):
1. Divide 389 by 222: 389 ÷ 222 = 1 remainder 167.
2. Since the remainder is not zero, divide 222 by 167: 222 ÷ 167 = 1 remainder 55.
3. Divide 167 by 55: 167 ÷ 55 = 3 remainder 2.
4. Divide 55 by 2: 55 ÷ 2 = 27 remainder 1.
5. Divide 2 by 1: 2 ÷ 1 = 2 remainder 0.
Since the remainder has become 0, the gcd(389, 222) is the last nonzero remainder encountered, which is 1.
Now, we can find the coefficients (a and b) that satisfy the equation g = a.389 + b.222, where g is the gcd:
Backtrack through the steps of the Euclidean algorithm to express each remainder as a linear combination of the original numbers:
Step 3: 55 = 167 - 3.55
Step 2: 167 = 222 - 1.55
Step 1: 389 = 222 + 1.167
Plugging these expressions back into the equation g = a.389 + b.222:
1 = (1.167) - (1.3).55
= (1.167) - (1.3)[(1.222) - (1.55)]
= (1.167) - (1.3).(1.222) + (1.3).(1.55)
= (1.167) - (1.3).(1.222) + (1.3){(1.389) - (1.222)}
Simplifying further:
1 = (4.167) - (3.222)
Therefore, a = 4 and b = -3 satisfy the equation g = a.389 + b.222, where g = gcd(389, 222) = 1.
So, g = 1, a = 4, and b = -3.