Fermat's Theorem : Number Theory #Fermat's #Theorem : #Number #Theory
Fermat's Theorem : Statement : If p is a prime and (a,p) = 1 then a p-1 ≡ 1 (mod p). Proof : Suppose p is a prime number and (a,p) = 1. Since (a,p) = 1 then the numbers a,2a,3a,…,(p-1) are divided by p and the remainders are 1,2,3 …, (p-1) ; not necessarily in this order. Let a ≡ r 1 ( mod p), 2a ≡ r 2 ( mod p) , … , (p-1)a ≡ r p-1 ( mod p) Since r 1 , r 2 , … r p-1 are remainders obtained when a,2a,…,(p-1)a are divided by p. ∴ r 1. r 2 . … .r p-1 = 1 . 2 .3 …. . (p-1). Multiplying the above congruent relations : a . 2a. … . (p-1) ≡ r 1 r 2 …r p-1 ( mod p ) ð {1.2…....