TdN: il teorema di Wilson

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

TdN: il teorema di Wilson

Messaggio da HiTLeuLeR » 11 giu 2005, 09:27

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.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 18 feb 2006, 19:06

Scusate ma dopo (n-1) cosa significa il simbolo "!" ?

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 18 feb 2006, 19:26

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

Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Messaggio da dimpim » 19 feb 2006, 10:33

HiTLeuLeR ha scritto:Per definizione, si pone poi 0! = 1.
Uhm... Questa cosa mi disordina i neuroni...

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 19 feb 2006, 12:19

...e perché mai?! oO'

Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Messaggio da dimpim » 19 feb 2006, 12:37

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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 19 feb 2006, 12:42

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

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 19 feb 2006, 14:32

In quanti modi puoi ordinare totalmente l'insieme vuoto?

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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 19 feb 2006, 14:45

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

Avatar utente
Oblomov
Messaggi: 284
Iscritto il: 23 ott 2005, 13:18
Località: Bologna

Messaggio da Oblomov » 19 feb 2006, 15:02

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
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 19 feb 2006, 15:05

Che sia completa posso garantirtelo; che ti sia comprensibile non dipende soltanto da me...

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 19 feb 2006, 15:13

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

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 20 feb 2006, 08:55

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 $.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 » 20 feb 2006, 21:45

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 $

Rispondi