Teorema di fermat - Considerazioni potenze modulo n.
Th Fermat
Sia $p$ un primo. Allora $AA a in ZZ : a^p-=a(modp)$.
Dalla dimostrazione di cui io sono in possesso, lo si vede come una diretta conseguenza del teorema di Eulero.
cioè
Ora , pongo a voi l'esame di controllare quest'altro tipo di dimostrazione che ho deciso di "imparare", verificando, in ciò che scrivo se ho ben inteso il ragionamento che c'è dietro.
dim (induzione su a) (metto in spoiler per guadagnare spazio.)
Che ne dite?
Conoscente altre dim di questo teorema?
-------------------------------------------------------------------------------
Osservazioni.
Sia $n in ZZ$. con $n=p_1*p_2*..........*p_n$ , primi distinti.E $a,b in ZZ$.
Per quali a e b si ha che $a^b-=0(modn)$ ??
Sono giunto alla conclusione che deve essere $a-=0(modn)$ e che in tal caso $AA b : a^p-=0(modn)$. Smentitemi se e' errata.
Cioè in linea di principio , non esistono $a
Grazie per le vostre delucidazioni.
Sia $p$ un primo. Allora $AA a in ZZ : a^p-=a(modp)$.
Dalla dimostrazione di cui io sono in possesso, lo si vede come una diretta conseguenza del teorema di Eulero.
cioè
Ora , pongo a voi l'esame di controllare quest'altro tipo di dimostrazione che ho deciso di "imparare", verificando, in ciò che scrivo se ho ben inteso il ragionamento che c'è dietro.
dim (induzione su a) (metto in spoiler per guadagnare spazio.)
Che ne dite?
Conoscente altre dim di questo teorema?
-------------------------------------------------------------------------------
Osservazioni.
Sia $n in ZZ$. con $n=p_1*p_2*..........*p_n$ , primi distinti.E $a,b in ZZ$.
Per quali a e b si ha che $a^b-=0(modn)$ ??
Sono giunto alla conclusione che deve essere $a-=0(modn)$ e che in tal caso $AA b : a^p-=0(modn)$. Smentitemi se e' errata.
Cioè in linea di principio , non esistono $a
Grazie per le vostre delucidazioni.
Risposte
La dimostrazione che preferisco fa uso dei gruppi: [tex]\mathbb{Z}/p\mathbb{Z}-\{0\}[/tex] è un gruppo moltiplicativo di ordine [tex]p-1[/tex] quindi ogni suo elemento [tex]a[/tex] verifica [tex]a^{p-1}=1[/tex], e il grosso è fatto.
Cosa vuoi dire?
"Kashaman":
ci si dovrebbe aspettare
Cosa vuoi dire?
Ciao Martino!
In buona sostanza è ciò che ho fatto io nel primo spoiler.
Comunque , per l'altra questione voglio dire questo. Forse non sono stato chiaro, cercherò di esserlo.
Prima questione :
Consideriamo $a, b ,n in ZZ, b>0$ con $n$ prodotto di primi $p_1,p_2,......,p_m$ distinti.
E' vero che $AA b in ZZ , b >0 , a^b-=0(modn) (1)<=> a-=0(mod n)$?
E cioè che non esiste $a
Supponiamo ora che esistano $\alpha_1,\alpha_2,.....,alpha_n in NN$ tali che $n= (p_1)^(\alpha_1) (p_2)^(\alpha_2) * (p_n)^(\alpha_n)$.
è vero che $EE b in ZZ, b>0 tale che a^b-=0(modn) <=> a-=0(mod p_1*p_2*******p_n)$ ?
Se non sono ancora abbastanza chiaro, dimmelo.
"Martino":
La dimostrazione che preferisco fa uso dei gruppi: [tex]\mathbb{Z}/p\mathbb{Z}-\{0\}[/tex] è un gruppo moltiplicativo di ordine [tex]p-1[/tex] quindi ogni suo elemento [tex]a[/tex] verifica [tex]a^{p-1}=1[/tex], e il grosso è fatto.
In buona sostanza è ciò che ho fatto io nel primo spoiler.
Comunque , per l'altra questione voglio dire questo. Forse non sono stato chiaro, cercherò di esserlo.
Prima questione :
Consideriamo $a, b ,n in ZZ, b>0$ con $n$ prodotto di primi $p_1,p_2,......,p_m$ distinti.
E' vero che $AA b in ZZ , b >0 , a^b-=0(modn) (1)<=> a-=0(mod n)$?
E cioè che non esiste $a
Supponiamo ora che esistano $\alpha_1,\alpha_2,.....,alpha_n in NN$ tali che $n= (p_1)^(\alpha_1) (p_2)^(\alpha_2) * (p_n)^(\alpha_n)$.
è vero che $EE b in ZZ, b>0 tale che a^b-=0(modn) <=> a-=0(mod p_1*p_2*******p_n)$ ?
Se non sono ancora abbastanza chiaro, dimmelo.
Sì è tutto giusto, ma io lo direi più semplicemente così: [tex]n[/tex] divide una potenza di [tex]a[/tex] se e solo se ogni primo che divide [tex]n[/tex] divide anche [tex]a[/tex].
è ciò che ho fatto io nel primo spoiler.Non proprio, tu hai usato il teorema di Eulero, io ho usato il fatto che [tex]\mathbb{Z}/p\mathbb{Z}[/tex] è un campo e la proprietà base dei gruppi per cui se [tex]g \in G[/tex] allora [tex]g^{|G|}=1[/tex]. Nota che il teorema di Eulero si può dimostrare allo stesso modo, osservando che il gruppo delle unità di [tex]\mathbb{Z}/n\mathbb{Z}[/tex] ha ordine [tex]\varphi(n)[/tex].
Ho capito la sottigliezza Martino, almeno credo.
Tu praticamente hai considerato $ZZ_p$ , $p$ primo. Ed hai poi considerato $(ZZ*_p,*)$ (gruppo moltiplicativo di $ZZ_p$. Hai constatato che $ZZ_p$ essendo un campo , gli elementi invertibili sono dell'ordine $p-1$ e che quindi $|U(ZZ*_p)| = p-1$. E allora $AA a in U(ZZ_p) : a^ ((|U(ZZ*_p)|)=p-1)=1_(ZZ_p) => a^(p-1)-=1(modp)=>a^p-=a(modp)$ giusto?.
Tu praticamente hai considerato $ZZ_p$ , $p$ primo. Ed hai poi considerato $(ZZ*_p,*)$ (gruppo moltiplicativo di $ZZ_p$. Hai constatato che $ZZ_p$ essendo un campo , gli elementi invertibili sono dell'ordine $p-1$ e che quindi $|U(ZZ*_p)| = p-1$. E allora $AA a in U(ZZ_p) : a^ ((|U(ZZ*_p)|)=p-1)=1_(ZZ_p) => a^(p-1)-=1(modp)=>a^p-=a(modp)$ giusto?.
Sì giusto.
Alla fine si può scegliere tale concatenazione :
Con lo stesso principio si può dimostrare Eulero. Constatando che $(U(Z_n))= f(n)$ e che quindi per gli elementi $a in ZZ$ tali che $(a,n)=1$ $a^f(n) -=1(modn)$ . Da cui, come caso particolare ,discende fermat, giusto?
Quindi , alla fine Il teorema di Eulero altro non e' che una generalizzazione di fermat.
Con lo stesso principio si può dimostrare Eulero. Constatando che $(U(Z_n))= f(n)$ e che quindi per gli elementi $a in ZZ$ tali che $(a,n)=1$ $a^f(n) -=1(modn)$ . Da cui, come caso particolare ,discende fermat, giusto?
Quindi , alla fine Il teorema di Eulero altro non e' che una generalizzazione di fermat.
Sì certo.
Thanks Martino, come sempre , molto gentile 
]Ho constatato vera anche quest'altra implicazione :
Siani $h,k,n in ZZ$ tali che $a^k-=1(modn)$ e $a^h-=1(modn) $ allora $a^(MCD(h,k))-=1(modn)$
dim
Dalle ipotesi date , si concerne che $f(n)|h$ e che $f(n)|k$.
Pertanto, posto $(h,k)$ si ha che $(h,k)=f(n)$. Dunque, la tesi risulta ovviamente valida.
Giusto ?
Siani $h,k,n in ZZ$ tali che $a^k-=1(modn)$ e $a^h-=1(modn) $ allora $a^(MCD(h,k))-=1(modn)$
dim
Dalle ipotesi date , si concerne che $f(n)|h$ e che $f(n)|k$.
Pertanto, posto $(h,k)$ si ha che $(h,k)=f(n)$. Dunque, la tesi risulta ovviamente valida.
Giusto ?
Per [tex]f(n)[/tex] intendi [tex]\varphi(n)[/tex] vero? Quello che vuoi dimostrare è giusto ma la dimostrazione è sbagliata. Invece di [tex]f(n)[/tex] devi usare l'ordine moltiplicativo di [tex]a[/tex] modulo [tex]n[/tex] (che non è detto che sia [tex]f(n)[/tex]). Inoltre dal fatto che [tex]f(n)[/tex] divide [tex]h,k[/tex] non segue che [tex]f(n)=MCD(h,k)[/tex] (è questo che intendevi?), segue solo che [tex]f(n)[/tex] divide [tex]MCD(h,k)[/tex] (per definizione di MCD), e questo ti basta per concludere.
PS. Non credo che tu possa usare il verbo "concernere" in quel contesto.
PS. Non credo che tu possa usare il verbo "concernere" in quel contesto.
Ho capito, quindi praticamente basta dire che $\phi(n)| h,k => \phi(n)| (h,k)$ da cui la tesi. Giusto? Scusa la svista-
No, come ti ripeto non puoi usare [tex]\varphi(n)[/tex], devi usare l'ordine moltiplicativo di [tex]a[/tex] modulo [tex]n[/tex].
per l'ordine di $a (modn)$ intendi al $min{n>0 | a^n-=1(modn)}$ giusto?
Sì giusto.
Ci riprovo, Allora : Sia $o(a) = min{\delta>0| a^(\delta)-=1(modn)$.
Ora essendo per ipotesi $a^h-=1(modn)$ e $a^k-=1(modn)$ segue che ,
$o(a) | h,k => o(a)| M.C.D(h,k)=d$ , da cui $d=o(a)*q , q in ZZ$ pertanto segue che $a^d-=a^(o(a)*q)-= (a^o(a))^q-=1^q-=1(modn)$
Ora essendo per ipotesi $a^h-=1(modn)$ e $a^k-=1(modn)$ segue che ,
$o(a) | h,k => o(a)| M.C.D(h,k)=d$ , da cui $d=o(a)*q , q in ZZ$ pertanto segue che $a^d-=a^(o(a)*q)-= (a^o(a))^q-=1^q-=1(modn)$
Sì giusto.
Scusatemi, magari dico una castroneria, ma il teorema di Fermat ha come ipotesi primaria che p non divida a, mentre nella relazione ( a + b ) \(\displaystyle ^p \) = a\(\displaystyle ^p \) + b\(\displaystyle ^p \) tale ipotesi non è richiesta.
Nel procedimento induttivo perciò, data l'arbitrarietà del'intero a e di p si potrebbe trovare un a per cui a = pk andando a verifcare l'ipotesi oltre il teorma di Fermat. Qualcuno mi potrebbe dire se ho detto una cosa errata, anche se l'ipotesi per p che divide a è banalmente vera.
Nel procedimento induttivo perciò, data l'arbitrarietà del'intero a e di p si potrebbe trovare un a per cui a = pk andando a verifcare l'ipotesi oltre il teorma di Fermat. Qualcuno mi potrebbe dire se ho detto una cosa errata, anche se l'ipotesi per p che divide a è banalmente vera.
Ciao Old Nick.
Il fatto è questo. Vi sono due formulazioni del teorema di Fermat.
la prima è questa:
Sia $p$ un primo. Allora $AA a in ZZ : a^p-=a(modp)$ (o equivalentemente, ragionando in termini di classi.
$[a]_p^p=[a]_p$)
Questa relazione è sempre vera. Anche per $a=pk, k in ZZ$.
Infatti,
$(pk)^p-=p^p*k^p-=0*k^p-=0-=p-=0(modp)$ ( perché essendo $ZZ_n$ commutativo, vale che $(ab)^n=a^n*b^n$))
la seconda è questa.
Sia $p$ un primo.
Allora $AA a in Z , a!=0 : a^(p-1)-=1(modp)$. Qui è richiesto il fatto che $a$ non sia multiplo di $p$-
Infatti , se $a$ fosse multiplo di $p$ allora si avrebbe che $0-=1(modp) => p|-1 = > -1=pq , q in ZZ$ il che è un assurdo essendo $p>=2$.
--------------------------------------------------------------------
La relazione $(a+b)^p-=a^p+b^p(modp)$ si chiama endomorfismo di Frobenius.
E notizie più dettagliate le puoi trovare qui --> http://it.wikipedia.org/wiki/Endomorfismo_di_Frobenius .
E' molto interessante come "Teorema".
Infatti, detto in parole povere . Se $A$ è un anello commutativo, per l'endomorfismo di frobenius,
$f:A->A $ def $AA a in A : f(a)=a^p$ ove $p$ è la caratteristica dell'anello, (cioè il suo ordine) , $f$ conserva sia la somma che il prodotto.
Il fatto è questo. Vi sono due formulazioni del teorema di Fermat.
la prima è questa:
Sia $p$ un primo. Allora $AA a in ZZ : a^p-=a(modp)$ (o equivalentemente, ragionando in termini di classi.
$[a]_p^p=[a]_p$)
Questa relazione è sempre vera. Anche per $a=pk, k in ZZ$.
Infatti,
$(pk)^p-=p^p*k^p-=0*k^p-=0-=p-=0(modp)$ ( perché essendo $ZZ_n$ commutativo, vale che $(ab)^n=a^n*b^n$))
la seconda è questa.
Sia $p$ un primo.
Allora $AA a in Z , a!=0 : a^(p-1)-=1(modp)$. Qui è richiesto il fatto che $a$ non sia multiplo di $p$-
Infatti , se $a$ fosse multiplo di $p$ allora si avrebbe che $0-=1(modp) => p|-1 = > -1=pq , q in ZZ$ il che è un assurdo essendo $p>=2$.
--------------------------------------------------------------------
La relazione $(a+b)^p-=a^p+b^p(modp)$ si chiama endomorfismo di Frobenius.
E notizie più dettagliate le puoi trovare qui --> http://it.wikipedia.org/wiki/Endomorfismo_di_Frobenius .
E' molto interessante come "Teorema".
Infatti, detto in parole povere . Se $A$ è un anello commutativo, per l'endomorfismo di frobenius,
$f:A->A $ def $AA a in A : f(a)=a^p$ ove $p$ è la caratteristica dell'anello, (cioè il suo ordine) , $f$ conserva sia la somma che il prodotto.
Ciao Kashman, prima di tutto ti rignrazio per la tua esposizione, però, secondo quanto tu mi hai esposto, mi pare nel caso
a\(\displaystyle ^ p - 1 \) = 0 mod p per p che non divide a, non può essere dimostrato con l'endomorfismo di Frobenius, poiché, a corre per tutto l'insieme degli interi minori di a e tra questi non è escluso che non ce ne sia uno multiplo di p, per cui il prcedimento induttivo verrebbe a perdere la suia efficacia. Mi potresti confutare questo mio dubbio?
Grazie
a\(\displaystyle ^ p - 1 \) = 0 mod p per p che non divide a, non può essere dimostrato con l'endomorfismo di Frobenius, poiché, a corre per tutto l'insieme degli interi minori di a e tra questi non è escluso che non ce ne sia uno multiplo di p, per cui il prcedimento induttivo verrebbe a perdere la suia efficacia. Mi potresti confutare questo mio dubbio?
Grazie
Non ho capito molto la tua richiesta, spero di non prendere cantonate.
Ciò che dice l'endomorfismo di frobenius non è altro che questo .
Se $a,b in A$ a anello con caratteristica $p$ primo, $(a+b)^p=a^p+b^p$ , sei d'accordo?
Prendiamo il caso di $ZZ_p$,
si traduce al seguente modo.
$AA a,b in ZZ_p : [(a+b)^p]_p=[a^p+b^p]_p$
dim
consideriamo $[(a+b)^p ]= [ \sum_(i =0)^p((p),(i))a^(n-i)b^i]_p=[((p),(0))a^p+((p),(1))a^(p-1)b+((p),(2))a^(p-2)b^2+..................((p),(p))b^p]_p$ , sei d'accordo? per il binomio di Newton.
Ora chiaramente$ [((p),(0))]_p=[1]_p$ e $ [((p),(p))]_p=[1]_p$
Mentre gli altri fattori $[((p),(i))]_p=[0]_p$ con $0
$=[a^p+0+0+0...........+0+b^p]_p=[a^p+b^p]_p$ . la tesi.
Ciò che dice l'endomorfismo di frobenius non è altro che questo .
Se $a,b in A$ a anello con caratteristica $p$ primo, $(a+b)^p=a^p+b^p$ , sei d'accordo?
Prendiamo il caso di $ZZ_p$,
si traduce al seguente modo.
$AA a,b in ZZ_p : [(a+b)^p]_p=[a^p+b^p]_p$
dim
consideriamo $[(a+b)^p ]= [ \sum_(i =0)^p((p),(i))a^(n-i)b^i]_p=[((p),(0))a^p+((p),(1))a^(p-1)b+((p),(2))a^(p-2)b^2+..................((p),(p))b^p]_p$ , sei d'accordo? per il binomio di Newton.
Ora chiaramente$ [((p),(0))]_p=[1]_p$ e $ [((p),(p))]_p=[1]_p$
Mentre gli altri fattori $[((p),(i))]_p=[0]_p$ con $0
$=[a^p+0+0+0...........+0+b^p]_p=[a^p+b^p]_p$ . la tesi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo