[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Il teorema di nonno Wilson

sarebbe potentissimo test di primalità, però...

Per farla breve, il teorema di Wilson può essere espresso in uno qualunque dei seguenti modi equivalenti fra di loro.

Teorema di Wilson (1)
Un numero n è primo se e solo se n divide (n-1)! + 1

Teorema di Wilson (2)
Se n è un numero primo allora (n-1)! + 1 è divisibile per n.
Se n è un numero composto allora (n-1)! + 1 non è divisibile per n.

Teorema di Wilson (3)
Sia n un numero intero maggiore di 1.
Il numero n è primo se e solo se (n -1)! = -1 (mod n)

Esempi.

19 è primo perché divide 18!+1
Infatti: 6402373705728001 / 19 = 336967037143579 (resto = 0)

21 invece non è primo perché non divide 20!+1
Infatti: 2432902008176640001 / 21 = 115852476579840000,04...

Per scoprire se un numero n è primo, basta semplicemente verificare se divide (n-1)!+1.

Il teorema di Wilson sarebbe quindi un potentissimo test di primalità, però il calcolo del fattoriale è piuttosto impegnativo.
E' più facile utilizzare il Piccolo Teorema di Fermat.

Piccolo Teorema di Fermat
Sia a un intero positivo qualsiasi.
Se p è un numero primo che non divide a, allora p divide a^p-1 - 1

Esempio.
17 divide 65535 = 2¹⁶ - 1

Ma non divaghiamo, ed ecco la domanda.

Come si dimostra il teorema di Wilson?

Nota storica. (tratta dal sito: La matematica del mondo islamico, (con qualche correzione) www.arab.it/islam/la_matemtica_del_mondo_islamico.htm)
Il matematico e astronomo persiano Abu Ali al-Hasan ibn al-Haytham (965-1040) fu probabilmente il primo a tentare di classificare tutti i numeri perfetti (numeri uguali alla somma dei propri divisori) sotto la forma 2k-1 (2k-1), in cui 2k-1 è un numero primo.
Il fatto straordinario, e assai poco noto, è che AI-Haytham enunciò quello che oggi va sotto il nome di teorema di Wilson. Secondo Al-Haytham, se p è un numero primo, allora 1 + (p-1)! è divisibile per p.
È da notare che questo teorema è chiamato teorema di Wilson perché il matematico inglese Edward Waring (1734 - 1798) scrisse nelle sue Meditationes algebraicae del 1770 che il teorema era del giudice e matematico inglese John Wilson (1741 - 1793). Né Waring né Wilson diedero però alcuna dimostrazione di questo fondamentale teorema sui numeri primi: la prima dimostrazione di cui abbiamo notizia è quella di Joseph-Louis Lagrange, del 1771 (1773?).
Insomma, prima che la teoria dei numeri giungesse a risultati più avanzati di quelli della matematica araba dovettero passare ben 750 anni.

Abu Ali al-Hasan ibn al-Haytham
(965-1040)
Matematico e astronomo persiano

Joseph-Louis Lagrange
(1736-1813)
Matematico italiano o francese?
Nacque a Torino e morì a Parigi

Ultimo aggiornamento: aprile 2005

Risposte & riflessioni

Vediamo come si può dimostrare la seguente versione.

Teorema di Wilson (3)
Sia n un numero intero maggiore di 1.
Il numero n è primo se e solo se (n -1)! = -1 (mod n)

Dobbiamo dimostrare i due versi del teorema:

a) se n è primo allora (n -1)! = -1 (mod n);
b) se (n -1)! = -1 (mod n) allora n è primo.

Ripasso di Aritmetica Modulare

Definizione di congruenza modulo n
Due numeri a, b, sono detti uguali o congrui modulo n se e solo se n|(a-b)

La scrittura n|(a-b) significa che n divide la differenza (a-b).
Di solito a, b sono interi relativi mentre n è intero positivo.

La congruenza modulo n si può esprimere così:
a mod b = n

o meglio così:
a = b (mod n)

ovvero, esiste un k intero per cui:
a - b = kn
a = kn + b

Esempi.
47 = 2 (mod 5), perché 47:5=9 con il resto di 2
16 = 1 (mod 3)
11 = 3 (mod 4)

