Dubbio su Piccolo Teorema di Fermat
Ciao a tutti,
vi sottopongo un dubbio relativo al Piccolo Teorema di Fermat.
Il PTF dice che $a^p equiv a$ $(mod p)$ se p primo. Poi c'è un corollario che dice che se $MCD(a,n) = 1 rightarrow a^(p-1) equiv 1$ $(mod n)$
Ora, sto risolvendo la seguente equazione congruenziale:
$4x = 3 (mod 385)$
avrà soluzione se e solo $ MCD(a,n) | b$ e dato che in questo caso $ MCD(4,385) = 1 rightarrow 1 | 3 $ è vero !
Tramite Algoritmo Euclideo ho ottenuto l'Identità di Bezout $1 = 385 + 4(-96) $ e di conseguenza $4^-1 = -96 = 289 (mod 385)$.
Facendo la prova effettivamente $4 * 289 = 1 (mod 385) $ quindi 289 è l'opposto di 4.
Ora, se volessi ottenere l'opposto di 4 tramite PTF dovrei fare $4^(385-2)$ che però mi da:
$4^383 equiv 9 (mod 385)$
Per cui, comè possibile che anche se $MCD(a,n)=1$ il PTF non funziona? (anche $4^385$ non fà 4 e $4^384$ non fà 1 !!!)
Grazie in anticipo,
Lorenzo
vi sottopongo un dubbio relativo al Piccolo Teorema di Fermat.
Il PTF dice che $a^p equiv a$ $(mod p)$ se p primo. Poi c'è un corollario che dice che se $MCD(a,n) = 1 rightarrow a^(p-1) equiv 1$ $(mod n)$
Ora, sto risolvendo la seguente equazione congruenziale:
$4x = 3 (mod 385)$
avrà soluzione se e solo $ MCD(a,n) | b$ e dato che in questo caso $ MCD(4,385) = 1 rightarrow 1 | 3 $ è vero !
Tramite Algoritmo Euclideo ho ottenuto l'Identità di Bezout $1 = 385 + 4(-96) $ e di conseguenza $4^-1 = -96 = 289 (mod 385)$.
Facendo la prova effettivamente $4 * 289 = 1 (mod 385) $ quindi 289 è l'opposto di 4.
Ora, se volessi ottenere l'opposto di 4 tramite PTF dovrei fare $4^(385-2)$ che però mi da:
$4^383 equiv 9 (mod 385)$
Per cui, comè possibile che anche se $MCD(a,n)=1$ il PTF non funziona? (anche $4^385$ non fà 4 e $4^384$ non fà 1 !!!)
Grazie in anticipo,
Lorenzo
Risposte
"lorenzoasr":
Il PTF dice che $a^p equiv a$ $(mod p)$ se p primo. Poi c'è un corollario che dice che se $MCD(a,n) = 1 rightarrow a^(p-1) equiv 1$ $(mod n)$ [...]
Per cui, comè possibile che anche se $MCD(a,n)=1$ il PTF non funziona? (anche $4^385$ non fà 4 e $4^384$ non fà 1 !!!)
Premetto che non ho capito molto dell'intervento (e non metto in dubbio che sia per ignoranza personale), però se il tuo corollario è giusto, devi pensare al fatto che $385$ non è primo. Cioè se devi calcolare $a^p$ con $p$ primo non puoi pensare $p=385$ dato che $385$ è sicuramente divisibile per $5$.
Comunque è probabile che ho frainteso gran parte del testo...
Ciao Zero87, innanzitutto grazie per la risposta!
Riformulo il problema, dato che oggi l'ho scritto frettolosamente e con qualche inesattezza!
Mi sono trovato a risolvere questa equazione congruenziale:
$4x equiv 3 (mod 385)$
Ho ragionato come segue: riscrivo l'equazioni come classi resto
$bar{4}x =_385 bar{3}$
Questa equazione ha soluzione dato che $MCD(4,385)=1$, allora scrivendo l'Identità di Bezout trovo l'elemento $bar{4}^-1$
$1 = 385(1) + 4(-96)$
Per cui $bar{4}^-1 = bar{-96} = bar{289}$
Tornando all'equazione:
$x = bar{3} * bar{289}$
$x = bar{867} rightarrow x = bar{97}$
Ed effettivamente questa è la soluzione!
Il mio dubbio questo: posso trovare l'inverso di $bar{4}$ anche con il Piccolo Teorema di Fermat ?
Il PTF recita: $a^p equiv a (mod p)$ se $p$ primo
quindi mi verrebbe da dire che non posso applicarlo a questo caso, ma poi c'è il corollario che dice:
Se a e p sono coprimi $rightarrow$ $a^(p-1) equiv 1 (mod p)$
e di conseguenza dovrebbe valere anche il PTF (?)
In questo caso 4 e 385 sono coprimi, ma $bar{4}^(p-1) = bar{4}^(384) equiv bar{36} (mod 385) $ che è chiaramente diverso da $bar{1}$.
A questo punto è evidente che o ho smontato centinaia di anni di algebra, oppure c'è qualcosa che non mi è molto chiaro
Riformulo il problema, dato che oggi l'ho scritto frettolosamente e con qualche inesattezza!
Mi sono trovato a risolvere questa equazione congruenziale:
$4x equiv 3 (mod 385)$
Ho ragionato come segue: riscrivo l'equazioni come classi resto
$bar{4}x =_385 bar{3}$
Questa equazione ha soluzione dato che $MCD(4,385)=1$, allora scrivendo l'Identità di Bezout trovo l'elemento $bar{4}^-1$
$1 = 385(1) + 4(-96)$
Per cui $bar{4}^-1 = bar{-96} = bar{289}$
Tornando all'equazione:
$x = bar{3} * bar{289}$
$x = bar{867} rightarrow x = bar{97}$
Ed effettivamente questa è la soluzione!
Il mio dubbio questo: posso trovare l'inverso di $bar{4}$ anche con il Piccolo Teorema di Fermat ?
Il PTF recita: $a^p equiv a (mod p)$ se $p$ primo
quindi mi verrebbe da dire che non posso applicarlo a questo caso, ma poi c'è il corollario che dice:
Se a e p sono coprimi $rightarrow$ $a^(p-1) equiv 1 (mod p)$
e di conseguenza dovrebbe valere anche il PTF (?)
In questo caso 4 e 385 sono coprimi, ma $bar{4}^(p-1) = bar{4}^(384) equiv bar{36} (mod 385) $ che è chiaramente diverso da $bar{1}$.
A questo punto è evidente che o ho smontato centinaia di anni di algebra, oppure c'è qualcosa che non mi è molto chiaro
Ho approfondito un pò la lettura e mi sembra di aver capito che il corollario vale solo per p primo !
Il "corollario" di cui parli credo sia il Teorema di Eulero-Fermat, che nella sua formulazione corretta afferma che, presi $a,n\in\mathbb(Z)$ tali che $mcd(a,n)=1$ si ha $a^(\varphi(n))\equiv 1 (mod n)$, dove con $\varphi(n)$ si intende il valore della funzione di Eulero $\varphi$ calcolata in $n$.
Ma $\varphi(n)=n-1$ $\Leftrightarrow$ $n\in\mathbb(P)$.
Da cui la falla del tuo ragionamento.
Ma $\varphi(n)=n-1$ $\Leftrightarrow$ $n\in\mathbb(P)$.
Da cui la falla del tuo ragionamento.
"Nulier":
Il "corollario" di cui parli credo sia il Teorema di Eulero-Fermat, che nella sua formulazione corretta afferma che, presi $a,n\in\mathbb(Z)$ tali che $mcd(a,n)=1$ si ha $a^(\varphi(n))\equiv 1 (mod n)$, dove con $\varphi(n)$ si intende il valore della funzione di Eulero $\varphi$ calcolata in $n$.
Ma $\varphi(n)=n-1$ $\Leftrightarrow$ $n\in\mathbb(P)$.
Da cui la falla del tuo ragionamento.
Avevo anche io questo sospetto, però mi ero fidato del corollario riportato da lorenzoasr che comunque non riportava uguale perché $385$ non è primo.
Poi il fatto che tale corollario esista o no, questo lo ignoro.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo