Find g := gcd(389; 222) and a; b 2 Z such that g = a � 389 + b � 222.

To find the greatest common divisor (gcd) of two numbers, you can use the Euclidean algorithm. The Euclidean algorithm involves dividing the larger number by the smaller number and taking the remainder. Then, you repeat the process with the smaller number and the remainder, until the remainder becomes zero. The last non-zero remainder is the gcd of the two numbers. Let's apply this algorithm to find g = gcd(389, 222).

Step 1: Divide 389 by 222:
389 ÷ 222 = 1 remainder 167

Step 2: Divide 222 by 167:
222 ÷ 167 = 1 remainder 55

Step 3: Divide 167 by 55:
167 ÷ 55 = 3 remainder 2

Step 4: Divide 55 by 2:
55 ÷ 2 = 27 remainder 1

Step 5: Divide 2 by 1:
2 ÷ 1 = 2 remainder 0

Since the remainder is now 0, we stop the algorithm. The gcd(389, 222) is the last non-zero remainder, which is 1.

Now, we need to find integers a and b such that g = a * 389 + b * 222, where g is the gcd. We can use the Extended Euclidean algorithm for this.

The extended Euclidean algorithm involves performing the Euclidean algorithm in reverse, while keeping track of two sets of coefficients, x and y. Starting from the last non-zero remainder, we have:

Step 5: 1 = 55 - 2 * 27
Step 4: 1 = 55 - 2 * (167 - 3 * 55)
= -2 * 167 + 7 * 55
Step 3: 1 = (-2) * (222 - 167) + 7 * 55
= 7 * 55 + (-2) * 222 + 3 * 167
Step 2: 1 = 7 * 55 + (-2) * 222 + 3 * (389 - 222)
= 3 * 389 + (-8) * 222
Step 1: 1 = 3 * 389 + (-8) * 222

From this, we can see that a = 3 and b = -8. Therefore, g = 1 = 3 * 389 + (-8) * 222.