“Sage code: Extended Euclidean Algorithm” (1_14.sage) download
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)