Fermat's Little Theorem Let p be a prime Any integer that satisfies ap=a mod p and any integer a not divisible by p satisfies -ap-1=1 mod p Generalization of fermat's Little theorem due to euler If g.c.d.(a, m)=1, then a(m)=1 mod mFermat’s Little Theorem • Let p be a prime • Any integer that satisfies ap = a mod p and any integer a not divisible by p satisfies – a p-1=1 mod p • Generalization of Fermat’s Little Theorem due to Euler: – If g.c.d.(a, m) = 1, then a(m)=1 mod m