Teorema di Wilson

In Teoria dei numeri, il teorema di Wilson afferma che, dato n > 1 naturale, esso è un numero primo se e solo se

${\displaystyle (n-1)!\ \equiv \ -1\ ({\mbox{mod}}\ n)}$ oppure, in forma equivalente, ${\displaystyle (n-2)!\ \equiv \ 1\ ({\mbox{mod}}\ n)}$

(si veda fattoriale e aritmetica modulare per la notazione). Il teorema fornisce quindi una condizione necessaria e sufficiente per stabilire se un numero n ≥ 2 è primo.

Storia

Questo teorema fu scoperto per la prima volta da Ibn al-Haytham (conosciuto anche come Alhazen) intorno all'anno mille^[1], ma ha preso il nome da John Wilson (allora studente del matematico inglese Edward Waring), che lo riscoprì più di 700 anni dopo. Waring annunciò il teorema nel 1770, nonostante né lui né Wilson possedessero una dimostrazione. Lagrange diede la prima dimostrazione nel 1773^[2]. Vi sono alcune ragioni per credere che Leibniz conoscesse questo risultato già un secolo prima, ma non lo pubblicò mai.

Esempi

Applichiamo il teorema di Wilson ai numeri 5 e 6:

• Per il numero 5 si ha: (4! + 1) = (24 + 1) = 25, che infatti è un multiplo di 5.
• Per il numero 6 si ha: (5! + 1) = (120 + 1) = 121, che non è un multiplo di 6.

La tabella seguente mostra i valori di n da 2 a 30, (n-1)! e il resto di (n-1)! nella divisione per n. Indichiamo il resto di m/n come m mod n. Se n è un numero primo, allora il colore di sfondo è rosa. E se n è un numero composto, quindi il colore di sfondo è verde pallido.

Tabella di resto modulo n

${\displaystyle n}$	${\displaystyle (n-1)!}$	${\displaystyle (n-1)!\ {\bmod {\ }}n}$
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

Dimostrazioni

Prima dimostrazione

Questa dimostrazione sfrutta il fatto che gli elementi invertibili dell'Anello ${\displaystyle \mathbb {Z} /n}$ delle classi di resto degli interi modulo n sono determinati mediante la Funzione φ di Eulero di n ovvero rappresentate dagli interi positivi m tali che m < n ed m coprimo con n. Quindi, se p è un primo, l'insieme ${\displaystyle G=(\mathbb {Z} /p)^{*}=\{1,2,\dots ,p-1\}}$ forma un gruppo nell'operazione di moltiplicazione modulo p. Ciò significa che per ogni elemento i in G, esiste un unico inverso j in G tale che ij ≡ 1 (mod p). Se i ≡ j (mod p), allora i² ≡ 1 (mod p), che implica i² − 1 = (i + 1)(i − 1) ≡ 0 (mod p), e poiché p è primo, questo implica che i ≡ 1 o −1 (mod p), cioè i = 1 o i = p − 1.

In altri termini, 1 e p − 1 sono gli unici termini che coincidono con i loro inversi, mentre ogni altro elemento di G ha un inverso diverso da sé stesso, perciò se raccogliamo gli elementi di G a coppie in questa maniera e li moltiplichiamo, il prodotto risultante sarà −1 ovvero

${\displaystyle (p-1)!=(p-1)(p-2)\cdots 2\cdot 1\equiv (p-1)\cdot 1\equiv -1\mod p}$

Per esempio, se p = 11, abbiamo

${\displaystyle 10!=1(10)(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)\ \equiv \ -1\ ({\mbox{mod}}\ 11).}$

Se p = 2, è banale la verifica del risultato.

Per quanto riguarda il teorema inverso (vedi sotto per maggiori dettagli), supponiamo che la congruenza valga per un composto n. Allora n ha un divisore proprio d tale che 1 < d < n. Ovviamente d divide (n − 1)! e, per ipotesi, d divide anche (n − 1)! + 1. Ma allora d divide anche la loro differenza, cioè d divide (n − 1)! + 1 - (n − 1)! = 1, e ciò è assurdo.

Seconda dimostrazione

Qui vi è un'altra dimostrazione del teorema.

Supponiamo che p sia un primo dispari. Si consideri il polinomio

${\displaystyle g(x)=(x-1)(x-2)\cdots (x-(p-1))}$

ricordando che se f(x) è un polinomio non nullo di grado d in un campo F, allora f(x) ammette al più d radici su F^[3]. Consideriamo ora il polinomio

${\displaystyle f(x)=g(x)-(x^{p-1}-1).}$

