Fermat's little theorem and congruence equations

Fermat's little theorem and congruence equations

Spec 5.4 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Fermat's little theorem: if pp is prime and p∤ap\nmid a, then ap−1≡1(modp)a^{p-1}\equiv1\pmod p.
  • To find ak(modp)a^k\pmod p, write k=q(p−1)+rk=q(p-1)+r; then ak≡ara^k\equiv a^r.
  • ax≡b(modn)ax\equiv b\pmod n has solutions if and only if d=hcf(a,n)d=\text{hcf}(a,n) divides bb, and then there are dd solutions modulo nn.
  • If hcf(a,n)=1\text{hcf}(a,n)=1, the multiplicative inverse of aa comes from Bezout.
  • If d>1d>1, divide aa, bb and nn by dd, solve, then list the dd solutions.

Fermat's little theorem

For a prime pp and aa not divisible by pp, ap−1≡1(modp)a^{p-1}\equiv1\pmod p.

Fermat's little theorem: if pp is prime and p∤ap\nmid a, then ap−1≡1(modp)a^{p-1}\equiv1\pmod p.

An equivalent form is ap≡a(modp)a^p\equiv a\pmod p for every integer aa. The proof is not required.

Example: p=7p=7, a=4a=4: 46≡1(mod7)4^6\equiv1\pmod7. Check: 43=64=63+1≡14^3=64=63+1\equiv1, so 46≡14^6\equiv1 as well.

Check both conditions first: the modulus must be prime and pp must not divide aa.

01234123456Power k4^k mod 7
Powers of 4 modulo 7 repeat every 3 steps, and 3 divides p − 1 = 6.
  • pp prime, p∤ap\nmid aap−1≡1(modp)a^{p-1}\equiv1\pmod p

What is 34(mod5)3^{4}\pmod5?

Reducing large powers

Reduce the base, then write the exponent as q(p−1)+rq(p-1)+r so that ak≡ara^k\equiv a^r.

To find ak(modp)a^k\pmod p: write k=q(p−1)+rk=q(p-1)+r with 0≤r<p−10\leq r<p-1. Then ak=(ap−1)q ar≡ar(modp)a^k=(a^{p-1})^q\,a^r\equiv a^r\pmod p.

Reduce the base first, then the exponent. For ak+bm+…a^k+b^m+\dots questions, reduce each power separately, then add and reduce.

The answer is the least positive residue.

  1. 1

    p = 7, so p − 1 = 6

    Fermat: 3⁶ ≡ 1 (mod 7)

  2. 2

    Write the exponent

    100 = 16 × 6 + 4

  3. 3

    Reduce

    3¹⁰⁰ ≡ 3⁴ (mod 7)

  4. 4

    Evaluate

    3⁴ = 81 ≡ 4 (mod 7)

Finding 3¹⁰⁰ mod 7.
  • k=q(p−1)+rk=q(p-1)+rak≡ar(modp)a^k\equiv a^r\pmod p

Worked example

Find 420(mod7)4^{20}\pmod7 and 1250(mod7)12^{50}\pmod7.

What is 2100(mod11)2^{100}\pmod{11}?

When ax ≡ b has solutions

Exactly when hcf(a,n)\text{hcf}(a,n) divides bb, and then there are dd solutions modulo nn.

Let d=hcf(a,n)d=\text{hcf}(a,n). The congruence ax≡b(modn)ax\equiv b\pmod n has a solution if and only if d∣bd\mid b.

When it does, there are exactly dd solutions modulo nn (the solution set), and if d=1d=1 there is a unique solution modulo nn.

Saying there is a unique solution when hcf(a,n)>1\text{hcf}(a,n)>1 is a common error.

012345678910111213144914

d∤bd\nmid b

  • No solutions

d=1d=1

  • One solution modulo n

d>1d>1 and d∣bd\mid b

  • d solutions modulo n

Worked example

Decide how many solutions 6x≡4(mod9)6x\equiv4\pmod9 and 6x≡9(mod15)6x\equiv9\pmod{15} have.

How many solutions modulo 1212 does 4x≡8(mod12)4x\equiv8\pmod{12} have?

Multiplicative inverses

If hcf(a,n)=1\text{hcf}(a,n)=1, Bezout gives ax+ny=1ax+ny=1, so xx is the inverse of aa modulo nn.

If hcf(a,n)=1\text{hcf}(a,n)=1, Bezout gives ax+ny=1ax+ny=1, so ax≡1(modn)ax\equiv1\pmod n: xx is the multiplicative inverse of aa modulo nn. Find it with the Euclidean algorithm and back substitution.

To solve ax≡bax\equiv b, multiply both sides by the inverse. Substitute your answer back into the original congruence to check it.

  1. 1

    Check hcf(3, 7) = 1

    so an inverse exists

  2. 2

    Euclidean algorithm

    7 = 2 × 3 + 1

  3. 3

    Back substitute

    1 = 7 − 2 × 3

  4. 4

    Read off the inverse

    3 × (−2) ≡ 1, so the inverse is −2 ≡ 5 (mod 7)

Finding the inverse of 3 modulo 7.
  • hcf(a,n)=1\text{hcf}(a,n)=1ax+ny=1⇒ax≡1ax+ny=1\Rightarrow ax\equiv1

Worked example

Find the inverse of 1717 modulo 4040 and solve 17x≡9(mod40)17x\equiv9\pmod{40}.

What is the inverse of 33 modulo 77?

Solving when hcf(a, n) > 1

Divide aa, bb and nn by dd, solve the reduced congruence, then add multiples of the reduced modulus.

If d=hcf(a,n)d=\text{hcf}(a,n) divides bb, divide aa, bb and nn by dd to get the reduced congruence a′x≡b′(modn′)a'x\equiv b'\pmod{n'}, which has hcf(a′,n′)=1\text{hcf}(a',n')=1 and a unique solution x≡x0(modn′)x\equiv x_0\pmod{n'}.

The solutions modulo nn are x0,  x0+n′,  x0+2n′,…,x0+(d−1)n′x_0,\;x_0+n',\;x_0+2n',\dots,x_0+(d-1)n'.

The modulus must be divided too; dividing only aa and bb is a common slip.

  1. 1

    Find d

    d=hcf(a,n)d=\text{hcf}(a,n), and check d∣bd\mid b

  2. 2

    Reduce

    divide a, b and n by d

  3. 3

    Solve

    use the inverse modulo n′

  4. 4

    List

    add multiples of n′ to get d solutions

Solving a congruence with a common factor.

Worked example

Solve 15x≡9(mod21)15x\equiv9\pmod{21}.

After dividing 6x≡9(mod15)6x\equiv9\pmod{15} by 33, the reduced congruence is...

Try an exam question

Solve the congruence 9x≡6(mod15)9x\equiv6\pmod{15}, giving all solutions modulo 1515.

[5 marks]

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 4204^{20} modulo 77.

1 mark, marked against the mark scheme

Revision notes