Teoria dos Números · Aritmética Modular

Pequeno Teorema de Fermat

aᵖ⁻¹ ≡ 1 (mod p) — a base da criptografia moderna, provada pela beleza das permutações modulares.

✦ Pequeno Teorema de Fermat
Se p é primo e mdc(a, p) = 1, então:

ap−1 ≡ 1 (mod p)
Forma alternativa (para todo inteiro a)
aᵖ ≡ a (mod p)
Enunciado por Pierre de Fermat em 1640, provado por Euler em 1736. Base da criptografia RSA e dos testes de primalidade modernos.
1
Pré-requisito

O que é congruência modular

Dizemos que a ≡ b (mod n) — lê-se "a é congruente a b módulo n" — quando n divide a diferença a − b:

a ≡ b (mod n)  ⟺  n | (a − b)  ⟺  a e b têm o mesmo resto na divisão por n
Exemplos
17 ≡ 2 (mod 5)    pois 17 − 2 = 15 = 5·3 ✓
100 ≡ 1 (mod 9)   pois 100 − 1 = 99 = 9·11 ✓
2⁴ = 16 ≡ 1 (mod 5)   pois 15 = 5·3 ✓
2
Demonstração

Prova por permutação dos restos

A prova mais elegante usa o fato de que multiplicar os restos não-nulos de 0 a p−1 por a (mod p) apenas os permuta.

🔷 Prova completa
  1. Considerar os p−1 restos não-nulos: 1, 2, 3, …, p−1.
  2. Multiplicar todos por a: a·1, a·2, a·3, …, a·(p−1).
    Como mdc(a,p)=1, nenhum desses é divisível por p, e todos têm restos distintos entre 1 e p−1.
    {a·1 mod p, a·2 mod p, …, a·(p−1) mod p} = {1, 2, …, p−1}
    Os restos são apenas uma permutação de 1, …, p−1.
  3. Multiplicar todos os elementos dos dois conjuntos:
    (a·1)·(a·2)···(a·(p−1)) ≡ 1·2···(p−1) (mod p)
    aᵖ⁻¹ · (p−1)! ≡ (p−1)! (mod p)
  4. Cancelar (p−1)!
    Como mdc((p−1)!, p) = 1 (p é primo), podemos dividir ambos os lados por (p−1)!:
    aᵖ⁻¹ ≡ 1 (mod p)    ∎
3
Exemplos

Verificações e cálculos

Exemplo 1 — 2¹⁰ mod 11

p = 11 (primo), a = 2, mdc(2,11)=1. Pelo teorema: 2¹⁰ ≡ 1 (mod 11).

2¹ = 2, 2² = 4, 2⁴ = 16 ≡ 5, 2⁵ ≡ 10, 2¹⁰ ≡ 100 ≡ 1 (mod 11) ✓
Exemplo 2 — calcular 3¹⁰⁰ mod 7 rapidamente

p = 7, a = 3. Então 3⁶ ≡ 1 (mod 7). Escrever 100 = 6·16 + 4:

3¹⁰⁰ = (3⁶)¹⁶ · 3⁴ ≡ 1¹⁶ · 81 ≡ 81 mod 7 = 4 (mod 7)
Exemplo 3 — pseudoprimos

Se n não é primo, pode ainda acontecer aⁿ⁻¹ ≡ 1 (mod n) para algum a. Por exemplo, 2³⁴⁰ ≡ 1 (mod 341), mas 341 = 11·31 não é primo! Esses são pseudoprimos de Fermat.

4
Interativo

Calculadora do Teorema de Fermat

Verifique aᵖ⁻¹ mod p para qualquer primo p e base a.

Configure e clique em Verificar.
5
Aplicações

Impacto e Generalizações

⚡ Criptografia RSA

O RSA usa diretamente o teorema de Fermat (na forma de Euler: aᵠ⁽ⁿ⁾ ≡ 1 mod n). A segurança do RSA depende de que fatorar n = p·q é difícil, mas calcular potências modulares (via Fermat) é fácil.

⚡ Teste de Primalidade de Miller-Rabin

O teste probabilístico de primalidade mais usado em prática é baseado no Teorema de Fermat. Se aᵖ⁻¹ ≢ 1 (mod p), então p não é primo — garantido. Testando vários valores de a, obtém-se certeza quase-absoluta sobre a primalidade com O(k·log³n) operações.

⚡ Teorema de Euler — generalização

Euler generalizou para qualquer n: se mdc(a,n)=1 então aᵠ⁽ⁿ⁾ ≡ 1 (mod n), onde φ(n) é a função totiente de Euler (quantidade de inteiros de 1 a n coprimos com n). Para p primo, φ(p) = p−1, recuperando Fermat.