Generate our RSA key pair from p = 59 and q = 71 using the extended Euclidean algorithm written out longhand — no `pow(e, -1, m)` shortcut — and verify the inverse by multiplication.

Answer

def egcd(a, b): if b == 0: return (a, 1, 0) g, x, y = egcd(b, a % b) return (g, y, x - (a // b) * y) def inverse(e, m): g, x, _ = egcd(e, m) if g != 1: return None return x % m p, q, e = 59, 71, 13 n = p * q phi = (p - 1) * (q - 1) d = inverse(e, phi) print("n =", n) print("phi =", phi) print("e =", e, "gcd =", egcd(e, phi)[0]) print("d =", d) print("e*d =", e * d, "= %d*phi + %d" % (e * d // phi, e * d % phi))

Stallings & Brown 5e ch21 §21.4; App B