Fermat's little theorem and congruence equations
Studying this course? Keep your progress in one place.
Key facts
- Fermat's little theorem: if is prime and , then .
- To find , write ; then .
- has solutions if and only if divides , and then there are solutions modulo .
- If , the multiplicative inverse of comes from Bezout.
- If , divide , and by , solve, then list the solutions.
Fermat's little theorem
For a prime and not divisible by , .
Fermat's little theorem: if is prime and , then .
An equivalent form is for every integer . The proof is not required.
Example: , : . Check: , so as well.
Check both conditions first: the modulus must be prime and must not divide .
- prime,
What is ?
Reducing large powers
Reduce the base, then write the exponent as so that .
To find : write with . Then .
Reduce the base first, then the exponent. For questions, reduce each power separately, then add and reduce.
The answer is the least positive residue.
- 1
p = 7, so p − 1 = 6
Fermat: 3⁶ ≡ 1 (mod 7)
- 2
Write the exponent
100 = 16 × 6 + 4
- 3
Reduce
3¹⁰⁰ ≡ 3⁴ (mod 7)
- 4
Evaluate
3⁴ = 81 ≡ 4 (mod 7)
Worked example
Find and .
- 1
, so .
- 2
and .
- 3
.
What is ?
When ax ≡ b has solutions
Exactly when divides , and then there are solutions modulo .
Let . The congruence has a solution if and only if .
When it does, there are exactly solutions modulo (the solution set), and if there is a unique solution modulo .
Saying there is a unique solution when is a common error.
- No solutions
- One solution modulo n
and
- d solutions modulo n
Worked example
Decide how many solutions and have.
- 1
: and .
- 2
: and , so there are solutions modulo .
- 3
Dividing by : , so , giving .
How many solutions modulo does have?
Multiplicative inverses
If , Bezout gives , so is the inverse of modulo .
If , Bezout gives , so : is the multiplicative inverse of modulo . Find it with the Euclidean algorithm and back substitution.
To solve , multiply both sides by the inverse. Substitute your answer back into the original congruence to check it.
- 1
Check hcf(3, 7) = 1
so an inverse exists
- 2
Euclidean algorithm
7 = 2 × 3 + 1
- 3
Back substitute
1 = 7 − 2 × 3
- 4
Read off the inverse
3 × (−2) ≡ 1, so the inverse is −2 ≡ 5 (mod 7)
Worked example
Find the inverse of modulo and solve .
- 1
, , .
- 2
.
- 3
So , and the inverse is .
- 4
Check: .
- 5
Multiply by : .
What is the inverse of modulo ?
Solving when hcf(a, n) > 1
Divide , and by , solve the reduced congruence, then add multiples of the reduced modulus.
If divides , divide , and by to get the reduced congruence , which has and a unique solution .
The solutions modulo are .
The modulus must be divided too; dividing only and is a common slip.
- 1
Find d
, and check
- 2
Reduce
divide a, b and n by d
- 3
Solve
use the inverse modulo n′
- 4
List
add multiples of n′ to get d solutions
Worked example
Solve .
- 1
and .
- 2
Divide through by : .
- 3
The inverse of is (since ), so .
- 4
Add multiples of to list the solutions modulo .
After dividing by , the reduced congruence is...
Try an exam question
Solve the congruence , giving all solutions modulo .
[5 marks]
- [1] and , so there are solutions modulo .
- [1]Divides through by : .
- [1]The inverse of modulo is .
- [1].
- [1].
That's the notes covered.
Carry on to the next subtopic.
Try a question
Use Fermat's little theorem to find the least non-negative residue of modulo .
1 mark, marked against the mark scheme
Use Fermat's little theorem to find the least non-negative residue of modulo .
1 mark, marked against the mark scheme