MDC, Euclides e inversos modulares

O algoritmo de Euclides se apoia em mdc(a, b) = mdc(b, a mod b). O resto cai pelo menos à metade a cada duas iterações, então o custo é O(log min(a, b)).

def mdc(a, b):
    while b:
        a, b = b, a % b
    return a

def euclides_estendido(a, b):
    """Retorna (g, x, y) com a·x + b·y = g = mdc(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x, y = euclides_estendido(b, a % b)
    return g, y, x - (a // b) * y

Identidade de Bézout e inverso modular

Existem x, y inteiros com  a·x + n·y = mdc(a, n)
Se mdc(a, n) = 1:  a·x ≡ 1 (mod n),  ou seja,  x = a⁻¹ mod n

O inverso modular é a “divisão” da aritmética modular. Ele só existe quando a e n são coprimos. Em Python 3.8+: pow(a, -1, n).

Teorema de Fermat

p primo, p ∤ a   ⇒   aᵖ⁻¹ ≡ 1 (mod p)
Euler:  mdc(a, n) = 1  ⇒  a^φ(n) ≡ 1 (mod n)

φ(n), a função totiente de Euler, conta quantos números de 1 a n são coprimos com n. Para n = p·q com p, q primos: φ(n) = (p−1)(q−1).