O Pequeno Teorema de Fermat é uma das joias da Teoria dos Números, e é utilizada, por exemplo, em testes de primalidade para a criptografia moderna.
Ela diz que p | n^p – n, para p primo.
Exemplo. n = 3 e p = 5.
n^p – n = 3^5 – 3 = 240, e 240 é divisível por 5.
Exemplo. n = 4 e p = 3.
n^p – n = 4^3 – 4 = 60, e 60 é divisível por 3.
Contra exemplo. n = 2 e p = 4.
n^p – n = 2^4 – 2 = 14, e 14 não é divisível por 4 (para o teorema funcionar, p deve ser primo em relação a n).
Não confundir com o Grande Teorema de Fermat, aquele que ficou famoso por demorar 300 anos para ser resolvido. O matemático Pierre de Fermat dizia ter a prova na cabeça, mas não cabia no rodapé do livro que ele estava anotando.
O Pequeno Teorema de Fermat tem uma prova combinatória / visualização muito bonita.
A primeira observação é que n^p é uma fórmula muito conhecida em análise combinatória.
Por exemplo, se p=3 posições (as três bolinhas abaixo) e n = 4 cores, n^p indica o número de combinações de cores para pintar as três bolinhas de forma diferente (onde a ordem importa).
A segunda observação. Há n = 4 cores únicas, então se eu pintar as p = 3 bolinhas apenas com uma cor, tenho 4 possibilidades.
Assim, n^p – n = 4^3 – 4 = 60 combinações possíveis de todas as cores para pintar 3 bolinhas, tirando as cores únicas.
Vamos ver as combinações de duas cores. Há 36 formas de colorir as três contas, usando as 4 cores combinadas duas a duas.
O argumento aqui é que, naturalmente, as cores se juntam em grupos de tamanho p.
Falando em joias, vamos usar a ideia de um colar.
Imagine cada coluna como se fosse um colar. Se eu amarrar o topo da linha com a base, tenho um círculo. Tenho que girar cada conta p vezes para ela se repetir, porque p é primo entre si com n – não vai haver uma combinação da mesma cor sem girar p posições.
Para combinações de três cores, vide esquema abaixo.
Há 24 formas de colorir as três contas, usando as 4 cores combinadas três a três.
Portanto 24 combinações 3 a 3, mais 36 combinações 2 a 2, mais 4 combinações únicas dá 64 combinações possíveis (igual a 4^3). Tirando as 4 combinações únicas, as outras combinações naturalmente formam grupos de periodicidade p = 3.
Ou seja, temos que p | n^p – n, para p primo.
Em post seguinte, vou mostrar um contra-exemplo visual, para ilustrar como dois números divisíveis entre si provocam uma repetição, e assim as combinações não se agrupam naturalmente em múltiplos de p.
Trilha sonora: Louis Armstrong – What a Wonderful World
Código fonte do desenho das bolinhas no Github: https://github.com/asgunzi/Prova-Visual-Pequeno-Teor-Fermat
Veja também:
Forgotten Lore - Ideias Técnicas com uma pitada de filosofia.