Verificatore di primo di Wilson

Il verificatore di primo di Wilson risponde a una domanda modulare precisa della teoria elementare dei numeri: dato un primo p, il quadrato di p divide il fattoriale di (p meno uno) più uno? In modo equivalente, (p−1)! è congruente a −1 modulo p²? Il teorema di Wilson garantisce già che ogni primo soddisfa la stessa congruenza modulo p, quindi la condizione di primo di Wilson è un rafforzamento genuino del modulo e non un nuovo test di primalità. Fornisca un primo p e lo strumento restituisce p, p al quadrato, il resto esatto di (p−1)! I piccoli primi di Wilson classici sono cinque e tredici; cinquecentosessantatré è l’unico altro primo di Wilson noto e resta comodamente nell’intervallo supportato. Il motore moltiplica interi successivi sotto un modulo BigInt, non campiona mai casualità, non legge mai l’orologio e non lascia mai il processo per una chiamata di rete.

Cos’è un primo di Wilson e cosa contiene la risposta

Un primo di Wilson è un numero primo p tale che il quadrato di p divide il fattoriale di (p meno uno) più uno. In linguaggio modulare la stessa affermazione si legge (p−1)! ≡ −1 (mod p²).

Il teorema di Wilson afferma che per ogni primo p si ha già (p−1)! ≡ −1 (mod p), quindi il fattoriale più uno è sempre divisibile per p; la condizione di Wilson chiede se quella divisibilità si solleva dal modulo p fino al modulo p². Gli unici primi di Wilson noti in letteratura sono cinque, tredici e cinquecentosessantatré; ricerche esaustive ben oltre un milione non hanno trovato altri esempi, il che rende l’elenco di tre membri un esempio preferito di quanto rari possano essere i sollevamenti modulari.

≡ -1 (mod p^2). Se Le serve solo la primalità ordinaria, usi un verificatore di primi dedicato; questa pagina risponde alla domanda modulare di Wilson con un resto esplicito.

Come si leggono gli ingressi e come il fattoriale modulare resta esatto

Segni più iniziali opzionali sono consentiti per valori positivi; spazi incorporati, prefissi esadecimali e notazione esponenziale sono respinti affinché una cella errata non diventi un flag sbagliato. Internamente il motore dimostra prima la primalità per divisione di prova fino alla radice quadrata di p, operazione economica a questa scala e del tutto deterministica.

Poi percorre il prodotto due per tre per quattro fino a p meno uno, riducendo modulo p al quadrato dopo ogni moltiplicazione con aritmetica BigInt così che i valori intermedi non trabocchino mai una parola macchina fissa e non derivino verso il floating-point. Il resto finale di quel prodotto più uno modulo p al quadrato è riconvertito in un numero JavaScript sicuro—p al quadrato è al massimo un bilione nell’intervallo consentito—e confrontato con zero.

Dove i controlli di Wilson si inseriscono nello studio, nelle demo e nel codice

Gli studenti incontrano i primi di Wilson studiando il teorema di Wilson, l’aritmetica modulare e specializzazioni rare di primi accanto ai primi di Sophie Germain, ai safeprimes e ai quozienti di Wilson. Gli insegnanti possono generare chiavi di risposta per fogli di lavoro senza fidarsi di app calcolatrice opache che nascondono il passo del prodotto modulare o accettano silenziosamente i composti.

Gli sviluppatori usano lo stesso contratto per validare dati di esempio di librerie di teoria dei numeri, per condizionare test di proprietà su generatori di primi casuali, o per pre-verificare che un seme di dimostrazione sia uno dei tre primi di Wilson classici prima di una presentazione dal vivo. La pratica di gara spesso necessita di una fonte rapida e offline di risposte di Wilson per controllare soluzioni senza scaricare tabelle OEIS né reimplementare la riduzione fattoriale modulare BigInt sotto pressione di tempo.

Lo abbini a un verificatore di primi ordinario quando serve solo la primalità, a un verificatore di primi gemelli quando servono primi dispari consecutivi, e a strumenti di esponenziazione modulare quando serve un pow-mod generale anziché un prodotto fattoriale specifico di Wilson.