Teorema di Wilson

teorema usato nella teoria dei numeri

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

oppure, in forma equivalente,

(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 modifica

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 modifica

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
     
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 modifica

Prima dimostrazione modifica

Questa dimostrazione sfrutta il fatto che gli elementi invertibili dell'Anello   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   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 i2 ≡ 1 (mod p), che implica i2 − 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

 

Per esempio, se p = 11, abbiamo

 

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 modifica

Qui vi è un'altra dimostrazione del teorema.

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

 

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

 

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 modifica

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:

 
 

dove p = 2m + 1. Questo diventa:

 

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

 

Formula esatta per π(x) modifica

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

 

per ogni numero primo p, e inoltre:

 

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

 

dove   indica la parte frazionaria di x. Questa formula sfrutta il fatto che, per n > 4,   è uguale a 0 se n è composto, a   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 modifica

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

 

dove p è un primo dispari.

Proviamo la generalizzazione. Per   la verifica è immediata, pertanto considereremo gli altri casi.

I casi dove la produttoria è congrua a   sono i casi in cui il modulo è ciclico, infatti   si può partizionare in tre insiemi distinti   dove:

  ,  ,  

Ora si ha che:

 

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

 

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

 

Ma poiché   è invertibile otteniamo   , valore che avevamo escluso. Quindi si ha che in   gli opposti sono distinti e pertanto   ed enumerandoli:

 

Quindi:

 

Guardando alla definizione di   abbiamo

 

dove   è la metà del numero di soluzioni dell'equazione  . Poiché il numero di soluzioni di tale equazioni vale:

  •   se  
  •   se  
  •   se  

Qui   è una valutazione. Sostituendo otteniamo

 

dove

  •   se  
  •   se  
  •   se  

Si vede quindi che solo i moduli ciclici hanno   , mentre per i moduli non ciclici   è pari.

Teorema inverso modifica

L'inverso del teorema di Wilson afferma che, dato un numero composto  ,

 

Ciò non considera il caso  , per cui  

Infatti, se   è un fattore primo di   tale che  , la sequenza

 

include   multipli di  . Dunque la massima potenza di   che divide il fattoriale è almeno   e la massima potenza che divide   è al più

 

La disuguaglianza richiesta

 

è valida in generale, ad eccezione del caso   ed  

Note modifica

  1. ^ O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews.
  2. ^ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers," Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, vol. 2, pages 125–137 (1771).
  3. ^ Teorema fondamentale dell'algebra

Bibliografia modifica

  • 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 modifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica