Dubbio su Piccolo Teorema di Fermat

lorenzoasr1
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

Risposte
Zero87
"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...

lorenzoasr1
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 :D

lorenzoasr1
Ho approfondito un pò la lettura e mi sembra di aver capito che il corollario vale solo per p primo !

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.

Zero87
"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. :D

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.