Piccolo Teorema di Fermat

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Piccolo Teorema di Fermat

Messaggio da Drago96 » 18 lug 2011, 14:06

Come molti di voi sapranno, il PTF dice che con $MCD(a,p)=1$ e $p$ primo si ha che $a^p\equiv a\pmod p$ .
Io ho trovato una dimostrazione in una riga, sfruttando gli ordini moltiplicativi.

E' noto che $ord(p^k)=p^k-p^{k-1}$, che con $k=1$ si traduce in $ord(p)=p-1$
Dato che $a^b \ mod \ m = (a \ mod \ m)^{b \ mod \ ord(m)}$ abbiamo che $a^p\equiv a^{p \ mod \ ord(p)}\equiv a^{p \ mod \ p-1}\equiv a^1 \pmod p$
C.V.D.

Penso che sia giusta, no? :)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
phi
Moderatore
Messaggi: 349
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da phi » 18 lug 2011, 15:32

A meno che io non fraintenda quello che stai dicendo (può darsi) mi pare che l'"una riga" con cui vorresti dimostrare il teorema si limiti in sostanza a ri-enunciarlo (se vuoi un po' più in generale...).
Se con $ord(m)$ intendi "il minimo naturale $k$ per cui per cui $a^k \equiv 1 (m)$ per ogni $a$ coprimo con $m$" la tua seconda riga segue banalmente, ma capirai stai precisamente invocando il PTF, apparentemente come caso particolare del teorema di Eulero ($ord_m(a)|\phi(m)$ se $(a,m)=1$).

[Postilla improbabile]Se poi per caso con quella notazione intendi "la cardinalità del gruppo moltiplicativo $(\mathbb{Z}/m\mathbb{Z})^*$, che è costituito dalle le classi di resto coprime con $m$", a quel punto è vero quel che dici all'inizio (di certo gli elementi sono $p-1$ se $p$ è primo); non è nemmeno difficile concludere giustificando come si deve la tua seconda riga (sfruttando la struttura di "gruppo" - ops, è la seconda volta che mi scappa questa parolaccia - cioè in sostanza il fatto che moltiplicare è bello e puoi fare gli inversi), ma quello che c'è di "dimostrazione" sta lì più che nelle due righe che hai scritto.[/Postilla improbabile]

In conclusione, bisogna vedere cosa intendi dire. La notazione che si usa di solito per gli ordini moltiplicativi è $ord_m(a)$ per intendere "l'ordine di $a$ modulo $m$" (minimo $k$ per cui $a^k\equiv 1 (m)$). Perciò riconosco che, qualunque cosa volesse significare, e anche se fosse standard a mia insaputa, non simpatizzo per il tuo "$ord(p)$".

Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da Drago96 » 18 lug 2011, 16:22

Io ho semplicemente usato quello che viene detto qua (pagg.26-27)

Poi non ho capito come la mia sia una "ri-enunciazione"... :roll:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
phi
Moderatore
Messaggi: 349
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da phi » 18 lug 2011, 16:50

Ok!
Scusami, ignora pure la mia seconda idea, in effetti era estremamente più probabile che intendessi la prima cosa che ho scritto.
Il tuo libro definisce $ord(p)$ come
il massimo degli ordini moltiplicativi $ord_a(p)$ al variare di $a$
(io lo scrivo in modo diverso, con $a$ e $p$ invertiti, ma mi adatterò al suo modo di dirlo).
Inoltre $ord_a(p)$ è
il più piccolo intero positivo $n$ tale che $a^n \equiv 1 (p)$.
Questa è precisamente la prima definizione che ti ho proposto.

Tu dici che è un fatto noto quanto sia $ord(p^k)$, e dunque $ord(p)$; è questo che ti contesto: come lo dimostri? Perché?
In più dovresti, se non erro, dimostrare il fatto che $ord_a(p)|ord(p)$.
Modulo questo, per me dire $ord(p)=p-1$ è praticamente dire "vale il PTF"; per questo ho parlato di rienunciare. Dare per noto $ord(p^k)=p^k−p^{k−1}$ è poi dire una cosa un po' più generale (e tendenzialmente meno facile da dimostrare) da cui ricavi banalmente il fatto che t'interessa, per cui dal mio punto di vista è un po' barare. Volendo si aggiusta tutto, ma bisogna capirsi bene su quali sono le premesse e cosa si usa per dimostrare cosa.

Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da Drago96 » 04 feb 2012, 13:29

Riprendo questa discussione in vista di Febbraio...
Se io usassi $ord(p)$ al posto di $\phi(n)$ per ridurre un esponente in una dimostrazione, varrebbe?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

