Notes - Solving AX+ BY = D

The following are notes from Introduction to Cryptography with Coding Theory.

• In a previous example we used the Euclidean Algorithm to find the GCD 
• We will now show how we can get the integers x,y that fulfill
• ax + by = gcd(a,b)
• Example gcd(482,1180)
• 1180 = 2 * 482 +216
• 482 = 2 * 216 + 50
• 216 = 4 * 50 + 16
• 50 = 3 * 16 + 2
• 16 = 8 * 2 + 0
• Which gave us q₁ = 2, q₂ = 2, q₃ = 4, q₄ = 3, q₅ = 8
• We will now use the following sequences
• x₀ = 0, x₁ = 1, x_j = -q_j-1 x_j-1 + x_j-2
• y₀ = 1, y₁ = 0, y_j = -q_j-1 y_j-1 + y_j-2
• In order to arrive at
• x₀ = 0
• x₁ = 1
• x₂ = -2 x₁ + x₀ = -2
• x₃ = -2 x₂ + x₁ = 5
• x₄ = -4 x₃ + x₂ = -22
• x₅ = -3 x₄ + x₃ = 71
• y₅ would be calculated similarly to arrive at -29
• We would then plug this in to ax + by = gcd(a,b)
• 482 * 71 + 1180 * (-29)
• 2
• This is often called the extended Euclidean algorithm
• used for congruences

Back to ToC