Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn9FM0Option · Further Pure Mathematics 2Number theoryDivisibility and modular arithmetic

Number theory · Subtopic 1 of 1

Number Theory

Euclid's algorithm finds $\gcd(a,b)$ by repeated division, and running it backwards writes the gcd as $ax+by$ (Bézout). In modular arithmetic we work with remainders: $a\equiv b\pmod n$ means $n\mid a-b$ . Fermat: for prime $p\nmid a$ , $a^{p-1}\equiv1\pmod p$ .

Edexcel 9FM0 Option≈ 45 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam Tutor

Section 1 of 14

Learning objectives

Use the Euclidean algorithm and Bézout's identity.
Calculate with congruences and solve linear congruences.
Use Fermat's little theorem for large powers.
Explain divisibility tests.

Pause and think

It's 9 o'clock. What time will it be in 100 hours?

Section 2 of 14

Core idea

Start hereClock arithmetic

If it's 9 o'clock now, what time is it in 100 hours? You don't need to count: only the remainder after dividing by 24 matters. Arithmetic with remainders turns huge calculations into small ones, and it secures every online payment.

The big idea

Euclid's algorithm finds $\gcd(a,b)$ by repeated division; reversing it writes $\gcd(a,b)=ax+by$ . Congruences mod $n$ let us add and multiply remainders, and Fermat's little theorem cuts large powers down to size.

1. Euclid's algorithm and Bézout

Why

\gcd(a,b)=\gcd(b,r)

$a=qb+r$
Division algorithm, $0\le r<b$ .
$d\mid a,\ d\mid b\Rightarrow d\mid a-qb=r$
A common divisor of $a,b$ divides $r$ .
$d\mid b,\ d\mid r\Rightarrow d\mid qb+r=a$
And conversely.

Same common divisors, so same gcd. Repeat until the remainder is

0

Worked example $\gcd(252,198)$ and Bézout

Find $\gcd(252,198)$ and integers $x,y$ with $252x+198y=\gcd$ .

Goal: gcd and $x,y$ .
Strategy: Divide down, then substitute back up.

$252=1\cdot198+54$
First division.
$198=3\cdot54+36,\quad54=1\cdot36+18,\quad36=2\cdot18$
Continue until remainder $0$ .
$18=54-36$
Start from the last non-zero remainder.
$=54-(198-3\cdot54)=4\cdot54-198$
Replace $36$ .
$=4(252-198)-198=4\cdot252-5\cdot198$
Replace $54$ .

Answer

\gcd=18=252(4)+198(-5)

✓ Check

1008-990=18

✓.

2. Congruences and Fermat

a\equiv b\pmod n\iff n\mid a-b

$n$: the modulus.

Worked exampleSolving a linear congruence

Solve $3x\equiv4\pmod7$ .

Goal: $x$ mod 7.
Strategy: Multiply by the inverse of 3.

$3\times5=15\equiv1$
So $3^{-1}\equiv5\pmod7$ .
$x\equiv5\times4=20\equiv6$
Multiply both sides by $5$ .

Answer

x\equiv6\pmod7

✓ Check

3\times6=18\equiv4

✓.

Fermat's little theorem (idea)

$\{a,2a,\ldots,(p-1)a\}\equiv\{1,2,\ldots,p-1\}$
Multiplying by $a$ just reorders the non-zero remainders ( $p$ prime, $p\nmid a$ ).
$a^{p-1}(p-1)!\equiv(p-1)!$
Multiply all elements of each set.
$a^{p-1}\equiv1\pmod p$
$(p-1)!$ is coprime to $p$ , so cancel.

Worked example $2^{100}\bmod7$

Find the remainder when $2^{100}$ is divided by $7$ .

Goal: A remainder.
Strategy: Find a small power $\equiv1$ .

$2^3=8\equiv1$
Even quicker than Fermat's $2^6$ .
$2^{100}=(2^3)^{33}\cdot2$
$100=3\times33+1$ .
$\equiv1^{33}\cdot2=2$
Replace $2^3$ by $1$ .

Answer

2

✓ CheckPowers cycle

2,4,1

; position

100\equiv1\pmod3

gives

2

✓.

Divisibility tests come from congruences

Drawing diagram…

Each test is just a congruence for 10.

Common misconceptionNo dividing From

6x\equiv6\pmod9

you can't cancel 6 to get

x\equiv1

x=4

and

x=7

also work, because

\gcd(6,9)=3

TrickDivisible by 11

10\equiv-1\pmod{11}

