Uma aplicação do Teorema de Wilson, da Teoria dos Números
Como saber se um número é primo ou não?
Há diversos métodos, um dos mais simples e efetivos é o do Crivo de Erastótenes.
Porém, não é o único. Um método curioso envolve o Teorema de Wilson.
No séc. XVIII, os matemáticos descobriram um método novo para testar primos.
Pegue um número N. Multiplique todos os números de 1 até N-1: 1 * 2 * 3 * …* N-1.
Some 1 ao total. Se o resultado for divisível por N, o número será primo.
Exemplo. Para N = 5, temos:
1 * 2 * 3 * 4 + 1 = 25, que é divisível por 5, portanto 5 é primo.
Já para N = 6, temos:
1 * 2 * 3 * 4 * 5 + 1 = 121, que não é divisível por 6, portanto 6 é composto.
Para N = 3, temos:
1*2 + 1 = 3, que é divisível por 3, portanto 3 é primo.
Podemos utilizar a notação fatorial (!) para indicar o produtório de 1 a N-1: (N-1)!
O problema deste teste é que (N-1)! cresce de forma absurdamente rápida. Imagine calcular 100!, vai explodir a memória da calculadora rapidamente.
Vale mais a pena salvar o resultado, conhecido como Teorema de Wilson. Para N primo, vale a seguinte fórmula:
(N-1)! = -1 mod N
Esta é uma das fórmulas mais clássicas do nobre ramo de conhecimento da Teoria dos Números, e um dia posto a prova.
Para ilustrar o post, uma imagem inspirada em crivo de Erastótenes, Teorema de Wilson e Kandinski.
Assine também a minha newsletter, para mais reflexões analíticas avançadas:
https://arnaldogunzi.substack.com
Vide também:
Originally published at https://ideiasesquecidas.com on September 22, 2024.
