FP2 5.4 - Fermat's little theorem | Edexcel A-Level Further Mathematics

Use Fermat's little theorem to reduce large powers modulo a prime (FP2 5.4). You will check its conditions, reduce exponents, use convenient signed bases and finish with the requested residue.

Check the prime modulus and the base

What is the remainder when $7^{1000}$ is divided by $13$ ? Expanding the power would bury the answer in an enormous integer. Fermat's little theorem lets you replace long stretches of multiplication by a return to residue $1$ .

You already know

With a fixed modulus, congruences are preserved by multiplication and positive integer powers. A negative representative is allowed during working. The least nonnegative residue lies in $0,\ldots,n-1$ ; the least positive representative lies in $1,\ldots,n$ .

Here is the concrete pattern behind the shortcut: modulo $13$ , repeatedly multiplying by $7$ eventually returns to $1$ , with $7^{12}\equiv1\pmod{13}$ . The theorem gives such a guaranteed return for every base not divisible by a prime modulus.

Fermat's little theorem

If $p$ is prime and $a$ is an integer not divisible by $p$ , then

a^{p-1}\equiv1\pmod p

An equivalent form, valid for every integer $a$ when $p$ is prime, is

a^p\equiv a\pmod p

The first form requires $\gcd(a,p)=1$ . If $p\mid a$ , every positive power of $a$ is congruent to $0\pmod p$ .

Not in the formula booklet: learn it.

For a prime $p$ , either $p\mid a$ or $\gcd(a,p)=1$ . Multiplying the first form by $a$ gives the second in the coprime case; the divisible case gives zero on both sides. Conversely, safe cancellation of $a$ in the second form gives the first when $\gcd(a,p)=1$ . A proof of the theorem itself is not required.

Worked example 1: both forms apply

Question. Use Fermat's little theorem to determine the least nonnegative residues of $4^{12}$ and $4^{13}$ modulo $13$ .

Plan. Check that the modulus is prime and the base is not divisible by it, then identify the exponents $p-1$ and $p$ .

\begin{aligned} 13&\text{ is prime},\qquad13\nmid4 &&\text{check both conditions}\\ 4^{12}&\equiv1\pmod{13} &&\text{the }p-1\text{ form}\\ 4^{13}&\equiv4\pmod{13} &&\text{the }p\text{ form} \end{aligned}

Why this step? The exponent yielding residue $1$ is one less than the prime modulus, not the prime modulus itself.

Answer. The residues are $1$ and $4$ , respectively.

Check. $4^3=64\equiv-1\pmod{13}$ , so $4^{12}=(4^3)^4\equiv(-1)^4=1\pmod{13}$ ; one more factor of $4$ gives residue $4$ .

Change only the base from $4$ to $26$ , keeping the two exponents and the modulus fixed. One theorem condition now fails.

Worked example 2: the base is divisible by the prime

Question. Determine the least nonnegative residues of $26^{12}$ and $26^{13}$ modulo $13$ . Explain which form of Fermat's little theorem applies.

Plan. Check divisibility before using the $p-1$ form; use the power law for a zero residue.

\begin{aligned} 26&=2(13)\equiv0\pmod{13} &&\text{the base is divisible by }13\\ 26^{12}&\equiv0^{12}=0\pmod{13} &&\text{power law}\\ 26^{13}&\equiv26\equiv0\pmod{13} &&\text{the }p\text{ form still applies} \end{aligned}

Why this step? The statement $26^{12}\equiv1\pmod{13}$ would use the first form outside its domain.

Answer. Both residues are $0$ . The $p$ form applies, but the $p-1$ form does not.

Check. Every positive power of $26=2(13)$ contains a factor of $13$ .

The modulus and the base play different roles: primeness is a condition on the modulus, while coprimality is the additional condition for the $p-1$ form.

Watch out

Do not write $a^p\equiv1\pmod p$ as Fermat's theorem. With $a=4,\ p=13$ , the correct line is $4^{13}\equiv4\pmod{13}$ ; the exponent that gives $1$ is $12$ . Also check $p\nmid a$ before using that $p-1$ form.

State the applicable theorem before reducing powers; this makes the role of its conditions visible.

Remove complete blocks of the exponent

Once $a^{p-1}\equiv1\pmod p$ , every complete block of $p-1$ factors contributes residue $1$ . Divide the exponent by $p-1$ , then retain its remainder.

Exponent reduction using Fermat

For prime $p$ , integer $a$ with $p\nmid a$ , and nonnegative integer $N$ , write

N=q(p-1)+r,\qquad0\leq r<p-1

Then

a^N=(a^{p-1})^q a^r\equiv1^q a^r\equiv a^r\pmod p

When $r=0$ , the retained power is $a^0=1$ .

Not in the formula booklet: learn it.

This reduces the exponent modulo $p-1$ ; the value of the power is still reduced modulo $p$ . Those are different jobs.

Worked example 3: a thousand factors become four

Question. Use Fermat's little theorem to determine the least positive residue of $7^{1000}$ modulo $13$ . Show detailed reasoning.

Plan. State the theorem for this base and prime, divide $1000$ by $12$ , then evaluate only the retained power.

\begin{aligned} 7^{12}&\equiv1\pmod{13} &&13\text{ prime},\ 13\nmid7\\ 1000&=83(12)+4 &&\text{divide the exponent by }p-1\\ 7^{1000}&=(7^{12})^{83}7^4\equiv7^4\pmod{13} &&\text{remove complete blocks}\\ 7^2&=49\equiv10\pmod{13} &&\text{reduce a smaller power}\\ 7^4&\equiv10^2=100\equiv9\pmod{13} &&\text{square and reduce} \end{aligned}

Why this step? Reducing the exponent before calculating the remaining power is precisely the use of Fermat's theorem requested in the question.

Answer. The least positive residue is $9$ .

Check. $7^4=2401=184(13)+9$ , and $1\leq9<13$ .

Increase only the exponent by $1$ . The same complete blocks remain, but the retained power gains one factor of $7$ .

Worked example 4: one extra factor

Question. Use Fermat's little theorem to determine the least positive residue of $7^{1001}$ modulo $13$ .

Plan. Use the same theorem and divide the new exponent by $12$ ; reuse the known residue of $7^4$ .

\begin{aligned} 7^{12}&\equiv1\pmod{13} &&13\text{ prime},\ 13\nmid7\\ 1001&=83(12)+5 &&\text{one larger remainder}\\ 7^{1001}&\equiv7^5\pmod{13} &&\text{remove complete blocks}\\ 7^5&=7^4(7)\equiv9(7)=63\equiv11\pmod{13} &&\text{multiply by one extra }7 \end{aligned}

Why this step? A remainder of $5$ means retain $7^5$ , rather than replacing the whole power by the integer $5$ .

Answer. The least positive residue is $11$ .

Check. $9(7)=63=4(13)+11$ , so it is the next residue after $9$ in the repeated-multiplication cycle.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

FP2 5.4 - Fermat's little theorem

Check the prime modulus and the base

Remove complete blocks of the exponent

Continue this lesson.

Learn faster with Nova