Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (990,84)
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 | 990 | |||
Set to 0 | 0 | Set to 1 | 1 | 84 | Quotient of 990/84 | 11 | |
1 - (11 x 0) | 1 | 0 - (11 x 1) | -11 | Remainder of 990/84 | 66 | Quotient of 84/66 | 1 |
0 - (1 x 1) | -1 | 1 - (1 x -11) | 12 | Remainder of 84/66 | 18 | Quotient of 66/18 | 3 |
1 - (3 x -1) | 4 | -11 - (3 x 12) | -47 | Remainder of 66/18 | 12 | Quotient of 18/12 | 1 |
-1 - (1 x 4) | -5 | 12 - (1 x -47) | 59 | Remainder of 18/12 | 6 | Quotient of 12/6 | 2 |
4 - (2 x -5) | 14 | -47 - (2 x 59) | -165 | Remainder of 12/6 | 0 | Quotient of 6/0 | 0 |
a = -5 and b = 59
ax + by = gcd(a,b)
990x + 84y = gcd(990