Teorema di Eulero
Ciao,
nn riesco a capire un passo della dimostrazione del teorema di Eulero, chiedo se gentilmente qualcuno puo spiegarmelo...
Teorema
se a,n sono coprimi allora $a^(phi(n))-=1modn$.$phi(n)$ e la funzione di Eulero.
dopo essere arrivato a dimostrare che $a^(p-1)-=1modp$ e che $a^(phi(p^k))-=1modp^k$, nn capisco la dimostrazione di questa congruenza: $a^(phi(n))-=1modn$. I miei vecchi appunti procedono nel seguente modo:
sia $n=p^kq^h$ e $phi(n)=phi(p^r)phi(q^h)$.
Allora $a^(phi(p^k))-=1modp^k$ cioe $a^(phi(p^r))=1+p^kl$
Poi procede cosi: $a^(phi(n))=(a^(phi(p^k)))^(phi(q^r))=(1+p^kl)^(phi(q^h))=1^(phi(q^h))$non capisco l ultima uguaglianza, quando eguaglia a 1 elevato.
Infine fa ancora due passaggi: $1^(phi(q^h))-=1modp^k$ e quindi $a^(phi(n))-=1modq^h$. Non ho capito nemmeno questi ultimi passaggi, ringrazio chiunque me li possa spiegare...ciao!
nn riesco a capire un passo della dimostrazione del teorema di Eulero, chiedo se gentilmente qualcuno puo spiegarmelo...
Teorema
se a,n sono coprimi allora $a^(phi(n))-=1modn$.$phi(n)$ e la funzione di Eulero.
dopo essere arrivato a dimostrare che $a^(p-1)-=1modp$ e che $a^(phi(p^k))-=1modp^k$, nn capisco la dimostrazione di questa congruenza: $a^(phi(n))-=1modn$. I miei vecchi appunti procedono nel seguente modo:
sia $n=p^kq^h$ e $phi(n)=phi(p^r)phi(q^h)$.
Allora $a^(phi(p^k))-=1modp^k$ cioe $a^(phi(p^r))=1+p^kl$
Poi procede cosi: $a^(phi(n))=(a^(phi(p^k)))^(phi(q^r))=(1+p^kl)^(phi(q^h))=1^(phi(q^h))$non capisco l ultima uguaglianza, quando eguaglia a 1 elevato.
Infine fa ancora due passaggi: $1^(phi(q^h))-=1modp^k$ e quindi $a^(phi(n))-=1modq^h$. Non ho capito nemmeno questi ultimi passaggi, ringrazio chiunque me li possa spiegare...ciao!
Risposte
nessuno puo aiutarmi??
C'è un po' di confusione con gli esponenti. A parte questo, l'uguaglianza $(1+p^{kl})^{\phi(q^h)}=1^{\phi(q^h)}$ di sicuro non ha senso, se non modulo qualcosa.
Per delle dimostrazioni comprensibili, guarda qui.
Per delle dimostrazioni comprensibili, guarda qui.
nn riusciamo ad aggiustare la mia?perche quella di wiki e diversa..
nessuno?sono autodidatta e nn so a chi chiedere se nn sul forum...
Potrebbe andar bene questa dimostrazione ,anche se non del tutto uguale a quella accennata
da te.
Risulta:
$a^(phi(p^k))-=1 (p^k)$ ed elevando ambo i membro a $phi(q^h)$ si ottiene:
$[a^(phi(p^k))]^(phi(q^h))-=1 (p^k)$,cioè $a^[(phi(p^k)*phi(q^h))]-=1 (p^k)$ ma $phi(p^k)*phi(q^h)=phi(n)$ e pertanto si ricava che:
$a^(phi(n))-=1 (p^k)$ Analogamente si può scrivere che $a^(phi(n))-=1 (q^h)$
Poiche' per ipotesi p^k e q^h sono coprimi ,per note proprieta' delle congruenze, sarà pure $a^(phi(n))-=1(p^k*q^h)$ e cioè $a^(phi(n))-=1 (n)$
Mi rendo conto che non è quello che ti aspettavi ( non so manco se è giusta e per la verifica lascio la parola agli esperti) ma questo mi ricordavo.
Ciao
da te.
Risulta:
$a^(phi(p^k))-=1 (p^k)$ ed elevando ambo i membro a $phi(q^h)$ si ottiene:
$[a^(phi(p^k))]^(phi(q^h))-=1 (p^k)$,cioè $a^[(phi(p^k)*phi(q^h))]-=1 (p^k)$ ma $phi(p^k)*phi(q^h)=phi(n)$ e pertanto si ricava che:
$a^(phi(n))-=1 (p^k)$ Analogamente si può scrivere che $a^(phi(n))-=1 (q^h)$
Poiche' per ipotesi p^k e q^h sono coprimi ,per note proprieta' delle congruenze, sarà pure $a^(phi(n))-=1(p^k*q^h)$ e cioè $a^(phi(n))-=1 (n)$
Mi rendo conto che non è quello che ti aspettavi ( non so manco se è giusta e per la verifica lascio la parola agli esperti) ma questo mi ricordavo.
Ciao
quando dici di elevare ad ambo i membri ne elevi soltanto uno poi perche?
Perchè ovviamente è $1^(phi(q^h))=1$.Ho adoperato la proprietà delle congruenze che dice che se $a-=b (s)$ é pure $a^n-=b^n (s)$.Nel nostro caso però risulta b=1 e quindi anche b^n=1.
Ciao.
Ciao.
ma nn e $(1*p^k)^(phi(q^h))$?
$p^k$ è il modulo rispetto al quale la congruenza è calcolata e non si deve elevare a potenza.Per esempio
se è $7-=3 (4)$ elevando al cubo si ha $7^3-=3^3 (4)$ e il modulo 4 è rimasto uguale.Quel $(p^k)$ è un simbolo ,non una espressione tra parentesi .Forse ti ha un pò ingannato il fatto che non ho scritto "mod" ma vi sono varie convenzioni nello scrivere una congruenza.
se è $7-=3 (4)$ elevando al cubo si ha $7^3-=3^3 (4)$ e il modulo 4 è rimasto uguale.Quel $(p^k)$ è un simbolo ,non una espressione tra parentesi .Forse ti ha un pò ingannato il fatto che non ho scritto "mod" ma vi sono varie convenzioni nello scrivere una congruenza.
grazie manlio, nn riesci ad assicurarmi che sia giusta la tua dimostrazione?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo