Pagina 1 di 1

TdN: il teorema di Wilson

Inviato: 11 giu 2005, 09:27
da HiTLeuLeR
Siccome se n'è parlato di recente, colgo l'occasione per inserirlo nella lista dei topic del glossario!

Teorema di Wilson: un intero $ n \geq 2 $ è primo sse $ (n-1)! \equiv - 1 \bmod n $.

Dim. [1]: la condizione è necessaria. Infatti, se $ n $ è primo, ogni intero positivo $ k < n $ è primo con $ n $, dunque invertibile $ \!\bmod\, n $. Del resto, l'equazione $ x^2 \equiv 1 \bmod n $, quando $ n $ sia un modulo primo, possiede le uniche soluzioni modulari $ x = 1 $ ed $ x = n-1 $. Se dunque $ n \geq 5 $, gli interi $ 2, 3, \ldots, n-2 $ possono essere associati a formare $ (n-3)/2 $ coppie di tipo $ (a, b) $ in cui $ b = a^{-1} $, ove $ a^{-1} $ denota qui l'inverso di $ a $ modulo $ n $. E allora, ancora per $ n \geq 5 $: $ \displaystyle (n-1)! \equiv (n-1)\cdot \prod_{k=2}^{n-2} k $ $ \equiv (n-1) \equiv - 1 \bmod n $. La tesi è poi banalmente soddisfatta (per verifica diretta) se $ n = 2 $ oppure $ n = 3 $.

La condizione è sufficiente. Supposto infatti $ (n-1)! \equiv -1 \bmod n $, ammettiamo pur tuttavia per assurdo che $ n $ possa essere composto. Esiste allora un intero $ m > 1 $ tale che $ m \mid n $, perciocché $ m \leq n-1 $, e dunque $ (n-1)! \equiv -1 \bmod n $ solo se $ 0 \equiv (n-1)! \equiv -1 \bmod m $, che è assurdo!!! Di qui la tesi, q.e.d.

Dim. [2]: vi propongo una variante per dimostrare la parte necessaria del teorema cui ho pensato tempo fa spazzolandomi i dentuzzi. :mrgreen: Se $ n = 2 $, la tesi è banalmente verificata. Sia pertanto nel seguito $ n \geq 3 $. Poiché $ n $ è primo, esiste $ g\in\mathbb{Z} $ tale che $ g $ sia una radice primitiva $ \!\bmod n $, e per ogni $ k = 1, 2, \ldots, n-1 $ esiste dunque, e univocamente determinato, un intero $ e_k \in \{1, 2, \ldots, n-1\} $ tale che $ g^{e_k} \equiv k \bmod n $. E allora: $ \displaystyle (n-1)! \equiv \prod_{k=1}^{n-1} k \equiv $ $ \displaystyle \prod_{k=1}^{n-1} g^{e_k} \equiv g^{\sum_{k=1}^{n-1} e_k} \bmod n $. Ma $ \displaystyle\sum_{k=1}^{n-1} e_k = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} $, sicché (in ultima analisi): $ (n-1)! \equiv g^{\frac{1}{2}n(n-1)} \equiv - 1 \bmod n $, poiché (per ipotesi) $ g $ è una radice primitiva $ \!\bmod n $, e dunque (per il lemma di Eulero): $ g^{(n-1)/2} \equiv - 1 \bmod n $. Di qui l'asserto, q.e.d.

Inviato: 18 feb 2006, 19:06
da piever
Scusate ma dopo (n-1) cosa significa il simbolo "!" ?

Inviato: 18 feb 2006, 19:26
da HiTLeuLeR
Se $ n > 0 $ è un intero, si indica con $ n! $ il fattoriale di $ n $, cioè il prodotto di tutti gli interi positivi da $ 1 $ fino ad $ n $. Così, per intenderci: $ 4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24 $. Per definizione, si pone poi $ 0! = 1 $.

Inviato: 19 feb 2006, 10:33
da dimpim
HiTLeuLeR ha scritto:Per definizione, si pone poi 0! = 1.
Uhm... Questa cosa mi disordina i neuroni...