Poiché i coefficienti dei termini di grado massimo si annullano, possiamo dedurre che f(x) è un polinomio di grado, al più, p − 2. Riducendo modulo p, deduciamo quindi che f(x) ammette al più p − 2 radici mod p. Ma per il teorema di Fermat, ognuno degli elementi 1, 2, ..., p − 1 è una radice di f(x). Ciò è impossibile, a meno che f(x) sia identicamente zero mod p, e questo può avvenire solo se ogni coefficiente di f(x) è divisibile per p.

Ma dal momento che p è dispari, il termine costante di f(x) è uguale a (p − 1)! + 1, e da ciò segue la tesi.

Applicazioni

Il teorema di Wilson è inutilizzabile come test di primalità, dal momento che il calcolo esplicito di (n − 1)! mod p, richiedendo n moltiplicazioni, è difficile per n grande.

Usando il teorema di Wilson, abbiamo per ogni primo p:

${\displaystyle 1\cdot 2\cdots (p-1)\ \equiv \ -1\ ({\mbox{mod}}\ p)}$

${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv \ -1\ ({\mbox{mod}}\ p),}$

dove p = 2m + 1. Questo diventa:

${\displaystyle \prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}\ ({\mbox{mod}}\ p).}$

Quindi la primalità è determinata dai residui quadratici modulo p. Possiamo utilizzare questo fatto per dimostrare parte di un noto risultato: −1 è un residuo quadratico mod p se p ≡ 1 (mod 4). Supponiamo infatti p = 4k + 1 per qualche intero k. Allora possiamo prendere m = 2k nella relazione precedente e concludere che

${\displaystyle \left(\prod _{j=1}^{2k}\ j\right)^{2}=\prod _{j=1}^{2k}\ j^{2}\ \equiv (-1)^{2k+1}\ =-1({\mbox{mod}}\ p).}$

Formula esatta per π(x)

Dal teorema di Wilson si può ricavare facilmente una formula per il numero di numeri primi minori di x. Infatti vale:

${\displaystyle \left(p-1\right)!\equiv -1{\pmod {p}}}$

per ogni numero primo p, e inoltre:

${\displaystyle \left(n-2\right)!\equiv 0{\pmod {n}}}$

per ogni numero composto n > 4. Utilizzando questi fatti si dimostra che, per n ≥ 5:

${\displaystyle \pi (x)=\sum _{5\leq n\leq x}n\left\{{\frac {\left(n-2\right)!}{n}}\right\}+2,}$

dove ${\displaystyle \lbrace x\rbrace }$ indica la parte frazionaria di x. Questa formula sfrutta il fatto che, per n > 4, ${\displaystyle \left\{{\frac {\left(n-2\right)!}{n}}\right\}}$ è uguale a 0 se n è composto, a ${\displaystyle {\frac {1}{n}}}$ se n è primo. Essa risulta comunque inutile nelle applicazioni poiché richiede una mole di calcoli di gran lunga più elevata del crivello di Eratostene, e va quindi considerata solo come una curiosità matematica.

Generalizzazione

Vi è anche una generalizzazione del teorema di Wilson, dovuta a Carl Friedrich Gauss:

