Fermat’s Little Theorem Illustration

Fermat’s Little Theorem says that "If p is a prime number and a is an integer such that gcd(a,p) = 1, then a^(p-1) = 1 (mod p)." The proof of this aside, let's just see this in action with some concrete integers. Recall that a^(p-1) = 1 (mod p) equates to a^(p-1) / p = something remainder 1.

Example 1: p = 2, a = 11

• gcd(2,11) = 1
• a^(p-1) = 11^1 = 11
• 11 mod 2 = 1

Example 2: p = 3, a = 4

• gcd(3,4) = 1
• a^(p-1) = 4^2 = 16
• 16 mod 3 =  1

Example 3: p = 5, a = 2

• gcd(5,2) = 1
• a^(p-1) = 2^4 = 16
• 16 mod 5 = 1

 Example 4: p = 11, a = 3

• gcd(3,11) = 1
• a^(p-1) = 3^10 = 59049
• 59049 mod 11 = 1