TT4–TT7 - Theorems of Fermat, Euler and Wilson | OCR A-Level Further Mathematics B (MEI)

Calculate and search with congruences. Use Fermat's little theorem, Euler's totient and theorem, and Wilson's theorem with their exact conditions; distinguish a necessary primality condition from an exact test.

Keep the remainder, change the representative

A program finds $2^{340}\equiv1\pmod{341}$ . Does that make $341$ prime?

It is tempting to reverse a familiar theorem. This lesson will show why that conclusion fails, and which theorem really does give an if-and-only-if prime test.

You already know

The preceding lesson used integer division and remainders in Python. Primes exceed $1$ ; two integers are co-prime when their greatest common divisor, or HCF, is $1$ .

Congruence expresses the common remainder without requiring the original integers to be equal.

Congruent modulo a positive integer

For an integer modulus $n>1$ , $a\equiv b\pmod n$ means that $n$ divides $a-b$ : the integers have the same remainder on division by $n$ . The required final representative $m$ satisfies $0\le m<n$ .

For example, $-2\equiv7\pmod9$ . Both name the same residue, but $7$ is the canonical final answer. Use a congruence sign between equivalent representatives; $16$ is not literally equal to $2$ , although $16\equiv2\pmod7$ .

Calculating with congruences

If $a\equiv r\pmod n$ and $b\equiv s\pmod n$ , then

a+b\equiv r+s,\quad a-b\equiv r-s,\quad ab\equiv rs\pmod n.

Non-negative integer powers may also be reduced before or after powering. Arbitrary division or cancellation is not justified: cancel a factor modulo $n$ only when it is co-prime to $n$ .

Not in the formula booklet: learn it.

Reduce early to keep calculations small, then reduce the final result once more.

Worked example 1: a sum

Question. Find the canonical residue of $3(47)+26$ modulo $9$ .

Plan. Replace both large integers by their remainders.

\begin{aligned} 47&\equiv2,\quad26\equiv8\pmod9 && \text{reduce inputs}\\ 3(47)+26&\equiv3(2)+8=14\equiv5\pmod9 && \text{calculate and reduce} \end{aligned}

Why this step? Congruence preserves addition and multiplication, so smaller representatives give the same final residue.

Answer. $5$ .

Check. $3(47)+26=167=18(9)+5$ .

Change only the addition sign to subtraction. The intermediate remainder becomes negative.

Worked example 2: a negative intermediate value

Question. Find $3(47)-26$ modulo $9$ .

Plan. Use the same representatives, then bring the answer into the required range.

\begin{aligned} 3(47)-26&\equiv3(2)-8=-2\pmod9 && \text{reduce inputs}\\ -2&\equiv-2+9=7\pmod9 && \text{canonical representative} \end{aligned}

Why this step? A negative representative is useful during working, but the final answer must lie between $0$ and $8$ .

Answer. $7$ .

Check. $115=12(9)+7$ .

Cancellation has a real boundary: $2x\equiv2\pmod6$ has residues $x=1,4$ . Cancelling $2$ while retaining modulus $6$ would lose a solution; here $\gcd(2,6)=2\ne1$ .

Watch out

Wrong final answer modulo $9$ : $-2$ . Right: $7$ . Equivalent representatives are allowed in working; final answers use $0\le m<n$ .

Reduce a new subtraction.

Search one complete set of residues

To solve a congruence modulo $n$ , it is enough to check $x=0,1,\ldots,n-1$ . Every other integer is congruent to exactly one of these representatives.

The program below returns every solution to $x^2\equiv-1\pmod n$ , for integer $n>1$ . The list starts empty; append retains a successful candidate, and the function returns the complete list after the loop.

Python

def roots_minus_one(n):
    answers = []
    for x in range(n):
        if (x * x) % n == n - 1:
            answers.append(x)
    return answers

Using $n-1$ for $-1$ matches Python's non-negative remainder for a positive modulus.

Worked example 3: two roots in one residue range

Question. Solve $x^2\equiv-1\pmod{13}$ , giving all canonical residues.

Plan. Search the complete residue range; use symmetry only to shorten the displayed checking.

\begin{array}{c|rrrrrrr} x&0&1&2&3&4&5&6\\ \hline x^2\bmod13&0&1&4&9&3&12&10 \end{array}

For $x=7,\ldots,12$ , the squares repeat those for $6,\ldots,1$ , because $13-x\equiv-x\pmod{13}$ . The successful values are $5$ and $13-5=8$ .

Why this step? The entire residue range must be covered; finding one root does not finish an all-solutions question.

Answer. $x\equiv5,8\pmod{13}$ .

Check. $25=2(13)-1$ and $64=5(13)-1$ .

Change only the modulus from $13$ to $17$ . The target representative changes with it.

Worked example 4: another modulus

