1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| # To find pairs of Bézout numbers for the integers (a,b),
# we apply the extended Euclidean algorithm
def xgcd(a,b):
u = 1; v = 0
x = 0; y = 1
print a, '=', u, '*', a, '+', v, '*', b
na = a
nb = b
while nb:
q = na//nb
x, u = u - q*x, x
y,v = v - q*y,y
na, nb = nb, na % nb
print na, '=', u, '*', a, '+', v, '*', b
return na, u, v
xgcd(50,17)
> 50 = 1 * 50 + 0 * 17
> 17 = 0 * 50 + 1 * 17
> 16 = 1 * 50 + -2 * 17
> 1 = -1 * 50 + 3 * 17
> (1, -1, 3)
xgcd(280,11)
> 280 = 1 * 280 + 0 * 11
> 11 = 0 * 280 + 1 * 11
> 5 = 1 * 280 + -25 * 11
> 1 = -2 * 280 + 51 * 11
> (1, -2, 51)
xgcd(50,35)
> 50 = 1 * 50 + 0 * 35
> 35 = 0 * 50 + 1 * 35
> 15 = 1 * 50 + -1 * 35
> 5 = -2 * 50 + 3 * 35
> (5, -2, 3)
|
