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

Código fonte do desenho das bolinhas no Github: https://github.com/asgunzi/Prova-Visual-Pequeno-Teor-Fermat

Veja também:

Números Triangulares

Números triangulares são aqueles que formam um triângulo, fazendo jus ao próprio nome.

1

3 = 1 +2

6 = 1 +2 + 3

10 = 1 +2 + 3 + 4

Fiz uma animaçãozinha para demonstrar. Para visualização interativa: https://asgunzi.github.io/NumerosTriangulares/

Cada número triangular é a soma da progressão geométrica 1+2+3+…+N, ou seja, podemos usar a fórmula da PG para calcular um número triangular qualquer.

Vide também:

Euclides e a prova visual dos primos

Um dos resultados mais belos da Matemática é a prova de Euclides, sobre a infinitude dos números primos, escrita há mais de 2.300 anos atrás.

Um número é primo se pode ser dividido apenas por 1 e por si mesmo, sem deixar resto.

A prova é por contradição. Primeiro Euclides supôs que o número de primos fosse finito: {p1, p2, …, pN}.

Para ilustrar, suponha que o conjunto de todos os primos seja formado apenas pelos três primeiros, {2, 3, 5}:

A seguir, Euclides afirmou que existe pelo menos um primo maior do que todos os primos finitos conhecidos: p1p2…*pN +1, ou seja, o produto de todos os primos + 1. Tal número não é divisível por nenhum dos primos anteriores, já que restaria 1 na divisão.

No caso do exemplo, tal número seria igual a 2 * 3 * 5 + 1 = 31.

Visualizando, o novo primo não é divisível por 2:

Nem por 3:

Nem por 5:

Sempre vai restar 1 na divisão.

Portanto, como sempre é possível encontrar esse primo adicional para um conjunto de primos finito, a conclusão é a de que o conjunto dos números primos é infinito.

Veja também:

https://ideiasesquecidas.com/2021/08/25/poligonos-e-conexoes/

Prova visual da sequência 1 + 2 + 4 + 8 = 2^N – 1

A progressão geométrica 1 + 2 + 4 + 8 + …, com cada elemento sendo o dobro da anterior, tem soma igual a 2^N-1, onde N é o número de elementos da soma.

Há uma prova visual muito bonita desta.

Imagine que tomamos emprestado um quadrado, o vermelho, e somamos o primeiro elemento (1):

O próximo elemento da soma, o 2, colocamos à direita – espelhando a soma anterior.

O próximo elemento da soma, o 4, é representado abaixo, de novo espelhando a soma anterior.

E assim sucessivamente. Para 8:

Para o 16:

Com 10 elementos:

Criei um programinha para visualizar dinamicamente essa soma geométrica. É da onde os prints acima foram tirados. Segue o link:

https://asgunzi.github.io/somageometricaD3

Agora, um pouco da teoria. Uma soma de PG finita é dada pela fórmula:

No caso da sequência acima, a1 = 1, q = 2, para N elementos. Então, fica S = 1*(2^N-1)/(2-1) = 2^N-1, que é a mesma conta.

Eu prefiro a prova visual…

Veja também:


Visualize a sequência de Fibonacci https://asgunzi.github.io/Fibonacci

Fórmula de soma de PA visual

https://ideiasesquecidas.com/2015/09/04/soma-visual-de-pa

Laboratório de Matemática


https://ideiasesquecidas.com/laboratorio-de-matematica

Soma de ímpares consecutivos – álgebra de pedrinhas

Gosto muito de provas visuais. Tenho neste blog uma coleção de provas deste tipo, envolvendo “álgebra de pedrinhas” – vide Laboratório de Matemática (ideiasesquecidas.com). Segue mais uma.

Prova visual de que a soma de ímpares consecutivos é divisível por 4:

Algebricamente, (2n+1) + (2n+3) = 4n +4, que é divisível por 4.

Ambas as provas são muito simples, porém a visual é mais bonita.

Veja também:

Prova visual da sequência 1+3+5+… (ideiasesquecidas.com)

Pitágoras Visual (ideiasesquecidas.com)