8.02l–8.02o - Fermat's little theorem and orders | OCR A-Level Further Mathematics A

Use both forms of Fermat's little theorem to reduce powers and prove divisibility, while keeping track of what the theorem does and does not establish. Find the order of a number modulo a prime, and use the binomial theorem to explain a powerful prime-modulus identity.

Fermat's theorem for coprime bases

Suppose $2^{340}$ leaves remainder one on division by $341$ . Does that prove $341$ is prime? Fermat's little theorem makes the test tempting; understanding its direction will save you from the trap.

Start with a genuine prime. Modulo seven, $2^3=8\equiv1$ , so $2^6\equiv1$ . Fermat's theorem guarantees a power giving one for every base coprime to a prime modulus, though the guaranteed exponent may not be the smallest.

You already know

You can reduce products and non-negative integer powers modulo a fixed integer. If a number is coprime to the modulus, it has a multiplicative inverse; Euclid's lemma permits cancellation from divisibility under the same coprimality condition.

The theorem's first form provides an exponent you can use immediately.

Fermat's little theorem: coprime form

If $p$ is prime and $\operatorname{hcf}(a,p)=1$ , then

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

Not in the formula booklet: learn it.

Use the theorem as a result: its proof is not needed here. If $N=q(p-1)+r$ , with $0\le r<p-1$ , then $a^N=(a^{p-1})^q a^r\equiv a^r\pmod p$ . Thus reduce the exponent modulo $p-1$ , after checking the two conditions.

Worked example 1: reducing an exponent

Question. Find the least non-negative residue of $7^{100}$ modulo thirteen.

Plan. Use Fermat's theorem to remove multiples of twelve from the exponent, then calculate the remaining small power.

\begin{aligned} 7^{12}&\equiv1\pmod{13} &&13\text{ prime},\ \operatorname{hcf}(7,13)=1\\ 100&=12\times8+4 &&\text{divide the exponent}\\ 7^{100}&\equiv7^4\pmod{13} &&\text{remove eight blocks}\\ 7^2&\equiv49\equiv10\pmod{13} &&\text{square and reduce}\\ 7^4&\equiv10^2=100\equiv9\pmod{13} &&\text{square again} \end{aligned}

Why this step? Thirteen is the modulus for residues, but twelve is the period supplied for the exponent. They have different jobs.

Answer. The residue is $9$ .

Check. $7^6\equiv7^4\,7^2\equiv9\times10\equiv12\equiv-1\pmod{13}$ , so $7^{12}\equiv1$ , consistent with the theorem.

The next example changes only the exponent by one. Keep the small remainder power and one extra factor of seven.

Worked example 2: one extra factor

Question. Find the least non-negative residue of $7^{101}$ modulo thirteen.

Plan. Reduce the exponent modulo twelve and use the power already found.

