Verificador de primo de Wilson

O verificador de primo de Wilson responde a uma pergunta modular precisa da teoria elementar dos números: dado um primo p, o quadrado de p divide o fatorial de (p menos um) mais um? De forma equivalente, (p−1)! é congruente a −1 módulo p²? O teorema de Wilson já garante que todo primo satisfaz a mesma congruência módulo p, de modo que a condição de primo de Wilson é um reforço genuíno do módulo, e não um novo teste de primalidade. Forneça um primo p e a ferramenta devolve p, p ao quadrado, o resto exato de (p−1)! Os pequenos primos de Wilson clássicos são cinco e treze; quinhentos e sessenta e três é o único outro primo de Wilson conhecido e ainda cabe confortavelmente no intervalo suportado. O motor multiplica inteiros sucessivos sob um módulo BigInt, nunca amostra aleatoriedade, nunca lê o relógio e nunca sai do processo por uma chamada de rede.

O que é um primo de Wilson e o que a resposta contém

Um primo de Wilson é um número primo p tal que o quadrado de p divide o fatorial de (p menos um) mais um. Em linguagem modular a mesma afirmação se lê (p−1)! ≡ −1 (mod p²).

O teorema de Wilson diz que para todo primo p já se tem (p−1)! ≡ −1 (mod p), de modo que o fatorial mais um é sempre divisível por p; a condição de Wilson pergunta se essa divisibilidade se eleva do módulo p até o módulo p².

Os únicos primos de Wilson conhecidos na literatura são cinco, treze e quinhentos e sessenta e três; buscas exaustivas bem além de um milhão não encontraram mais exemplos, o que torna a lista de três membros um exemplo favorito de quão raros os levantamentos modulares podem ser. ≡ -1 (mod p^2). Se você só precisa de primalidade ordinária, use um verificador de primos dedicado; esta página responde à pergunta modular de Wilson com um resto explícito.

Como as entradas são lidas e como o fatorial modular permanece exato

Sinais de mais iniciais opcionais são permitidos em valores positivos; espaços embutidos, prefixos hexadecimais e notação exponencial são rejeitados para que uma célula errada não se torne um indicador incorreto. Internamente o motor primeiro prova a primalidade por divisão de tentativa até a raiz quadrada de p, o que é barato nessa escala e totalmente determinístico.

Em seguida percorre o produto dois vezes três vezes quatro até p menos um, reduzindo módulo p ao quadrado após cada multiplicação com aritmética BigInt para que valores intermediários nunca transbordem uma palavra de máquina fixa nem derivem para ponto flutuante. O resto final desse produto mais um módulo p ao quadrado é convertido de volta a um número JavaScript seguro—p ao quadrado é no máximo um trilhão no intervalo permitido—e comparado com zero.

Onde as verificações de Wilson se encaixam no estudo, demos e código

Estudantes encontram primos de Wilson ao estudar o teorema de Wilson, a aritmética modular e especializações raras de primos junto a primos de Sophie Germain, safeprimes e quocientes de Wilson. Professores podem gerar chaves de resposta para folhas de exercícios sem confiar em apps de calculadora opacas que escondem o passo do produto modular ou aceitam compostos em silêncio.

Desenvolvedores usam o mesmo contrato para validar dados de amostra de bibliotecas de teoria dos números, para condicionar testes de propriedades em geradores de primos aleatórios, ou para pré-verificar que uma semente de demonstração é um dos três primos de Wilson clássicos antes de uma apresentação ao vivo. A prática de contestações frequentemente precisa de uma fonte rápida e offline de respostas de Wilson para checar soluções sem baixar tabelas OEIS nem reimplementar redução modular fatorial com BigInt sob pressão de tempo.

Combine com um verificador de primos ordinário quando precisar só de primalidade, com um verificador de primos gêmeos quando precisar de primos ímpares consecutivos, e com ferramentas de exponenciação modular quando precisar de pow-mod geral em vez de um produto fatorial específico de Wilson.