Nota.
Si può anche dire che:
11 = -1 (mod 4) perché 3 = 4 - 1

Dimostrazione

E' facile verificare direttamente che il teorema vale per n=2, n=3.

1! = 1 (mod 2) = -1 (mod 2)

2! = 2 (mod 3) = -1 (mod 3)

Assumiamo quindi n>3.

Secondo verso del teorema.
Cominciamo col dimostrare il secondo verso, che è quello più facile.

b) se (n -1)! = -1 (mod n) allora n è primo.

Secondo la logica, l'implicazione diretta è equivalente alla sua contronominale.
Ovvero: A implica B (diretta)
è equivalente a: NON-B implica NON-A (contronominale)

Perciò dimostriamo che:

Se n NON è primo allora (n -1)! NON è -1 (mod n).

Facilissimo!
Se n non è primo, allora è composto.
Se è composto, allora è uguale al prodotto di almeno due fattori diversi da 1 e da n.
Almeno uno dei suoi fattori deve essere fra i seguenti:

2, 3, 4, ... , n-1

che sono proprio quelli che costituiscono (n-1)!
Dunque (n-1)! ed n hanno almeno un fattore comune maggiore di 1.
Dunque, la divisione (n-1)! : n non potrà dare come resto n -1.
Ovvero (n-1)! <> -1 (mod n)

Consideriamo ad esempio il numero composto 8 = 2*2*2 e il numero 7! = 7*6*5*4*3*2.
Essi hanno il fattore 2 in comune.
Eseguiamo la divisione semplificando per il fattore comune 2:
7! : 8 = 7*6*5*4*3 : 4
Il resto della divisione dovrà essere un numero minore di 4 ed è evidente che non potrà mai essere 8-1=7.
L'esempio è scritto in modo da poter essere facilmente generalizzato.

Primo verso del teorema.

Dimostriamo ora il primo verso del teorema, che è un po' più difficile.

a) se n è primo allora (n -1)! = -1 (mod n)

E' equivalente a dimostrare che:
Se n è primo allora (n -2)! = 1 (mod n)

Consideriamo ad esempio il numero primo 13 e il numero (13-2)! = 11!
11! = 11*10*9*8*7*6*5*4*3*2
Come si vede i fattori sono in numero pari e si possono raggruppare in coppie, ciascuna delle quali sia uguale a 1 (mod 13).
11*6 = 66 = 1 (mod 13)
10*4 = 40 = 1 (mod 13)
9*3 = 27 = 1 (mod 13)
8*5 = 40 = 1 (mod 13)
2*7 = 14 = 1 (mod 13)
Possiamo dunque scrivere:
11! = 11*10*9*8*7*6*5*4*3*2 = 66*40*27*40*14 = 1*1*1*1*1 = 1 (mod 13)
Moltiplichiamo ora per 12 entrambi i membri dell'uguaglianza:
11!*12 = 12! = 1*12 = 12 = -1 (mod 13)
Ed ecco che abbiamo concluso.

Ma la domanda è: dato un qualunque numero dispari fattoriale (n-2)!, si possono sempre raggruppare i fattori in coppie, ciascuna delle quali sia uguale a 1 (mod n)?

La risposta è "sì" e ci si arriva con le seguenti due definizioni e il teorema.

Definizione di numeri associati modulo n
Due numeri, il cui prodotto è congruo a 1 (mod n) si dicono associati modulo n.
In formule: se a*b = 1 (mod n) allora a e b sono associati modulo n.

Esempi.
12 e 3 sono associati modulo 35 perché 12*3 = 1 (mod 35)
12 e 38 sono associati modulo 35 perché 12*38 = 456 = 1 (mod 35)

Definizione di inverso di a (mod n)
Il minimo numero positivo fra tutti gli associati ad a si chiama inverso di a (mod n) e si denota con a^-1 oppure 1/a.

Esempio.
3 è l'inverso di 12 (mod 35)
3 = 1/12 = 12^-1 (mod 35)

Teorema
I numeri primi con n della successione
2, 3, 4, ... , n-2
si possono ripartire in (n-3)/2 coppie di numeri disuguali e inversi (mod n).

That's all folks

Sito Web realizzato da Gianfranco Bo