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

Giovanni Barazzetta il 24 Settembre 2015 ha risposto:

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