${\displaystyle \prod _{\begin{matrix}1\leq a<n\\(a,n)=1\end{matrix}}a\ \equiv \ \left\{{\begin{matrix}-1\ ({\mbox{mod }}n)&{\mbox{se }}n=2,4,\;p^{\alpha },\;2p^{\alpha }\\\ \ 1\ ({\mbox{mod }}n)&{\mbox{altrimenti}}\end{matrix}}\right.}$

dove p è un primo dispari.

Proviamo la generalizzazione. Per ${\displaystyle n=2}$ la verifica è immediata, pertanto considereremo gli altri casi.

I casi dove la produttoria è congrua a ${\displaystyle -1}$ sono i casi in cui il modulo è ciclico, infatti ${\displaystyle \mathbb {Z} _{n}}$ si può partizionare in tre insiemi distinti ${\displaystyle I_{0},I_{1},I_{2}}$ dove:

${\displaystyle I_{0}=\left\{x\in \mathbb {Z} _{n}:(x,n)\neq 1\right\}}$ , ${\displaystyle I_{1}=\left\{x\in \mathbb {Z} _{n}:(x,n)=1\land x^{2}\not \equiv 1{\pmod {n}}\right\}}$, ${\displaystyle I_{2}=\left\{x\in \mathbb {Z} _{n}:(x,n)=1\land x^{2}\equiv 1{\pmod {n}}\right\}.}$

Ora si ha che:

${\displaystyle \prod _{\begin{matrix}1\leq a<n\\(a,n)=1\end{matrix}}a\equiv \prod _{x\in I_{1}}x\prod _{y\in I_{2}}y{\pmod {n}}.}$

L'insieme ${\displaystyle I_{1}}$ contiene ogni elemento ed il suo inverso, pertanto la produttoria vale 1 (In questo insieme ogni elemento è distinto dal suo inverso). L'insieme ${\displaystyle I_{2}}$ contiene tutte le radici seconde dell'unità, pertanto è un gruppo rispetto alla moltiplicazione. In particolare, contenendo l'elemento ${\displaystyle -1,}$ si ha che

${\displaystyle -1,x\in I_{2}\Rightarrow -x\in I_{2}}$

e poiché ogni elemento è distinto dal suo opposto, per assurdo

${\displaystyle x\equiv -x{\pmod {n}}\Rightarrow 2x\equiv 0{\pmod {n}}.}$

Ma poiché ${\displaystyle x}$ è invertibile otteniamo ${\displaystyle n=2}$ , valore che avevamo escluso. Quindi si ha che in ${\displaystyle I_{2}}$ gli opposti sono distinti e pertanto ${\displaystyle \left|I_{2}\right|=2r}$ ed enumerandoli:

${\displaystyle I_{2}=\left\{x_{1},-x_{1},x_{2},-x_{2},\ldots ,x_{r},-x_{r}\right\}.}$

Quindi:

${\displaystyle \prod _{y\in I_{2}}y\equiv (x_{1})(-x_{1})(x_{2})(x_{2})\ldots (x_{r})(-x_{r})\equiv (-1)^{r}(x_{1})^{2}(x_{2})^{2}\ldots (x_{r})^{2}{\pmod {n}}.}$

Guardando alla definizione di ${\displaystyle I_{2}}$ abbiamo

${\displaystyle \prod _{y\in I_{2}}y\equiv (-1)^{r}{\pmod {n}},}$

dove ${\displaystyle r}$ è la metà del numero di soluzioni dell'equazione ${\displaystyle x^{2}-1\equiv 0{\pmod {n}}}$. Poiché il numero di soluzioni di tale equazioni vale:

• ${\displaystyle 2^{\omega (n)}}$ se ${\displaystyle \nu _{2}(n)=0,2;}$
• ${\displaystyle 2^{\omega (n)-1}}$ se ${\displaystyle \nu _{2}(n)=1;}$
• ${\displaystyle 2^{\omega (n)+1}}$ se ${\displaystyle \nu _{2}(n)>2.}$

Qui ${\displaystyle \nu _{2}(n)}$ è una valutazione. Sostituendo otteniamo

${\displaystyle \prod _{\begin{matrix}1\leq a<n\\(a,n)=1\end{matrix}}a\equiv (-1)^{2^{\omega (n)+s}}{\pmod {n}},}$

dove

• ${\displaystyle s=-1}$ se ${\displaystyle \nu _{2}(n)=0,2;}$
• ${\displaystyle s=-2}$ se ${\displaystyle \nu _{2}(n)=1;}$
• ${\displaystyle s=0}$ se ${\displaystyle \nu _{2}(n)>2.}$

Si vede quindi che solo i moduli ciclici hanno ${\displaystyle r=1}$ , mentre per i moduli non ciclici ${\displaystyle r}$ è pari.

Teorema inverso

L'inverso del teorema di Wilson afferma che, dato un numero composto ${\displaystyle n>5}$,

${\displaystyle n|(n-1)!.}$

Ciò non considera il caso ${\displaystyle n=4}$, per cui ${\displaystyle 3!\equiv 2{\pmod {4}}.}$

Infatti, se ${\displaystyle q}$ è un fattore primo di ${\displaystyle n}$ tale che ${\displaystyle n=qa}$, la sequenza

${\displaystyle 1,2,\cdots ,n-1}$

include ${\displaystyle a-1}$ multipli di ${\displaystyle q}$. Dunque la massima potenza di ${\displaystyle q}$ che divide il fattoriale è almeno ${\displaystyle {n \over q}-1}$ e la massima potenza che divide ${\displaystyle n}$ è al più

${\displaystyle {{\log n} \over {\log q}}.}$

La disuguaglianza richiesta

${\displaystyle {{\log n} \over {\log q}}\leq {n \over q}-1}$

è valida in generale, ad eccezione del caso ${\displaystyle q=2}$ ed ${\displaystyle n=4.}$

Note

Bibliografia

• Luca Barbieri Viale, Teorema 4.28, Che cos'è un numero ? Raffaello Cortina, 2013, ISBN 978-88-6030-604-3
• Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994, ISBN 88-08-09154-6.
• Trygve Nagell, Introduction to number theory, 2ª ed., New York, Chelsea, 2001, ISBN 0-8218-2833-9.

Collegamenti esterni

• Wilson, teorema di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) William L. Hosch, Wilson’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Teorema di Wilson, su MathWorld, Wolfram Research.
• Saggio sui numeri primi, con una sezione dedicata al teorema di Wilson (PDF), su math.unipr.it.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri