OliForum Matematico

Salve. So che, se a==b mod m, allora (a^k)==(b^k) mod m per ogni k naturale. Mi chiedevo dunque se e in quali casi si potesse operare al contrario, cioè partendo da (a^k)==(b^k) mod m e arrivare ad a==b mod m, senza magari perdere soluzioni per strada o commettere un errore. Grazie a chiunque saprà rispondermi!
(Spero di non aver sbagliato sezione del Forum)

La risposta breve è "se $a$ e $b$ non hanno fattori comuni con $m$ e se lo sai per un $k$ che sia coprimo con $\varphi(m)$, allora sai che $a\equiv b \bmod m$".

Meno in breve, $\varphi(m)$ è il numero di interi tra $0$ e $m$ che sono coprimi (ovvero che non hanno divisori maggiori di $1$ in comune) con $m$, ad esempio
$$\varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(5)=4$$
e in generale, se $p>0$ è primo, $\varphi(p)=p-1$; inoltre, se $a,\ b$ sono coprimi tra loro (che, in un modo ancora diverso, si può dire $\mathrm{MCD}(a,b)=1$), allora $\varphi(ab)=\varphi(a)\varphi(b)$, quindi ad esempio $\varphi(15)=\varphi(5)\varphi(3)=4\cdot 2=8$.

Domanda bonus: quanto fa $\varphi(3^2)$? e $\varphi(5^2)$? e $\varphi(3^3)$? ... e $\varphi(p^k)$ con $p$ primo e $k$ naturale?

Poi, c'è il Teorema di Eulero-Fermat, che dice che, se $a$ e $m$ sono coprimi, allora $a^{\varphi(m)}\equiv 1 \bmod m$.

Quindi, ora, mettiamo assieme i pezzi... supponiamo che $a$ e $b$ siano coprimi con $m$ e che $k$ sia coprimo con $\varphi(m)$.
Poiché $\mathrm{MCD}(k,\varphi(m))=1$, allora esiste $s$ intero tale che $ks\equiv 1 \bmod \varphi(m)$, ovvero $ks=1+n\varphi(m)$ per qualche $n>0$, per cui
$$a^k\equiv b^k \bmod m$$
implica
$$a^{ks} \equiv b^{ks} \bmod m$$
ovvero
$$a^{1+n\varphi(m)}\equiv b^{1+n\varphi(m)} \bmod m$$
ovvero
$$a(a^{\varphi(m)})^n\equiv b(b^{\varphi(m)})^n\bmod m$$
ma per il teorema di Eulero-Fermat la roba tra parentesi è congrua a $1$ e dunque
$$a\equiv b\bmod m\;.$$

Ora, resta da capire cosa succede negli altri casi: quando $a$ e $b$ non sono coprimi con $m$ e quando magari loro lo sono con $m$, ma $k$ non lo è con $\varphi(m)$... Ma magari puoi provarci tu buttando lì un po' di esempi.

In generale, su queste cose, potresti guardarti un po' dei video di TdN 1 e 2 dei Senior basic!

Intanto ti ringrazio per la risposta tanto esauriente. Appena avrò tempo mi dedicherò ai quesiti che hai posto.

Phi(p^k) con p primo e k naturale = (p-1)p^(k-1).
Infatti, tra i numeri minori o uguali a p^k, sono tutti primi con p^k tranne i multipli di k, che sono (p^k)/p = p^(k-1). Quindi Phi(p^k) = p^k-p^(k-1) = (p-1)p^(k-1). È giusto?

È giusto!