Fermat's Little Theorem

Fermat's Little Theorem (FLT) is a specific case of Euler's Theorem for prime moduli. It is ubiquitous in primality testing and simplifying powers.

Statement

Theorem (Fermat's Little Theorem)

p

is a prime number and

a

is an integer not divisible by

p

a^{p - 1} \equiv 1 (mod p)

Alternatively, for any integer $a$ :

a^{p} \equiv a (mod p)

a^{p - 2}

is the modular inverse of

a

modulo

p

To compute

a^{b} (mod p)

, we can reduce the exponent

b

modulo

p - 1

a^{b} \equiv a^{b (mod p - 1)} (mod p)

Exercise (Problem 1)

Compute

2^{100} (mod 13)

Exercise (Problem 2)

Show that

n^{13} - n

is divisible by

2730

for all integers

n

. (Hint: $2730 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 13$ . Use FLT for each prime).

Exercise (Problem 3)

Find all primes

p

such that

p

divides

2^{p} + 1