AlanG
Messaggi: 24
Iscritto il: 05 set 2012, 20:26

Re: Piccolo Teorema di Fermat

Messaggio da AlanG » 07 set 2012, 13:38

Drago96 ha scritto:Come molti di voi sapranno, il PTF dice che con $MCD(a,p)=1$ e $p$ primo si ha che $a^p\equiv a\pmod p$ .
Io ho trovato una dimostrazione in una riga, sfruttando gli ordini moltiplicativi.

E' noto che $ord(p^k)=p^k-p^{k-1}$, che con $k=1$ si traduce in $ord(p)=p-1$
Dato che $a^b \ mod \ m = (a \ mod \ m)^{b \ mod \ ord(m)}$ abbiamo che $a^p\equiv a^{p \ mod \ ord(p)}\equiv a^{p \ mod \ p-1}\equiv a^1 \pmod p$
C.V.D.

Penso che sia giusta, no? :)
scusate se riesumo questo post.Ma il teorema è sbagliato. Sembra un ibrido tra il teorema di Eulero e il piccolo di fermat.

Teorema di eulero Sia $a \in Z$ sia $n$ un intero positivo. Se $(a,n)=1$ allora $a$ elevato alla funzione di eulero $\phi(n)$ è congruo ad uno modulo n.
dim si dimostra con il teorema di lagrange osservando che la cardinalità di $Z_n$ è proprio $\phi(n)$
teorema (piccolo) di fermatè meno generale, vale solo per gli $n$ primi.
Sia $p$ un primo.Allora $\forall a \in Z : a^p-=a(modp)$
dim si dimostra a partire da eulero. Notando che $\phi(p)=p-1$
oppure per induzione su $a$.


e rispondo anche aDrago96 ,con molti mesi in ritardo.
si vale. Ma è più difficile trovare l'ordine di un numero nel gruppo $Z_n$ moltiplicativo.



ciao.

EvaristeG
Site Admin
Messaggi: 4737
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da EvaristeG » 09 set 2012, 00:21

Beh, intanto l'enunciato di Drago non è sbagliato, è proprio uguale al tuo piccolo di fermat, solo che lui ha aggiunto l'ipotesi (a,p)=1 che non va qui, ma nella versione che dice che $a^{p-1}\equiv 1\bmod p$.

Poi il succo dei precedenti post era che dimostrare questo teorema USANDO il fatto che l'ordine di a mod p divide p-1 è un po' barare: il difficile è proprio quest'ultima parte. Far poi discendere quest'ultima parte dal fatto che in generale l'ordine di a mod n divide $\varphi(n)$, beh, è barare un'altra volta, visto che questo secondo fatto è più complicato da dimostrare del precedente. Invocare lagrange, ci lascia col problema di dimostrare che la cardinalità del gruppo moltiplicativo mod n è proprio $\varphi(n)$ e se poi uno definisce proprio $\varphi(n)$ in questo modo, allora si ha il problema di dimostrare una qualche formula per $\varphi(n)$.

Insomma, le dimostrazioni da una riga nascondono dentro di esse l'omessa dimostrazione di un altro fatto che alla fin fine è abbastanza equivalente o addirittura più generale di quello che si vuol dimostrare.

Btw, nelle olimpiadi di solito non si insegna a gente che sa la teoria dei gruppi, quindi le dimostrazioni che si trovano nel materiale degli stages olimpici quasi mai utilizzano cose come il teorema di lagrange o simili. In particolare, la dimostrazione solita del piccolo teorema di Fermat è questa:

Sia $p$ un primo e $a$ un intero tale che $(a,p)=1$. Consideriamo l'insieme
$$A=\{a, 2a, 3a, \ldots, (p-1)a\}$$
Poiché $(a,p)=1$, si ha che $ha\equiv ka \bmod p$ se e solo se $h\equiv k\bmod p$, ma se $1\leq h,k\leq p-1$, questo implica $h=k$.
Dunque, modulo $p$, l'insieme $A$ è equivalente a $\{1,\ldots, p-1\}$. Questo vuol dire che (tutte le congruenze sono mod p)
$$a\cdot 2a\cdot 3a\cdot\ldots\cdot (p-1)a\equiv 1\cdot2\cdot3\cdot\ldots\cdot p-1$$
ovvero
$$a^{p-1}(p-1)!\equiv (p-1)!$$
e poichè $(p-1)!$ non è zero mod p, possiamo dividere ottenendo
$$a^{p-1}\equiv 1$$

AlanG
Messaggi: 24
Iscritto il: 05 set 2012, 20:26

