n|(n-1)!

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Haile
Messaggi: 515
Iscritto il: 30 mag 2008, 14:29
Località: Bergamo

n|(n-1)!

Messaggio da Haile »

Da lasciare ai non troppo esperti:

Sia $ $n > 5$ $ un intero.

Si dimostri che $ $n$ $ è composto se e solo se $ $(n-1)! \equiv 0 \pmod n$ $

Buon lavoro.
[i]
Mathematical proofs are like diamonds: hard and clear.

[/i]
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Allora diciamola tutta:
mostrare che $ ~\displaystyle (n-1)! \equiv -1 \pmod n $ se (e solo se) n>1 è primo.
Avatar utente
gismondo
Messaggi: 84
Iscritto il: 05 feb 2009, 18:42
Località: Roma

Messaggio da gismondo »

(n-1)! è il prodotto di tutti i numeri interi da 1 a (n-1)
Se a questo oggetto noi sommiamo 1, otteniamo un valore (chiamiamolo A) che non può essere diviso dai numeri da 1 a (n-1) perchè darebbe resto 1.
Se A è divisibile per n, allora n dovrà essere primo, perchè se fosse composto, allora A sarebbe divisibile per uno qualsiasi dei suoi fattori, i quali però ricadono nell'intervallo 1-(n-1), che abbiamo già dimostrato non possono dividere A.
Spero sia chiaro
"Per tre cose vale la pena di vivere: la matematica, la musica e l'amore"
Avatar utente
gismondo
Messaggi: 84
Iscritto il: 05 feb 2009, 18:42
Località: Roma

Messaggio da gismondo »

(n-1)! è il prodotto di tutti i numeri interi da 1 a (n-1)
Se a questo oggetto noi sommiamo 1, otteniamo un valore (chiamiamolo A) che non può essere diviso dai numeri da 1 a (n-1) perchè darebbe resto 1.
Se A è divisibile per n, allora n dovrà essere primo, perchè se fosse composto, allora A sarebbe divisibile per uno qualsiasi dei suoi fattori, i quali però ricadono nell'intervallo 1-(n-1), che abbiamo già dimostrato non possono dividere A.
Spero sia chiaro
"Per tre cose vale la pena di vivere: la matematica, la musica e l'amore"
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

gismondo ha scritto:Spero sia chiaro
E' chiarissimo (doppiamente chiaro!), ma non risponde né al quesito di Haile, né al mio.
Avatar utente
gismondo
Messaggi: 84
Iscritto il: 05 feb 2009, 18:42
Località: Roma

Messaggio da gismondo »

(scusatemi per il doppio post precedente)
Grazie della risposta...
Potresti spiegarmi perchè non risponde al tuo quesito? Mi sembra che con quel procedimento ho fatto vedere che n dev'essere per forza primo...
Grazie
"Per tre cose vale la pena di vivere: la matematica, la musica e l'amore"
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Esatto, ma quell'implicazione l'avevo messa tra parentesi, perché banale. Quella interessante è l'altra implicazione: se n è primo, divide (n-1)!+1.
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 »

TG's problem (che avevo dimostrato per sbaglio in una discussione con jordan):
Tolti 1 e -1, ogni classe di resto si "accoppia" con il suo inverso per dare prodotto 1, mentre 1 e -1 sono gli unici inversi di sè stessi perché $ $g^{2x}\equiv1\pmod p $ ha ovviamente come uniche soluzioni $ $p-1 $ e $ $\frac{p-1}2 $. Quindi il prodotto totale è -1.
Btw per chi non lo sapesse, questo si chiama teorema di Wilson.
Rispondi