, so take alternate digit sums:

918082\to2-8+0-8+1-9=-22

, divisible by 11.

Pause and think

Find $5^{12}\bmod13$ without a calculator.

Summary

$\gcd(a,b)=\gcd(b,r)$ .
Back-substitute for Bézout.
Solve congruences with inverses.
Fermat: $a^{p-1}\equiv1\pmod p$ .

Congruent: Same remainder on division by n.
Coprime: gcd equal to 1.
Modular inverse: $b$ with $ab\equiv1\pmod n$ .

HistoryEuclid and Fermat. Euclid's algorithm (c. 300 BC) is one of the oldest algorithms still in daily use. Fermat stated his "little theorem" in a 1640 letter, without proof.

Fun factRSA. Every secure website uses modular powers: RSA encryption relies on Fermat's (and Euler's) theorem.

Section 3 of 14

Key formulae

Division algorithm

a=qb+r,\ 0\le r<b;\quad\gcd(a,b)=\gcd(b,r)

Bézout

\gcd(a,b)=ax+by\ \text{for some integers }x,y

Fermat's little theorem

p\text{ prime},\ p\nmid a\ \Rightarrow\ a^{p-1}\equiv1\pmod p

TrickDivisibility by 9.

10\equiv1\pmod9

, so every power of 10 is

\equiv1

: a number is congruent to its digit sum mod 9 (and mod 3).

Section 4 of 14

Worked examples

Example 1 · Euclid and Bézout0 / 3 steps

Find

\gcd(252,198)

and integers with

252x+198y=\gcd

Example 2 · A congruence0 / 2 steps

Solve

3x\equiv4\pmod7

Section 5 of 14

Explore the graph

Powers of 2 mod 7 repeat

Loading the interactive graph…

Try this

The remainders cycle $1,2,4,1,2,4,\ldots$ with period $3$ .
Fermat guarantees the period divides $7-1=6$ .

$2^3\equiv1\pmod7$ .

In the real worldISBN check digits. Book numbers end in a check digit chosen so a weighted sum is divisible by 11 (or 10): a single mistyped digit always breaks the congruence.

Section 6 of 14

Common mistakes

IncorrectDividing in congruences

CorrectMultiply by an inverse

Division only works when the divisor is coprime to the modulus.

IncorrectFermat for composite

n

Correct

n

must be prime

2^{8}\not\equiv1\pmod9

IncorrectLosing track in back-substitution

CorrectKeep

a

and

b

as symbols

Collect multiples of the original numbers at each step.

2¹⁰⁰ mod 7 by calculator

Fermat: 2³ ≡ 1, so it's 2. Next question.

Section 7 of 14

Exam tip

Exam tipLayout for Euclid. Write each line as

a=qb+r

in a column; back-substitution is far easier when the lines are aligned.

Section 8 of 14

Guided practice

SA-FP-NT-G011 markL1 FoundationNon-calculatorCongruences

Find

47\bmod5

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-FP-NT-0012 marksL2 StandardNon-calculatorEuclid

Use the Euclidean algorithm to find

\gcd(252,198)

Salam Academy Original Practice · Proposed mark scheme

SA-FP-NT-0022 marksL2 StandardNon-calculatorCongruences

Solve

3x\equiv4\pmod7

, giving

0\le x<7

Salam Academy Original Practice · Proposed mark scheme

SA-FP-NT-0033 marksL3 ExamNon-calculatorFermat

Find

2^{100}\bmod7

Salam Academy Original Practice · Proposed mark scheme

SA-FP-NT-0041 markL1 FoundationNon-calculatorFermat

Find

4872\bmod9

using the digit sum.

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-FP-NT-0054 marksL4 ChallengingNon-calculatorEuclid

Find the smallest positive integer

x

for which there is an integer

y

with

252x+198y=18

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Euclid: repeated division.
Bézout: back-substitute.
Congruences: multiply by inverses.
Fermat reduces powers.

Section 12 of 14

Quick quiz

Q1 · SA-FP-NT-Q011 markL1 FoundationNon-calculatorCongruences

a\equiv b\pmod n

means

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: A level Further Mathematics 9FM0
Where: Further Pure 2 · Number theory
Expected: Division algorithm, Euclid's algorithm, Bézout's identity, modular arithmetic, linear congruences, Fermat's little theorem, divisibility tests; combinatorics including derangements.
Calculator: Permitted; show enough working to earn the method marks.
Typical style: Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
Open in: 9FM0 · Option

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel 9FM0, First teaching 2017 (official specification).