Fermat's little theorem (statement): Question bank

Throughout, FLT = Fermat's Little Theorem, and $p ∤ a$ means " $p$ does not divide $a$ ".

Figure — Fermat's little theorem (statement)

True or false — justify

Every prime

p

satisfies

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

for all integers

a

False. It fails when

p ∣ a

: then

a \equiv 0

, so

a^{p - 1} \equiv 0 \neq \equiv 1

. You need the coprimality condition

g cd (a, p) = 1

(Form 1).

The alternative form

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

needs

g cd (a, p) = 1

False. That is Form 2's whole point — it holds for every integer

a

, including multiples of

p

, because both sides collapse to

0

when

p ∣ a

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

holds for one particular

a

coprime to

p

, that alone proves

p

is prime.

False. A single base can pass by luck. Carmichael Numbers (like

561

) pass for all coprime bases yet are composite; passing is evidence, never proof, of primality.

n^{m - 1} \neq \equiv 1 (mod m)

for some

a = n

with

g cd (n, m) = 1

, then

m

is definitely composite.

True. This is the contrapositive of Form 1: a genuine prime must satisfy the congruence for every coprime base, so a single failure rules primality out completely.

2^{4} \equiv 1 (mod 4)

is an instance of Fermat's Little Theorem.

False.

4

is not prime, so FLT says nothing. (And in fact

2^{4} = 16 \equiv 0 (mod 4)

.) FLT's modulus must be prime.

For prime

p

, the numbers

{1, 2, \dots, p - 1}

each have a multiplicative inverse mod

p

True. Since each is coprime to

p

, Form 1 gives

a \cdot a^{p - 2} \equiv a^{p - 1} \equiv 1

, so

a^{p - 2}

is the inverse. This is the Multiplicative Group Modulo Prime having every element invertible.

Raising to the power

p - 1

is the smallest exponent that always returns

1

for coprime

a

False — but the "smallest" depends on the base. Take the prime

p = 7

, so

p - 1 = 6

. The base

a = 2

already returns

1

at the smaller exponent

3

(since

2^{3} = 8 \equiv 1 (mod 7)

), and

3

is a divisor of

6

. So

p - 1

always works, yet an individual base's true "order" can be a proper divisor of

p - 1

Spot the error

6^{2} \equiv 1 (mod 3)

by FLT, since

p = 3

and

p - 1 = 2

." — find the flaw.

g cd (6, 3) = 3 \neq = 1

, so the coprimality condition fails and Form 1 does not apply. Correctly,

6 \equiv 0

, giving

6^{2} \equiv 0 (mod 3)

"To compute

3^{11} mod 11

I use FLT:

3^{11} \equiv 1

." — what went wrong?

The exponent is wrong. Form 1 gives

3^{10} \equiv 1

; the exponent is

p - 1 = 10

, not

p = 11

. Using

p

instead, the right statement is Form 2:

3^{11} \equiv 3 (mod 11)

2^{3} \equiv 1 (mod 4)

by FLT because

4 - 1 = 3

." — why is this nonsense?

The modulus

4

is composite, so FLT is off the table entirely. The generalization for composite moduli uses Euler's Totient Function

ϕ

, and there

ϕ (4) = 2

, not

3

— so the correct exponent isn't even

3

"Since

a^{p - 1} \equiv 1

, we may cancel and conclude

a^{p - 2} \equiv 1/ a

, so I'll just divide." — spot the sloppy step.

"Dividing" isn't a mod operation; you multiply by an inverse. The clean statement is

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

, where

a^{- 1}

is the element that multiplies

a

1

— it exists only because

g cd (a, p) = 1

4^{6} \equiv 1 (mod 6)

, so FLT works for

6

." — why is the conclusion illegitimate even though composites can accidentally satisfy such congruences?

6

is composite and

g cd (4, 6) = 2 \neq = 1

, so nothing here is FLT; it's just an arithmetic coincidence (in fact

4^{6} = 4096 \equiv 4 (mod 6)

, not

1

). A pattern matching the shape of FLT is never FLT unless the modulus is prime.

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

because every number to the

p - 1

gives

1

." — where's the trap?

0

is a multiple of

p

(it's

p \cdot 0

), so

