Piccolo Teorema di Fermat
Piccolo Teorema di Fermat
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?
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)
Re: Piccolo Teorema di Fermat
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)$".
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)$".
Re: Piccolo Teorema di Fermat
Io ho semplicemente usato quello che viene detto qua (pagg.26-27)
Poi non ho capito come la mia sia una "ri-enunciazione"...
Poi non ho capito come la mia sia una "ri-enunciazione"...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Piccolo Teorema di Fermat
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
Inoltre $ord_a(p)$ è
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.
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
(io lo scrivo in modo diverso, con $a$ e $p$ invertiti, ma mi adatterò al suo modo di dirlo).il massimo degli ordini moltiplicativi $ord_a(p)$ al variare di $a$
Inoltre $ord_a(p)$ è
Questa è precisamente la prima definizione che ti ho proposto.il più piccolo intero positivo $n$ tale che $a^n \equiv 1 (p)$.
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.
Re: Piccolo Teorema di Fermat
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?
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)
Re: Piccolo Teorema di Fermat
scusate se riesumo questo post.Ma il teorema è sbagliato. Sembra un ibrido tra il teorema di Eulero e il piccolo di fermat.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?
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.
Re: Piccolo Teorema di Fermat
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$$
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$$
Re: Piccolo Teorema di Fermat
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à.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$.
Era questo solo la mia precisazione.
Carina, non l'avevo mai vista. E' abbastanza elementare e molto intuitiva. Ho imparato una cosa nuovaBtw, 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$$
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.
Re: Piccolo Teorema di Fermat
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$
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.
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
Re: Piccolo Teorema di Fermat
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.
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.
Re: Piccolo Teorema di Fermat
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.
Re: Piccolo Teorema di Fermat
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)$
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:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Piccolo Teorema di Fermat
ciao Drago! scusa se sono stato un poco duro, è che esser precisi nell'enunciazione in un Th in matematica è molto importante capirai in seguito, perché non cominciare da ora?Drago96 ha scritto:Confermo l'opinione di EvaristeG: ho confuso ipotesi e tesi di due varianti del Piccolo di Fermat...
Se l'hai rielaborata (intendo non copiata) e capita ti faccio i miei complimenti. Piccola chicca :
Inoltre, questa è la dimostrazione che $ord_a(n)\mid\varphi(n)$Testo nascosto:
Testo nascosto:
Re: Piccolo Teorema di Fermat
Sì, certo che l'ho capita...
E sì, sono del 96
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)
Re: Piccolo Teorema di Fermat
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ì
Io sono del 92. Continua così