Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (17,55)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 17 | |||
Set to 0 | 0 | Set to 1 | 1 | 55 | Quotient of 17/55 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 17/55 | 17 | Quotient of 55/17 | 3 |
0 - (3 x 1) | -3 | 1 - (3 x 0) | 1 | Remainder of 55/17 | 4 | Quotient of 17/4 | 4 |
1 - (4 x -3) | 13 | 0 - (4 x 1) | -4 | Remainder of 17/4 | 1 | Quotient of 4/1 | 4 |
-3 - (4 x 13) | -55 | 1 - (4 x -4) | 17 | Remainder of 4/1 | 0 | Quotient of 1/0 | 0 |
a = 13 and b = -4
ax + by = gcd(a,b)
17x + 55y = gcd(17