Fermat's little theorem

Problem: For prime p and a with p ∤ a, a^{p−1} ≡ 1 (mod p)

We evaluate a^{p−1} mod p exactly (and also a^p mod p) using fast modular exponentiation; we explain why the theorem holds, and verify it with multiple harness checks.

Input

When p is prime and gcd(a,p)=1, FLT gives a^{p−1} ≡ 1 (mod p); the corollary a^p ≡ a (mod p) holds for all integers a. For composite p, the congruence may fail.

Output

Residue a^{p−1} mod p
—
Residue a^{p} mod p
—
gcd(a,p)
—
p prime? (trial)
—
Verdict
—

Reason Why

Group-theoretic proof. For a prime p, the nonzero residue classes form a multiplicative group (ℤ/pℤ)^× of order p−1. The element [a] with p∤a has order dividing p−1, hence [a]^{p−1}=[1], i.e. a^{p−1} ≡ 1 (mod p).
Combinatorial proof. Consider the set S={1,2,…,p−1}. Multiplication by a permutes S modulo p when p∤a. Taking products gives a^{p−1}(p−1)! ≡ (p−1)! (mod p), and since (p−1)!≠0 (mod p), cancellation yields a^{p−1}≡1.
Corollary. For any integer a and prime p, a^p ≡ a (mod p). If p|a both sides are 0; otherwise divide by a in the previous congruence.

Check (harness)

Preloaded Checks (harness)

Each block checks a^{p−1} ≡ 1 (mod p) with gcd(a,p)=1 and notes failures for composite p.