Inviato: 19 feb 2006, 12:19
da HiTLeuLeR
...e perché mai?! oO'

Inviato: 19 feb 2006, 12:37
da dimpim
Perché, se il fattoriale è il prodotto di tutti gli interi positivi da 1 a n, qualsiasi numero moltiplicato per 0 dà 0 (almeno così mi hanno insegnato)...
Per questo non capisco perché definire 0! = 1 (sono convinto che c'è un motivo, ma non riesco a trovarlo).

Inviato: 19 feb 2006, 12:42
da HiTLeuLeR
dimpim ha scritto:Perché, se il fattoriale è il prodotto di tutti gli interi positivi da 1 a n [...]
...ma questo è vero sse $ n $ è un intero $ > 0 $ (di definizione trattasi, nulla c'è da discutere). In quanto al caso in cui $ n = 0 $, in linea di principio, nulla avrebbe vietato - e nulla di fatto vieta! - di porre $ 0! := e^{i\pi} + 1 $. Soltanto che è più utile porre $ 0! := 1 $, soprattutto tenendo a mente i significati combinatorici del fattoriale...

Inviato: 19 feb 2006, 14:32
da edriv
In quanti modi puoi ordinare totalmente l'insieme vuoto?

A me viene da dire uno... quindi 0! = 1

Inviato: 19 feb 2006, 14:45
da HiTLeuLeR
Sì, edriv, però sia chiaro che questo non dimostra nulla: è solo una ragione in più a supporto della scelta (!) di porre (com'è d'uso) $ 0! := 1 $. E non è l'unica...

Inviato: 19 feb 2006, 15:02
da Oblomov
Anche a me era stato detto che il fattoriale di 0 deve essere considerato 1 per ragioni di comodità,ma ignoro quali siano esattamente.Se HiTLeuLeR o qualcun'altro può spiegarmele...
Saluti da Ob
P.S.HiT,avevo già letto del teorema di Wilson,ma non ero riuscito ad afferrarne la spiegazione.Adesso mi leggo la tua con più comodo(mi garantisci che é completa e comprensibile,please?).Di nuovo saluti,
Oblomov

Inviato: 19 feb 2006, 15:05
da HiTLeuLeR
Che sia completa posso garantirtelo; che ti sia comprensibile non dipende soltanto da me...

Inviato: 19 feb 2006, 15:13
da HiTLeuLeR
Oblomov ha scritto:Anche a me era stato detto che il fattoriale di 0 deve essere considerato 1 per ragioni di comodità, ma ignoro quali siano esattamente. Se HiTLeuLeR o qualcun'altro può spiegarmele...
"Qualcun altro" si scrive senz'apostrofo, ma a parte questo... :wink: Le ragioni combinatoriche sono state già accennate; delle altre, di natura squisitamente analitica, riguardano il fatto che una simpatica funzioncina introdotta da buon vecchio Euler - la gamma! - interpola (come si dice) il fattoriale ai numeri reali. E siccome la gamma è continua attorno allo zero e $ \Gamma(0) = 1 $, sarà parso una volta in più naturale assumere $ 0! := 1 $.

Inviato: 20 feb 2006, 08:55
da Marco
Ne aggiungo una stupida anch'io:

Se definisci il fattoriale per ricorrenza così:

$ 1! = 1 $
$ n! = n \cdot (n-1)! $,

allora l'unico modo per estendere la definizione in modo coerente a 0, è fare sì che

$ 1! = 1 \cdot 0! $, da cui $ 0! = 1 $.

Inviato: 20 feb 2006, 21:45
da ficus2002
Anch'io anch'io:

ponendo $ 0!=1 $ si può scrivere lo sviluppo di Taylor in forma compatta
$ f(x_0+h)=f\left( x_0\right) + xf'\left( x_0\right)+\ldots=\sum_{n=0}^{+\infty}\frac{f^{(n)}(x_0)}{n!}h^n $