Prova visual do Pequeno Teorema de Fermat

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.

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.

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