Congruenza lineare

[maluz1]

Buongiorno,
devo risolvere una congruenza lineare con un esponente e, pur avendo la soluzione, non sono riuscito a capirla.

$ x^33 -= 2 mod 55 $

Qui i passaggi:
1 - Calcolo del $ MCD(2, 55) = 1 $. 2 è quindi invertibile, di conseguenza se esiste una soluzione x dell'equazione, questa deve essere invertibile in modulo 55. Questo da cosa è dovuto?
2 - Calcolo di $ Phi(55) = 40 $. $ MCD(40, 33) = 1 $, quindi 33 è invertibile in modulo 40, poi si calcola l'inverso (d = 17). La soluzione sarà quindi $ 2^17 $. Questa è la parte dove sto avendo più difficoltà, perchè poi parte tutto da $ Phi $?
3 - Determinare il minimo rappresentate positivo di $ 2^17 $ in modulo 55, ma questo è chiaro.

Grazie

[dan952]

1) Se $x$ non fosse invertibile modulo 55 allora $(x,55)>1$ ma allora $55$ non divide $x^{33}-2$ come richiesto perché $(2,55)=1$ (e l'MCD di x e 55 quindi non divide 2)

2) $x^{33 \cdot d}-=x^{\Phi(55)+1} -= x -=2^{d} \mod 55$ per Eulero, da cui la necessità di trovare $d$

[maluz1]

Innanzitutto grazie per la risposta, in particolare però non ho capito il secondo punto, potresti spiegarmelo per favore?

[dan952]

Per il teorema di Eulero sappiamo che se $(x,n)=1$ risulta $x^{\Phi(n)} -= 1 \mod n$, quindi $x^{\Phi(n)+1} -= x \mod n$. La strategia per trovare la soluzione si basa su quest'ultima congruenza.

Ora noi sappiamo che $(33,40)=1$ dunque $33$ è invertibile modulo 40 cioè esiste $d$ tale che $33d-= 1 \mod 40$, ovvero $33d=1+40k$.
Come abbiamo detto prima $x^{40k} -= 1 \mod 40$ (se $(x,40)=1$ anche $(x^k,40)=1$) dunque $x^{40k+1} -= x \mod 40$, ma $33d=1+40k$ quindi $x^{33d} -= x -=2^d \mod 40$

[maluz1]

Ho capito, grazie mille!