Question. Solve $x^2\equiv-1\pmod{17}$ .

Plan. Check representatives through $8$ and their negatives.

\begin{array}{c|rrrrrrrrr} x&0&1&2&3&4&5&6&7&8\\ \hline x^2\bmod17&0&1&4&9&16&8&2&15&13 \end{array}

The value $16$ occurs at $4$ , and by symmetry at $17-4=13$ .

Why this step? The condition is now a remainder of $16$ , not the previous modulus's target $12$ .

Answer. $x\equiv4,13\pmod{17}$ .

Check. $4^2=16$ and $13^2=169=10(17)-1$ .

Predict, run, then change the modulus from $13$ to $17$ . Both runs should agree with the complete searches.

Search a complete residue range

{"code":"def roots_minus_one(n):\n answers = []\n for x in range(n):\n if (x * x) % n == n - 1:\n answers.append(x)\n return answers\n\nprint(roots_minus_one(13))","instructions":"Predict and run. Replace 13 by 17 in the call, predict the new list and run again. Explain why range(n) includes every canonical candidate exactly once."}

A complete modular search settles every residue class, even though it tests only finitely many representatives.

Watch out

Wrong: stop at the first successful root when asked for all roots. Right: retain every success and finish the complete residue range.

Adapt the target as well as the modulus.

A prime modulus shortens an exponent

Fermat's little theorem replaces a large exponent by blocks of $p-1$ , provided the modulus is prime and the base is co-prime to it.

Fermat's little theorem

If $p$ is prime and $\gcd(a,p)=1$ , then

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

Thus if $k=q(p-1)+r$ , with $k\ge0$ and $0\le r<p-1$ , then $a^k\equiv a^r\pmod p$ . The related form $a^p\equiv a\pmod p$ holds for every integer $a$ .

Not in the formula booklet: learn it.

State the conditions before reducing the exponent. A divisible base behaves differently: $11^{10}\equiv0\pmod{11}$ , not $1$ .

Worked example 5: many complete blocks

Question. Find $7^{202}$ modulo $11$ .

Plan. Check the conditions and split $202$ into blocks of $10$ .

\begin{aligned} 11&\text{ is prime},\quad\gcd(7,11)=1 && \text{conditions}\\ 7^{10}&\equiv1\pmod{11} && \text{Fermat}\\ 202&=20(10)+2 && \text{split exponent}\\ 7^{202}&\equiv(7^{10})^{20}7^2\equiv49\equiv5\pmod{11} \end{aligned}

Why this step? The blocks have length $p-1=10$ , not $p=11$ .

Answer. $5$ .

Check. The remaining calculation is $7^2=4(11)+5$ .

Increase only the exponent by $1$ , so one additional factor $7$ remains.

Worked example 6: one more factor

Question. Find $7^{203}$ modulo $11$ .

Plan. Use the same conditions and a new exponent remainder.

\begin{aligned} 203&=20(10)+3 && \text{new decomposition}\\ 7^{203}&\equiv(7^{10})^{20}7^3 && \text{Fermat applies}\\ &\equiv7(5)=35\equiv2\pmod{11} && 7^2\equiv5 \end{aligned}

Why this step? Increasing the exponent by one multiplies the previous residue by the base, then requires another reduction.

Answer. $2$ .

Check. $7^3=343=31(11)+2$ .

The hook contains a surprising trap: $341=11\times31$ is composite, yet $2^{10}=1024\equiv1\pmod{341}$ , so $2^{340}=(2^{10})^{34}\equiv1$ . Passing this single Fermat-style test does not prove primality.

Watch out

Wrong: reverse Fermat's theorem to claim that a successful power test proves a number prime. Right: prime and co-prime are hypotheses; the converse need not hold.

Apply the theorem at a new prime modulus.

Count the co-prime residues

Euler's totient counts which residues can play the role needed in a more general exponent theorem.

Euler's totient

For $n>1$ , $\varphi(n)$ is the number of positive integers less than $n$ that are co-prime to $n$ . The conventional extension is $\varphi(1)=1$ .

Counting $1\le k\le n$ gives the same result when $n>1$ , because $\gcd(n,n)=n$ . It also implements that conventional value at $1$ .

Totient from prime factors

If the distinct prime factors of $n>1$ are $p_1,\ldots,p_r$ , then

\varphi(n)=n\prod_{i=1}^r\left(1-\frac1{p_i}\right).

In particular, $\varphi(p^a)=p^a-p^{a-1}$ for prime $p$ and integer $a\ge1$ . Each distinct prime contributes one factor, regardless of its exponent.

Not in the formula booklet: learn it.

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

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

TT4–TT7 - Theorems of Fermat, Euler and Wilson

Keep the remainder, change the representative

Search one complete set of residues

A prime modulus shortens an exponent

Count the co-prime residues

Continue this lesson.

Learn faster with Nova