Piccolo Teorema di Fermat

[Drago96]

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?

[phi]

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

[Drago96]

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

Poi non ho capito come la mia sia una "ri-enunciazione"...

[phi]

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.

[Drago96]

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?

[AlanG]

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]

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]

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

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]

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]

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]

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.

[Drago96]

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.

[AlanG]

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

[Drago96]

Sì, certo che l'ho capita...
E sì, sono del 96

[AlanG]

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ì