Esercizio su congruenza e resto di una divisione

[michele_7483]

Gentili utenti del forum,
potreste aiutarmi con il seguente esercizio?

Trovare il resto della divisione di $334422555^65566$ per $18$

Ho cominciato a svolgerlo così:

Considerando che $334422555^65566$ è congruo modulo $18$ con il resto $r$ della divisione, dobbiamo risolvere la seguente congruenza:

$334422555^65566 \equiv r\quad mod 18$

Che diventa

$15^65566 \equiv r \quad mod 18$

A questo punto, dato che 15 e 18 non sono coprimi, il teorema di Eulero non si può applicare, quindi come proseguire?

[Cannelloni]

La risposta è $r=9$. Per vederlo ci sono due modi, il primo è quello disperato, da usare solo in caso di emergenza: provi a fare davvero $15^{65566}$, ma lo fai un pezzo per volta, cioè
$15\cdot 15 = 225 \cong 9 mod 18$ adesso anziché $225\cdot 15$ fai
$9\cdot 15 = 135\cong 9 mod 18$ e ti accorgi che già ti puoi fermare perché sei entrato in un loop.
Quanto è disperato questo metodo? Te lo dice il modulo e non l'esponente. Il modulo è 18, è basso, puoi provare questo metodo sapendo che non farai più di 18 operazioni, che tutto sommato è umano.

Metodo 2, molto più elegante ed economico: Teorema cinese del resto. Scrivi la congruenza che ti interessa scomponendo il modulo in fattori primi
$15^{65566}\cong r mod 2$ che implica $r\cong 1 mod 2$
$15^{65566}\cong r mod 9$ che implica $r\cong 0 mod 9$ perché nel 15 c'è un 3 tra i fattori e già $15^2$ fa $0$ modulo $9$. Vedi che anche qua incontriamo il discorso del "loop". Quell'esponente gigantesco non serve a niente, da lo stesso risultato di $15^2$ o di $15^n$ con $n\geq 2$ qualsiasi.

Per finire: dettagli sul metodo 1, nel caso le cose non andassero subito bene. Fare operazioni modulo 18 significa avere 18 possibili risultati (invece che infiniti) e questo porta con se numerose implicazioni che non siamo abituati a sfruttare. Se, per esempio, invece di 15 dovevi fare 4 elevato a quel brutto esponente bastava dare un'occhiata a come si comportano le potenze di 4 modulo 18
$4^1=4$
$4^2=16$
$4^3=4^2\cdot 4 = 64 = 10$
$4^4=4^3\cdot 4 = 40 = 4$
Ecco fatto, sai che
$4^{3n+1}=4$
$4^{3n+2}=16$
$4^{3n}=10$
A questo punto calcoli il resto modulo $3$ di $65566$ e a seconda della classe di resto trovi il risultato. In questo caso $65566\cong 1 mod 3$ quindi $4^{65566}\cong 8 mod 18$