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

Question

84𝑥 + 33𝑦 = gcd(84,33)

Answer 1

Wikipedia is your friend, if your book isn't

We use the standard Euclidean algorithm, but we use the same calculation on two additional columns. We can label the three columns r, s, and t, where the first two rows of r are our two original numbers, the first two rows of s are 1 and 0 and the first two rows of t are 0 and 1.

Thus, our first two rows on 84x + 33y are

84 1 0

33 0 1

Then, in the next row, in the first column, we normally just put 84 (mod 33), or r₃, but if we consider that r₃ = r₁ - r₂q₂, or q2 = int(r₁/r₂), or in general r_i = r_i-2 - r_i-1q_i-1, we shall use the same formula for s and t.

s_i = s_i-2 - s_i-1q_i-1, t_i = t_i-2 - t_i-1q_i-1,

Our final values of s and t become the x and y values that solve 84x + 33y = gcd(84,33)

Note that once we have this solution, we have the general solution for 84x + 33y, as we just divide gcd(84,33) into the number and multiply this times our solution to the EEA solution.

Then, for this problem,

in row 3, r₃ = r₁ - r₂q₂, we get, as 84 (mod 33) = 18 and int(84/33) = 2

18 = 84 - 33 * 2

r₃ = 18 and also q2 = 2

Then, we can now calculate s₃ and t₃

s_i = s_i-2 - s_i-1q_i-1,

s₃ = s₁ - s₂* q₂

s₃ = 1 - 0 * 2

s₃ = 1

t_i = t_i-2 - t_i-1q_i-1,

t₃ = t₁ - t₂* q₂

t₃ = 0 - 1 * 2

t₃ = -2

We now have

84 1 0

33 0 1

18 1 -2

Then, in row 4,

as 33 (mod 18) = 15, and int(33/18) = 1

we have 15 = 33 - 18 * 1, so r₄ = 15, q₃ = 1, and

s_i = s_i-2 - s_i-1q_i-1,

s₄ = s₂ - s₃* q₃

s₄ = 0 - 1* 1 = -1

t_i = t_i-2 - t_i-1q_i-1,

t₄ = t₂ - t₃* q₃

t₄ = 1 - (-2) * 1 = 3

84 1 0

33 0 1

18 1 -2

15 -1 3

Then, we keep going

84 1 0

33 0 1

18 1 -2

15 -1 3

3 2 -5

0

Then, from the next to last row, 3 = 2 * 84 - 5 * 33

Compute, and you will see that this is correct