Fermats lille teorem

Dette innlegget har allerede blitt vist 1534 ganger!

Teorem: La p være et primtall og a et heltall så p ikke deler a. Da er ap-1 ≡ 1 (mod p)

Eksempel på bruksområde: regn ut 6^195 mod 17.
17 er primtall og deler ikke 6, dermed kan vi bruke Fermats lille teorem.

Fra Fermats lille teorem har vi at 616 ≡ 1 (mod 17)
6195 = 612*16 + 3 = 616*1263≡112*63=63=216 ≡ 12 (mod 17)

Korollar: p er et primtall og a er et heltall, da er ap ≡ a (mod p). Uavhengig om pa eller ikke.

Korollar: La p være primtall og a et heltall, da er ap-1 ≡ 1 eller 0 (mod p) – 1 dersom p ikke deler a, 0 dersom p a)