g cd (0, p) = p \neq = 1

and the condition fails;

0^{p - 1} \equiv 0

. FLT's "every number" only means every number coprime to $p$ .

Why questions

Why does the theorem cancel

(p - 1)!

in the intuitive derivation but this cancellation would be illegal for a composite modulus?

Cancellation needs

(p - 1)!

to be invertible mod the modulus, i.e. coprime to it. For prime

p

, none of

1, \dots, p - 1

shares a factor with

p

, so

(p - 1)!

is coprime. For a composite

n

, some factor below

n

divides

n

, killing invertibility.

Why does multiplying

{1, 2, \dots, p - 1}

by a coprime

a

just permute the set rather than land two elements on the same value?

ai \equiv aj (mod p)

then

p ∣ a (i - j)

; since

p ∤ a

and

p

is prime,

p ∣ (i - j)

, forcing

i = j

. So the map is injective on a finite set, hence a bijection — a permutation (this is exactly the shuffle in the figure above).

Why is

p - 1

(and not

p

) the natural exponent in Form 1?

There are exactly

p - 1

nonzero residues coprime to

p

; that count is the order of the Multiplicative Group Modulo Prime, and by Lagrange's theorem every element raised to the group order returns the identity

1

Why does Form 2,

a^{p} \equiv a

, follow from Form 1 for coprime

a

Multiply Form 1 by

a

a \cdot a^{p - 1} \equiv a \cdot 1

, i.e.

a^{p} \equiv a

. For non-coprime

a

(a multiple of

p

) both sides are

\equiv 0

, so Form 2 still holds — that's why it's the "for all

a

" version.

Why does FLT make computing modular inverses easy for prime moduli specifically?

Because

a^{p - 2}

is a closed formula for

a^{- 1}

a \cdot a^{p - 2} = a^{p - 1} \equiv 1

. For composite

n

you have no clean formula unless

g cd (a, n) = 1

, and you'd use

a^{ϕ (n) - 1}

instead.

Why is FLT only a one-directional primality test?

Passing (

a^{n - 1} \equiv 1

) is a necessary condition for primes but not sufficient — Carmichael Numbers pass for all coprime bases. Only failing is conclusive, ruling primality out. See Properties of Prime Numbers.

Edge cases

What does FLT say when

a \equiv 1 (mod p)

Trivially consistent:

1^{p - 1} \equiv 1

. It's a valid but uninformative instance — the theorem's content is in bases that aren't already

1

What does FLT say when

a \equiv p - 1 \equiv - 1 (mod p)

(- 1)^{p - 1}

. Since

p - 1

is even for every odd prime,

(- 1)^{p - 1} = 1

, consistent with FLT. This quietly uses that all primes except

2

are odd.

Does FLT apply when

p = 2

Yes. For

p = 2

the only coprime residue is

a \equiv 1

, and

1^{2 - 1} = 1 \equiv 1 (mod 2)

. Form 2 also holds:

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

for every integer (even

\to

even, odd

\to

odd).

What happens if you plug a negative integer

a

(with

p ∤ a

) into FLT?

It still works — congruences depend only on residue classes. E.g.

(- 3)^{4} = 81 \equiv 1 (mod 5)

, matching

3^{4} \equiv 1

, because

- 3 \equiv 2

and the theorem holds for every nonzero class.

Can the exponent

p - 1

ever be replaced by a smaller number that works for all coprime bases at once for prime

p

No smaller universal exponent exists for prime

p

: some base (a "primitive root") has order exactly

p - 1

, so nothing below

p - 1

returns

1

for that base. Individual bases may have smaller orders, but not all of them.

g cd (a, p) = 1

but

a > p

, is FLT still literally true?

Yes. FLT is a statement about residue classes, so the size of

a

is irrelevant; reduce

a mod p

first if you like. E.g.

1 2^{4} \equiv 2^{4} = 16 \equiv 1 (mod 5)

Connections

Fermat's little theorem (statement) — the parent statement these traps stress-test.
Wilson's Theorem — the $(p - 1)!$ appearing above links to another prime signature.
Modular Exponentiation Algorithms — where reducing exponents mod $p - 1$ pays off.
RSA Cryptosystem — the applied stakes of getting these conditions right.