PICCOLO TEOREMA DI FERMAT

Il piccolo teorema di Fermat afferma che se a è coprimo a p :

a^p-1=1 mod p

può servire per dimostrare che un numero NON è primo. In pratica dice che il periodo delle potenze con base a  mod p è un divisore di  p-1 e poi si ripetono. Ad esempio le potenze di 5,6,7… mod 11 si ripetono ogni 10 potenze. Così 5⁰=1, 5¹=5, 5²=3, 5³=4, 5⁴=9, 5⁵=1

E’ sicuramente molto utile quando si devono calcolare potenze modulo p primo.

Ad esempio: calcolare il resto di 4⁴⁰ diviso per 19.

4 è coprimo a 19 quindi 4¹⁸=1 . Scrivo 4⁴⁰= (4¹⁸)²4⁴=4⁴=(16)²=(-3)²=9

POTENZE CICLICHE MODULO n: cifra delle unità o ultime cifre

Le potenze modulo n sono clicliche con periodo d
ESEMPIO: in modulo 10 ( cifra delle unità)
potenze di 2
2^0=1
2^1=2
2^2=4
2^3=8
2^4=6
2^5=2
2^6=4
SI RIPETONO OGNI 4 termini
quindi possiamo calcolare la cifra delle unità di qualunque potenza di 2
2^134= ?  134=2 mod 4 allora 2^134=2^2=4
L' unità della potenza è 4

ALTRE POTENZE MOD 10

le cifre che si ripetono sono :

e i periodi sono :

Per ottenere le ultime due cifre di una potenza bisogna scriverlo mod 100