Teorema di Wilson

Da Wikipedia, l'enciclopedia libera.

In Teoria dei numeri, il teorema di Wilson afferma che, dato numero primo p > 1,

$(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)$

(vedi fattoriale e aritmetica modulare per la notazione). Vale anche il teorema inverso. In parole: L’intero n ≥ 2 è primo se e solo se n divide (n−1)!+1. Tale condizione è necessaria e sufficiente per stabilire se un numero n>=2 è un numero primo.

Indice

1 Storia
2 Dimostrazioni
- 2.1 Prima dimostrazione
- 2.2 Seconda dimostrazione
3 Applicazioni
- 3.1 Formula esatta per π(x)
4 Generalizzazione
5 Teorema inverso
6 Bibliografia
7 Collegamenti esterni

[modifica] Storia

Questo teorema fu scoperto per la prima volta da Ibn al-Haytham (conosciuto anche come Alhazen), ma ha preso il nome da John Wilson (uno 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. Vi sono alcune ragioni per credere che Leibniz conoscesse questo risultato già un secolo prima, ma non lo pubblicò mai. Il numeri primi, il teorema di Wilson e altre loro proprietà hanno assunto notevole importanza nell'ambito della crittografia a partire dagli anni '70.

[modifica] Dimostrazioni

[modifica] Prima dimostrazione

Questa dimostrazione sfrutta il fatto che se p è un primo dispari, allora l'insieme G = (Z/pZ)^× = {1, 2, ... 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 or −1 (mod p), cioè i = 1 o i = p − 1.

In altri termini, 1 e p − 1 sono uno l'inverso dell'altro, ma ogni altro elemento di G ha un inverso diverso, perciò se raccogliamo gli elementi di G a coppie in questa maniera e li moltiplichiamo, il prodotto risultante sarà −1. Per esempio, se p = 11, abbiamo

$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, ed ovviamente d divide (n − 1)! ma per ipotesi, d divide anche (n − 1)! + 1, e quindi d divide 1, assurdo.

[modifica] Seconda dimostrazione

Qui vi è un'altra dimostrazione del teorema.

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

$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. Consideriamo ora il polinomio

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) è 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.

[modifica] 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:

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

$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:

$\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1}\ (\mbox{mod}\ p)$

E 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

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

[modifica] 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:

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

per ogni numero primo p, e inoltre:

$\left(n-2\right)! \equiv 0$ Mod n

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

$\pi(x)= \sum_{5 \leq n \leq x} n \left\{ \frac{\left(n-2\right)!}{n}\right\} + 2$

dove ${x}$ indica la parte frazionaria di x. Questa formula sfrutta il fatto che, per n > 4, $\left\{ \frac{\left(n-2\right)!}{n}\right\}$ è uguale a 0 se n è composto, a $\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.

[modifica] Generalizzazione

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

$\prod_{\begin{matrix} 1 \le a < m \\ (a,m)=1 \end{matrix}} a \ \equiv \ \left \{ \begin{matrix} -1\ (\mbox{mod }m) & \mbox{se } m=4,\;p^\alpha,\;2p^\alpha \\ \ \ 1\ (\mbox{mod }m) & \mbox{altrimenti} \end{matrix} \right.$

dove p è un primo dispari.

[modifica] Teorema inverso

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

n divide (n − 1)!.

Ciò non considera il caso n = 4, per cui 3! è congruo a 2 modulo 4.

Infatti se q è un fattore primo di n, tale che n = qa, i numeri

1, 2, ..., n − 1

includono a − 1 multipli di q. Dunque la massima potenza di q che divide il fattoriale è almeno n/q − 1; e la massima potenza che divide n al più

log n/log q.

La disuguaglianza richiesta

log n/log q ≤ n/q − 1

è valida in generale, ad eccezione del caso q = 2 ed n = 4.

[modifica] Bibliografia

H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo II.5

[modifica] Collegamenti esterni

[1] Saggio sui numeri primi, con una sezione dedicata al teorema di Wilson.

Estratto da "http://it.wikipedia.org../../../t/e/o/Teorema_di_Wilson_5178.html"

Categorie: Aritmetica modulare | Teoremi