Em 1640, Pierre de Fermat escreveu em uma carta a um amigo.

Se pé primo e aé qualquer inteiro não divisível por p, então aᵖ⁻¹ − 1é divisível por p.

Ao contrário da maioria das coisas que digo aos meus amigos, Fermat estava certo. Fermat nunca provou isso. Ele deixou o trabalho para Leonhard Euler, conhecido aqui como a pessoa mais ocupada de toda a história da matemática. Em 1736, Euler mostrou que Fermat estava certo e estendeu a afirmação também.

Pequeno Teorema de Fermat

Fermat tinha peixes maiores para fritar, então esse era seu pequeno teorema. Afirma que, para qualquer número primo pe inteiro aque é coprimo para p: aᵖ⁻¹ % p = 1.

Por que Fermat estava certo?

A lista de números a, 2a, 3a, ..., (p-1)asão todos primos de p, porque pé primo. Se usarmos mod pcada um desses números, teremos a garantia de produzir uma lista de todos os números entre 1& p-1. Isso ocorre porque haverá p - 1resultados distintos. Podemos provar que serão distintos.

> if `k` & `m` are two values between `1` & `p - 1`
> to prove they are NOT distinct we would want to find
ka ≡ ma (mod p)
> because of the cancellation rule
k ≡ m (mod p)
> because `k` & `m` were defined as being less than `p`
k = m

Assim, mostramos que, dada a lista a, 2a, 3a, ..., (p-1)a (mod p), obteríamos o conjunto completo de números 1 -> p - 1. Ordenar esses resultados nos daria o conjunto: 1, 2, ..., p-1.

Um exemplo pode tornar as coisas mais claras:

p = 7, a = 3
> a, 2a, 3a, ..., (p-1)a
1(3), 2(3), 3(3), 4(3), 5(3), 6(3)
3, 6, 9, 12, 15, 18
> all `mod p`
3, 6, 2, 5, 1, 4
> ordering the results
1, 2, 3, 4, 5, 6

> we know that
a, 2a, ..., (p-1)a ≡ 1, 2, ..., p-1 (mod p)
> multiplying all elements
a x 2a x ... x (p-1)a ≡ 1 x 2 x ... x (p-1) (mod p)
> simplifies
aᵖ⁻¹(p-1)! ≡ (p-1)! (mod p)
> cancel `(p-1)!`
> giving us
aᵖ⁻¹ ≡ 1 (mod p)

Teorema de Euler

Tendo provado o Pequeno Teorema de Fermat, Euler decidiu continuar. Ele foi capaz de mostrar que, para quaisquer dois números inteiros primos entre si, nenhum deles é necessariamente primo: aᵠ⁽ⁿ⁾ ≡ 1 (mod n). refere-se à Função Totient de Euler, que exploramos anteriormente . A função Totient de qualquer número inteiro nretorna o número de ncoprimos menores que n.

Ao contrário do Pequeno Teorema de Fermat, a extensão de Euler eliminou a necessidade de o módulo ser um número primo. Felizmente, já fizemos a maior parte do trabalho para provar isso.

Lembre-se de como, com o Pequeno Teorema de Fermat, todos aos múltiplos de ' (mod p), deram os números 1 -> p-1. Essa lista de números, 1 -> p-1eram primos de p's, dado que pé primo. Nesse caso, o módulo nnão é primo, mas a lista de ncoprimos de ' multiplicada por a, all (mod n), ainda produz ncoprimos de '. Por exemplo

> remembering that
(n) = Number of n's coprimes
n = 10
> n's coprimes
1, 3, 7, 9
a x 3a x 7a x 9a ≡ 1 x 3 x 7 x 9 (mod n)
> where n = 10, this gives us the number of "a" factors
aᵠ⁽¹⁰⁾
aᵠ⁽¹⁰⁾ x (1 x 3 x 7 x 9) ≡ (1 x 3 x 7 x 9) (mod n)
> cancel the coprime multiplication
aᵠ⁽¹⁰⁾ ≡ 1 (mod n)

O Pequeno Teorema de Fermat e o Teorema de Euler são muito importantes para a Teoria dos Números. Eles ajudam a resolver casos da Função Carmichael, que cobrimos em profundidade . Eles são interessantes isoladamente também, como um exemplo de uso da Função Totiente de Euler.

E tudo começou com uma carta a um amigo há quase 400 anos.

Mais ?

Eu escrevo o boletim informativo mais curto do mundo. Uma coisa rápida que aprendi, vi ou li durante a semana, toda quarta-feira.

Quero que seja o boletim informativo mais acessível e direto que você receber.

Pode valer a pena tentar. Cancelar a inscrição também é fácil.

Chama-se . Vejo você lá!