Esercizi con Teorema di Eulero - Fermat

Teorema di Eulero Fermat - Esercizi

Esercizio 1
Determinare le ultime due cifre di .
Svolgimento
Determinare le ultime due cifre di vuol dire determinare Siccome , per il Teorema di Eulero - Fermat, allora:
7^φ(100) ≡ 1 (mod 100). Siccome φ (100) vale 40:
7⁴⁰ ≡ 1 (mod 100).
Ora non ci resta che determinare 84539 modulo 40, con una semplice divisione. Risulta 19.
Di conseguenza, ci resta da determinare 7¹⁹ mod 100, facendo un po' di calcoli, notiamo che c'è una ripetizione periodo 4: 7, 49, 43, 1.
Siccome 19 ≡ 3 (mod 4), allora la risposta è 43.
Esercizio 2
Qual è il resto della divisione di per 37?
Svolgimento
Ricaviamo anzitutto 8213745 modulo 37: 4.
Ora dobbiamo risolvere mod 37.
Ora, siccome 37 è primo, φ (37) = 36
Allora 4³⁶ ≡ 1 (mod 37)
Ora determiniamo 987 modulo 36 con una semplice divisione: 15.
Ora non ci resta altro che determinare . Sfruttando le proprietà delle potenze (senza calcolare direttamente 4¹⁵, e si determina esattamente 11.