3⁶ mod 7
aᵖ⁻¹ ≡ 1
1.
If is prime and , then . Equivalently, for every integer .
This page is easier if you are comfortable with:
Check: , so . The exponent can be reduced modulo : to find , write , so . For a larger prime, , since . This makes huge powers easy by hand; the arithmetic of remainders is explained in remainders.
The proof multiplies the residues , which are a rearrangement of modulo , so ; cancelling (invertible, see Wilson's theorem) gives the result. Another proof expands with the binomial theorem, since is divisible by for (binomial coefficients).
The generalisation to composite moduli is Euler's theorem. Fermat gives inverses, , used with linear congruences, a quick (but imperfect) primality test, and the encryption in RSA; its relative for squares is Euler's criterion.
Fermat's theorem says that powers of a number cycle back to 1 modulo a prime, which makes huge powers easy to reduce.
The cycle length 6 divides p − 1 = 6.
These examples are worked by hand, step by step, so you can compare your own working.
Verify Fermat for , .
Find .
Find .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
aᵖ⁻¹ ≡ 1
1.
100 mod 6 = 4, so 2⁴ mod 7
2.
3⁵ mod 7
5.
aᵖ⁻¹ ≡ 1
1.
If p is prime and p ∤ a then aᵖ⁻¹ ≡ 1 (mod p); equivalently aᵖ ≡ a. It reduces large exponents and gives inverses a⁻¹ ≡ aᵖ⁻².
Find 3⁶ mod 7.
Find 2¹⁰⁰ mod 7 using exponent mod 6.
Find 3⁻¹ mod 7 as 3⁵ mod 7.
Find 5¹² mod 13.
applies to 9 ✗
needs prime p ✓
Use Euler instead.
a = 7 ✗
p ∤ a ✓
Then aᵖ ≡ 0.
reduce by 7 ✗
reduce by p − 1 ✓
Period p − 1.
aᵖ ≡ 1 ✗
aᵖ⁻¹ ≡ 1 ✓
Check.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1
1
1
1
2
6
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
aᵖ⁻¹ ≡ 1 (mod p) for prime p not dividing a.
Reduce the exponent modulo p − 1.
a⁻¹ ≡ aᵖ⁻².
No; use Euler’s theorem.
Euler’s theorem and the totient.
Wilson’s theorem.
More in Discrete maths and number theory and the formula sheets.