\begin{aligned} 101&=12\times8+5 &&\text{exponent remainder five}\\ 7^{101}&\equiv7^5\pmod{13} &&\text{Fermat's theorem, same conditions}\\ &\equiv7\times9=63\equiv11\pmod{13} &&7^4\equiv9 \end{aligned}

Why this step? Increasing an exponent by one multiplies the residue by the base; it does not increase the residue by one.

Answer. The residue is $11$ .

Check. Multiplying the previous answer by seven gives $9\times7=63=13\times4+11$ .

The prime and coprimality conditions are part of a valid application.

Watch out

Wrong: $13^{12}\equiv1\pmod{13}$ by Fermat's theorem. The base and modulus are not coprime. Right: $13^{12}\equiv0\pmod{13}$ , because the power is a multiple of thirteen.

The same reduction works for a still larger exponent without calculating the full power.

Fermat's theorem for every integer

The second form includes bases divisible by the prime, so it is especially useful in statements about every integer.

Fermat's little theorem: unrestricted-base form

If $p$ is prime, then for every integer $a$ ,

a^p\equiv a\pmod p

Equivalently, $p\mid(a^p-a)$ .
Not in the formula booklet: learn it.

If $p\nmid a$ , multiplying the first form by $a$ gives this form. If $p\mid a$ , both $a^p$ and $a$ are divisible by $p$ , so it still holds. Conversely, for a base coprime to $p$ , you can cancel $a$ using its inverse to recover the first form. This explains how the forms fit together, without proving the theorem itself.

For example, $11^{11}\equiv11\equiv0\pmod{11}$ , so the second form handles precisely the boundary that prevented the first form from giving one.

Worked example 3: a divisibility statement for all integers

Question. Prove that $11\mid(n^{11}+10n)$ for every integer $n$ .

Plan. Isolate the difference $n^{11}-n$ supplied by Fermat's theorem.

\begin{aligned} n^{11}+10n&=(n^{11}-n)+11n &&\text{isolate the theorem's expression}\\ n^{11}-n&\equiv0\pmod{11} &&11\text{ is prime}\\ 11n&\equiv0\pmod{11} &&n\text{ is an integer} \end{aligned}

Why this step? The unrestricted-base form applies even when $n$ itself is divisible by eleven, so no exceptional case is left out.

Answer. The sum is congruent to zero modulo eleven for every integer $n$ ; therefore $11\mid(n^{11}+10n)$ .

Check. At $n=0$ the expression is zero; at $n=1$ it is eleven. Both satisfy the conclusion.

The next example changes only the constant term. The same theorem now proves that divisibility is impossible.

Worked example 4: a constant changes the conclusion

Question. Determine whether $n^{11}+10n+1$ can be divisible by eleven for any integer $n$ .

Plan. Reduce the first two terms using the previous argument, then retain the added constant.

\begin{aligned} n^{11}+10n+1 &\equiv n+10n+1\pmod{11} &&n^{11}\equiv n\\ &\equiv11n+1\equiv1\pmod{11} &&\text{collect terms} \end{aligned}

Why this step? A theorem about a difference does not make an extra constant disappear; its residue decides the new question.

Answer. It is never divisible by eleven: its least non-negative residue is always one.

Check. At $n=1$ , the value is twelve, with remainder one.

For a universal statement, write the theorem in a form that covers every permitted base.

Watch out

Wrong: using $n^{10}\equiv1\pmod{11}$ for every integer $n$ . It fails when $11\mid n$ . Right: $n^{11}\equiv n\pmod{11}$ holds for every integer.

Change the prime and keep the added constant visible.

Why a passed test does not prove primality

Fermat's theorem gives a necessary property of primes, so failing the property can rule out primality; passing it need not establish primality.

For example, $15$ is coprime to two, but

2^{14}=(2^4)^3\,2^2\equiv1^3\times4=4\not\equiv1\pmod{15}

If fifteen were prime, the first form of Fermat's theorem would give one, so this failure proves it composite.

Now examine the opening number:

\begin{aligned} 341&=11\times31 &&\text{composite}\\ 2^{10}&=1024=3\times341+1 &&\text{remainder one}\\ 2^{340}&=(2^{10})^{34}\equiv1\pmod{341} &&\text{passes the power test} \end{aligned}

The arithmetic test passes, but the number is still composite.

Pseudoprime to a base

A composite positive integer $N$ is a pseudoprime to base $a$ if $\operatorname{hcf}(a,N)=1$ and $a^{N-1}\equiv1\pmod N$ . Thus $341$ is a pseudoprime to base two. Fifteen is not a pseudoprime to base two.

The base is part of the description: passing for one base gives no claim about every other base. The implication and its failed converse are not in the formula booklet: learn the distinction.

Key idea

Prime modulus implies Fermat's congruence; Fermat's congruence alone does not imply prime modulus.

A factorisation settles compositeness even when a modular test happens to pass.

Continue this lesson.

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

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

8.02l–8.02o - Fermat's little theorem and orders

Fermat's theorem for coprime bases

Fermat's theorem for every integer

Why a passed test does not prove primality

Continue this lesson.

Learn faster with Nova