Congruenza con a<mod

[UBun]

Ragazzi, svolgendo un esercizio sul sistema RSA basato su equazioni diofantee e su congruenze lineari, mi sono imabattuto in questa congruenza che non riesco proprio a svolgere, perché il termine a è minore di n in mod!
Dovrei svolgere la divisione di \(\displaystyle 5^{13} \) per 161..

\(\displaystyle 5^{13} \equiv 159 (mod 161) \)

So che esiste un intero r (resto) che dovrebbe essere \(\displaystyle 0\leq r <161 \), ma non riesco a procurarmelo.

Ho provato a trovare il resto della divisione di 5:161, ma non riesco a procedere perché mi esce 0,0310559. Quindi non riesco a trovare il resto!

La soluzione è 159, ma non riesco a capire come fa...

Potete aiutarmi, per favore?

[Kippis]

Stai cercando il rappresentante canonico di $ 5^(13) $ in $ ZZ_161 $. Il tuo ragionamento è sostanzialmente sbagliato, non ha senso dividere 5 per 161, visto che è già rappresentante canonico per la sua classe. A questo punto hai due possibilità: la prima è: usa la calcolatrice, dividi $ 5^(13) $ per 161 e prendine il resto, oppure scrivi $ 5^(13) $ come $ 5^(6) * 5^(6) * 5 $ .
$ 5^(6) -= 8 mod 161 $, dunque si ha $ 8 * 8 * 5 -= 320mod 161 $, da cui $ 320 -= 159mod 161 $.

[UBun]

"Kippis":Stai cercando il rappresentante canonico di $ 5^(13) $ in $ ZZ_161 $. Il tuo ragionamento è sostanzialmente sbagliato, non ha senso dividere 5 per 161, visto che è già rappresentante canonico per la sua classe. A questo punto hai due possibilità: la prima è: usa la calcolatrice, dividi $ 5^(13) $ per 161 e prendine il resto, oppure scrivi $ 5^(13) $ come $ 5^(6) * 5^(6) * 5 $ .
$ 5^(6) -= 8 mod 161 $, dunque si ha $ 8 * 8 * 5 -= 320mod 161 $, da cui $ 320 -= 159mod 161 $.

Vero, posso fattorizzare $ a=5^(13) $ per poi usare la proprietà transitiva!
Grazie mille, davvero!