Re: Piccolo Teorema di Fermat

Messaggio da AlanG » 09 set 2012, 02:12

EvaristeG ha scritto:Beh, intanto l'enunciato di Drago non è sbagliato, è proprio uguale al tuo piccolo di fermat, solo che lui ha aggiunto l'ipotesi (a,p)=1 che non va qui, ma nella versione che dice che $a^{p-1}\equiv 1\bmod p$.
Giusto. Ma converrai con me che i due enunciati non sono strettamente equivalenti. Il primo è generale, vale per ogni intero. Anche per i multipli di $p$, il secondo invece no, vale solo per i non multipli di $p$. Aggiungere l'ipotesi $(a,p)=1$ all'enunciato del primo post, fa perdere la generalità.
Era questo solo la mia precisazione.
Btw, nelle olimpiadi di solito non si insegna a gente che sa la teoria dei gruppi, quindi le dimostrazioni che si trovano nel materiale degli stages olimpici quasi mai utilizzano cose come il teorema di lagrange o simili. In particolare, la dimostrazione solita del piccolo teorema di Fermat è questa:

Sia $p$ un primo e $a$ un intero tale che $(a,p)=1$. Consideriamo l'insieme
$$A=\{a, 2a, 3a, \ldots, (p-1)a\}$$
Poiché $(a,p)=1$, si ha che $ha\equiv ka \bmod p$ se e solo se $h\equiv k\bmod p$, ma se $1\leq h,k\leq p-1$, questo implica $h=k$.
Dunque, modulo $p$, l'insieme $A$ è equivalente a $\{1,\ldots, p-1\}$. Questo vuol dire che (tutte le congruenze sono mod p)
$$a\cdot 2a\cdot 3a\cdot\ldots\cdot (p-1)a\equiv 1\cdot2\cdot3\cdot\ldots\cdot p-1$$
ovvero
$$a^{p-1}(p-1)!\equiv (p-1)!$$
e poichè $(p-1)!$ non è zero mod p, possiamo dividere ottenendo
$$a^{p-1}\equiv 1$$
Carina, non l'avevo mai vista. E' abbastanza elementare e molto intuitiva. Ho imparato una cosa nuova :wink:

dato che siamo in tema, ne posto un'altra variante decisamente più abbordabile. fa uso del principio di induzione.
dim Sia $p \in Z$ un primo voglio mostrare che $\forall a \in Z : a^p-=a(modp)$
lemma Per ogni $a$ e per ogni $b$ interi vale : $(a+b)^p-=a^p+b^p(modp)$
dim lemma Sviluppando $(a+b)^n$ con il binomio di Newton si verifica facilmente che i termini nell'inframezzo di $a^p$ e $b^p$ conservano il fattore $p$ , pertanto son tutti congrui a zero modulo $p$ ne segue allora la tesi.
continua dimostrazione Procediamo per induzione su $a$.
Base induzione : Per $a=0$ la tesi è vera infatti $0^p-=0(modp)$
Ipotesi induttiva. Supponiamo vera la tesi per $a$
dimostriamola per $a+1$
passo induttivo : distinguiamo due casi se $a>=0$
abbiamo che $(a+1)^p-=${per il lemma e l'ipotesi induttiva }$a^p+1^p-=a^p+1$
se $a<0$ allora $-a>0$ segue allora che $(-a)^p-=-a(modp)$ ma allora
$0=0^p=(a+(-a))^p-=a^p+(-a)^p-=a^p+(-a)(modp)$ e dunque $a^p-=a(modp)$

Cordiali saluti.

EvaristeG
Site Admin
Messaggi: 4737
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da EvaristeG » 09 set 2012, 13:05

I due enunciati sono equivalenti:
se per ogni $a$ con $(a,p)=1$ vale $a^{p-1}\equiv 1 \bmod p$, allora moltiplicando per $a$ si ha $a^p\equiv a \bmod p$ che vale anche banalmente se $p\vert a$.
se per ogni $a$ si ha $a^p\equiv a \bmod p$, allora se $(a,p)=1$ possiamo dividere per $a$ ottenendo $a^{p-1}\equiv 1\bmod p$.

Comunque, per fare il simbolo di congruenza, invece di usare quella buffa notazione $-=$, ti consiglierei di usare $\equiv$

Codice: Seleziona tutto

\equiv
E in generale, se vuoi sapere come si scrive una formula, basta farci click sopra col destro e selezionare show source (o l'equivalente), per vedere il sorgente tex.

AlanG
Messaggi: 24
Iscritto il: 05 set 2012, 20:26

Re: Piccolo Teorema di Fermat

Messaggio da AlanG » 09 set 2012, 15:08

No forse non mi sono spiegato.
Questo enunciato :
Sia $p\in Z$, un primo.$\forall a \in Z : a^p\equiv a(modp)$
non è equivalente a questo :
Sia $p$ un primo. $a \in Z$ tale che $(a,p)=1$ . Allora $a^p\equiv a(modp)$.
Sono entrambi veri, ma al secondo si assegnano ipotesi aggiuntive che fan perdere generalità. A mio parere è formalmente scorretto, anche se vero.
che poi dal primo enunciato si deduce quest'altro :
$p$ primo, $a \in Z$ t.c $(a,p)=1$ Allora $a^{p-1}\equiv1(modp)$ è ovvio.

EvaristeG
Site Admin
Messaggi: 4737
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da EvaristeG » 09 set 2012, 21:50

Come vuoi, le opinioni sono gratis e ognuno ne può avere una ... secondo me è semplicemente stato un errore "da studio" ... cioè si è confuso mentre scriveva. Visto che tu avevi detto "è falso", ho voluto precisare, per i passanti, che più che falso gli era scappata dentro una formula da una formulazione alternativa dello stesso teorema.

Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da Drago96 » 10 set 2012, 11:32

Confermo l'opinione di EvaristeG: ho confuso ipotesi e tesi di due varianti del Piccolo di Fermat... :)

Comunque, se ti può interessare, anche la dimostrazione del Teorema di Eulero è simile (prendi l'insieme dei coprimi, moltiplichi ogni elemento per $a$ coprimo, vedi che gli insiemi sono lo stesso $\mod n$, moltiplichi tutto e "semplifichi") ;)

Inoltre, questa è la dimostrazione che $ord_a(n)\mid\varphi(n)$
Testo nascosto:
Siano $q,r\in\mathbb Z : \varphi(n)=q\cdot ord_a(n)+r$, con $0<r<ord_a(n)$ (divisione euclidea con resto).
Dunque $1\equiv a^{\varphi(n)}\equiv a^{q\cdot ord_a(n)+r}\equiv \left(a^{ord_a(n)}\right)^q\cdot a^r\equiv1^q\cdot a^r\equiv a^r\pmod n$.
Ma $ord_a(n)$ è per definizione il più piccolo $k$ tale che $a^k\equiv1\pmod n$; ma $r<ord_a(n)$: assurdo.
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

AlanG
Messaggi: 24
Iscritto il: 05 set 2012, 20:26

Re: Piccolo Teorema di Fermat

Messaggio da AlanG » 10 set 2012, 16:55

Drago96 ha scritto:Confermo l'opinione di EvaristeG: ho confuso ipotesi e tesi di due varianti del Piccolo di Fermat... :)
ciao Drago! scusa se sono stato un poco duro, è che esser precisi nell'enunciazione in un Th in matematica è molto importante :wink: capirai in seguito, perché non cominciare da ora?

Inoltre, questa è la dimostrazione che $ord_a(n)\mid\varphi(n)$
Testo nascosto:
Siano $q,r\in\mathbb Z : \varphi(n)=q\cdot ord_a(n)+r$, con $0<r<ord_a(n)$ (divisione euclidea con resto).
Dunque $1\equiv a^{\varphi(n)}\equiv a^{q\cdot ord_a(n)+r}\equiv \left(a^{ord_a(n)}\right)^q\cdot a^r\equiv1^q\cdot a^r\equiv a^r\pmod n$.
Ma $ord_a(n)$ è per definizione il più piccolo $k$ tale che $a^k\equiv1\pmod n$; ma $r<ord_a(n)$: assurdo.
Se l'hai rielaborata (intendo non copiata) e capita ti faccio i miei complimenti. Piccola chicca :
Testo nascosto:
se mai studierai matematica, quella cosa vale per ogni gruppo abeliano finito <- leggi se ti può interessare, a titolo informativo.
PS : davvero sei del 96?

Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Piccolo Teorema di Fermat

Messaggio da Drago96 » 10 set 2012, 18:44

Sì, certo che l'ho capita... :D
E sì, sono del 96 :)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

AlanG
Messaggi: 24
Iscritto il: 05 set 2012, 20:26

Re: Piccolo Teorema di Fermat

Messaggio da AlanG » 10 set 2012, 18:47

complimenti, sei giovane. Fai il terzo giusto? o giù di li. Io alla tua età non sapevo che esistesse un teorema chiamato piccolo teorema di Fermat XD
Io sono del 92. Continua così

Rispondi