URGENTE.....Piccolo Teorema di Fermat
Determinare il resto della divisione di 190^597 per 17 usando il piccolo teorema di fermat....vorrei spiegazione dei passaggi per risolverlo!
il 23 Settembre 2015, da Andrea Manisi
Ciao Andrea! Il piccolo teorema di Fermat afferma che, se $p$ è un numero primo, per ogni numero intero $a$ vale $ a^p \equiv a \ (\text{mod } p)$, o, se $p$ non divide $a$, $$ a^{p-1} \equiv 1 \ (\text{mod } p) $$Ne abbiamo una dimostrazione qui https://library.weschool.com/lezione/piccolo-teorema-di-fermat-dimostrazione-2468.html, mentre un sacco di proprietà utili delle congruenze sono spiegate in questo video: https://library.weschool.com/lezione/aritmetica-modulare-congruenze-e-criteri-di-divisibilit%C3%A0-2470.html. Sfruttiamo tutto questo armamentario per risolvere il tuo problema. Iniziamo a ridurre l'esponente ($597$): per usare il piccolo teorema di Fermat, è utile dividerlo per $16$. Con un rapido conto scopriamo che $597 = 37 \cdot 16 + 5$. Quindi, $190^{597} = 190^{37 \cdot 16 + 5} = 190^{37 \cdot 16}\cdot 197^{5}$, da cui deduciamo che $ 190^{597} \equiv 197^5 (\text{mod }17)$. Ora tocca a $190$: siccome $190 = 10 \cdot 19$ e $19 \equiv 2 (\text{mod }17)$, otteniamo che $190^{597} \equiv 10^5 \cdot 2^5 \equiv (20)^5 \equiv 3^5 (\text{mod }17)$. Ora si tratta solo di calcolare il resto di $3^5$ diviso per $17$, che è molto meglio! Con un po' di conti, che sfruttano sempre le proprietà delle classi di resto, arriviamo al risultato: $5$. Fammi sapere se è giusto! Ciao e buona giornata :D