Exercise 0.3.15 (Inverse of $a$ mod $n$)

Proof. We use the Python program “bezout” given in Exercise 0.2.1.

def bezout(a,b):
    """input  : integers (a,b)
        output : (x,y,d),
        (x,y) solution of ax+by =d, d = gcd(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)

     In [1]: from numtheory import bezout
     In [2]: bezout(13, 20)
     Out[2]: (17, -11, 1)

So ${\overline{13}}^{-1}=\overline{17}$ in $\mathbb{Z}∕20\mathbb{Z}$.

(verification: $13\cdot 17=221=11\cdot 20+1$.)

(b)

     In [3]: bezout(69, 89)
     Out[3]: (40, -31, 1)

So ${\overline{69}}^{-1}=\overline{40}$ in $\mathbb{Z}∕89\mathbb{Z}$.

(c)

     In [4]: bezout(1891,3797)
     Out[4]: (253, -126, 1)

So ${\overline{253}}^{-1}=\overline{253}$ in $\mathbb{Z}∕3797\mathbb{Z}$.

(d)

     In [5]: bezout(6003722857,77695236973)
     Out[5]: (77695236753, -6003722840, 1)

So ${\overline{6003722857}}^{-1}=\overline{77695236753}$ in $\mathbb{Z}∕77695236973\mathbb{Z}$.