Find g:=ged[389,222] and a,b E Z such that g=a.389+b .222
To find g (the greatest common divisor) of two numbers, we will use the Euclidean algorithm. However, in this case, we are also given two coefficients a and b that satisfy the equation g = a * 389 + b * 222.
Let's follow these steps to calculate g using the Euclidean algorithm:
Step 1: Divide the larger number by the smaller number and find the remainder.
- Divide 389 by 222: 389 ÷ 222 = 1 remainder 167
Step 2: Divide the previous divisor (222) by the remainder (167) and find the new remainder.
- Divide 222 by 167: 222 ÷ 167 = 1 remainder 55
Step 3: Repeat Step 2 until the remainder is zero.
- Divide 167 by 55: 167 ÷ 55 = 3 remainder 2
- Divide 55 by 2: 55 ÷ 2 = 27 remainder 1
- Divide 2 by 1: 2 ÷ 1 = 2 remainder 0
Since the remainder is now zero, we stop here.
The greatest common divisor (g) is the last non-zero remainder, which is 1.
Now, let's find the coefficients a and b such that g = a * 389 + b * 222.
We can also use the extended Euclidean algorithm to find these coefficients.
Step 1: Write down the equation g = a * 389 + b * 222 as an equation for remainders:
- 1 = 1 * 167 + 0 * 55
- 1 = 0 * 167 + 1 * 55
- 1 = 1 * 167 - 1 * 55
- 1 = 1 * (389 - 222) - 1 * 55
- 1 = 1 * 389 - 1 * 222 - 1 * 55
From the equation, we can see that a = 1, b = -1.
Therefore, the greatest common divisor g of 389 and 222 is 1, and we have g = 1 = 1 * 389 + (-1) * 222.