Use the EEA to find integers 𝑥 and 𝑦 such that:

Question

300𝑥 + 222𝑦 = gcd(300,222)

Answer 1

I showed the formula previously, so I will just show the results of the algorithm here.

The gcd of 300 and 222 is 6 and, using the next to last row, 6 = -17 * 300 + 23 * 222

Calculate, and you will see that the algorithm works

If you are using Excel, you will keep an additional column that has the values of q = int(r_i-2/r_i-1), as this allows one to calculate values of r, s, and t.