Many sources complicate how Euclid’s algorithm for finding the greatest common divisor of two integers works. The following is a description of its simplest variant.

This is of course computationally less efficient than the more advanced versions, but remember this if you need to remember something but don’t want to.

Extended Euclidean algorithm

euclid(a,b) gives a triplet (d, x, y) such that d = gcd(a, b) = ax + by.

import math
def euclid(a, b):
    if b==0:
        return (a, 1, b)
    (d_, x_, y_) = euclid(b, a % b)
    (d, x, y) = (d_, y_, x_ - math.floor(a / b) * y_)
    return (d, x, y)

If p is a prime, running euclid(a, p) gives x as the multiplicative inverse of a modulo p; ax mod p = 1.