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