Exercise 0.2.1 (Equation $ax +by = d$, where $d = \mathrm{g.c.d}(a,b)$)

Proof. We use this homemade program in Python:

def gcd(a,b):
    a , b = abs(a), abs(b)
    while b != 0:
        a, b = b, a%b
    return a

def lcm(a,b):
 return abs((a*b) // gcd(a,b))
 
def bezout(a,b):
    """input  : integers (a,b)
        output : (x,y,d),
        (x,y) solution of ax+by =d, d = pgcd(a,b)
    """
    sgn_a = 1 if a >= 0 else -1
    sgn_b = 1 if b >= 0 else -1
    (r0, r1)=(abs(a), abs(b))
    (u0, v0) = (1, 0)
    (u1, v1) = (0, 1)
    while r1 != 0:
        q = r0 // r1
        (r2, u2, v2) = (r0 - q * r1, u0 - q * u1, v0 - q * v1)
        (r0, r1) = (r1, r2)
        (u0, u1) = (u1, u2)
        (v0, v1) = (v1, v2)
    x , y, d  = sgn_a * u0, sgn_b * v0, r0
    if x <= 0: x, y = x + abs(b), y - sgn_b * a
    return x, y, d

(a)

With Ipython:

     In [4]: a, b = 20, 13; (gcd(a,b), lcm(a,b), bezout(a,b))
     Out[4]: (1, 260, (2, -3, 1))

So for $a=20,b=13$,

$$\begin{array}{lll}\hfill a\wedge b=1,a\vee b=260,& & \hfill \\ \hfill 2a-3b=1.& & \hfill \end{array}$$

(b)

     In [5]: a, b = 69, 372; (gcd(a,b), lcm(a,b), bezout(a,b))
     Out[5]: (3, 8556, (27, -5, 3))

So for $a=69,b=372$,

$$\begin{array}{lll}\hfill a\wedge b=3,a\vee b=8556,& & \hfill \\ \hfill 27a-5b=3.& & \hfill \end{array}$$

(c)

     In [6]: a, b = 792, 275; (gcd(a,b), lcm(a,b), bezout(a,b))
     Out[6]: (11, 19800, (8, -23, 11))

So for $a=792,b=275$,

$$\begin{array}{lll}\hfill a\wedge b=11,a\vee b=19800,& & \hfill \\ \hfill 8a-23b=11.& & \hfill \end{array}$$

(d)

     In [7]: a, b = 11391,5673; (gcd(a,b), lcm(a,b), bezout(a,b))
     Out[7]: (3, 21540381, (5547, -11138, 3))

So for $a=11391,b=5673$,

$$\begin{array}{lll}\hfill a\wedge b=3,a\vee b=21540381,& & \hfill \\ \hfill 5547a-11138b=3& & \hfill \end{array}$$

(e)

     In [8]: a, b = 1761, 1567; (gcd(a,b), lcm(a,b), bezout(a,b))
     Out[8]: (1, 2759487, (1462, -1643, 1))

So for $a=1761,b=1567$,

$$\begin{array}{lll}\hfill a\wedge b=1,a\vee b=2759487,& & \hfill \\ \hfill 1462a-1643b=1.& & \hfill \end{array}$$

(f)

     In [9]: a, b = 507885, 60808; (gcd(a,b), lcm(a,b), bezout(a,b))
     Out[9]: (691, 44693880, (60791, -507743, 691))

So for $a=507885,b=60808$,

$$\begin{array}{lll}\hfill a\wedge b=691,a\vee b=44693880,& & \hfill \\ \hfill 60791a-507743b=691.& & \hfill \end{array}$$