8.02e–8.02h - Modular arithmetic and congruences | OCR A-Level Further Mathematics A

Calculate with remainders, solve linear congruences, and use quadratic residues to settle equations without searching through every integer. You will combine up to three congruences, including systems whose moduli share a factor, and express every solution rather than one successful example.

Arithmetic with remainders

An integer leaves remainder $3$ on division by $5$ and remainder $2$ on division by $7$ . What is the smallest positive integer it could be, and how can you describe every possibility? There are infinitely many candidates, but only a few remainders to organise.

First, consider a simpler calculation. Both $17$ and $5$ leave remainder $5$ on division by $12$ . For a question about twelves, replacing $17$ by $5$ loses nothing useful.

You already know

Division writes a positive integer as $a=nq+r$ , where $0\le r<n$ . The remainder is unique, and a remainder of zero means exact divisibility.

The notation records that two integers differ by a multiple of the modulus.

Congruence

For integers $a,b$ and a modulus $n\ge2$ ,

a\equiv b\pmod n

means $n\mid(a-b)$ . Equivalently, $a$ and $b$ have the same remainder on division by $n$ . The least non-negative residue is the unique representative in $0,1,\ldots,n-1$ . For example, $17\equiv5\pmod{12}$ and $-7\equiv5\pmod{12}$ , but $17\ne5$ .

Negative representatives can make arithmetic shorter. For example, $99\equiv-1\pmod{10}$ , so $99^2\equiv1\pmod{10}$ : you know the last digit without squaring ninety-nine.

[DIAGRAM: asset_name: Congruence classes modulo five; asset_slug: h245_8_02_residue_classes; caption: Every integer belongs to one of five remainder classes; description: Five horizontal rows labelled zero through four contain the integers from minus ten to fourteen arranged by common remainder modulo five. The row with remainder three contains minus seven, minus two, three, eight and thirteen and is highlighted blue. Arrows join successive integers in that row, each separated by five.]
Every integer belongs to one of five remainder classes

Adding or multiplying congruent integers preserves congruence. If $a-b=nu$ and $c-d=nv$ , then $(a+c)-(b+d)=n(u+v)$ and $ac-bd=a(c-d)+d(a-b)$ are multiples of $n$ .

Arithmetic modulo a fixed integer

For a common modulus $n\ge2$ , if $a\equiv b\pmod n$ and $c\equiv d\pmod n$ , then

a\pm c\equiv b\pm d\pmod n,\qquad ac\equiv bd\pmod n

In particular, $a^k\equiv b^k\pmod n$ for every non-negative integer $k$ .
Not in the formula booklet: learn it.

Reduce after each multiplication to avoid carrying large numbers.

Worked example 1: reducing a large power

Question. Find the least non-negative residue of $8^{25}+8$ modulo seven.

Plan. Replace eight by its remainder one before taking the power.

\begin{aligned} 8&\equiv1\pmod7 &&8-1=7\\ 8^{25}+8&\equiv1^{25}+1\pmod7 &&\text{powers and addition}\\ &\equiv2\pmod7 &&\text{least non-negative residue} \end{aligned}

Why this step? Taking a power of the small representative gives the same remainder as taking a power of the original number.

Answer. The residue is $2$ .

Check. The units modulo seven cycle immediately: every positive power of a number congruent to one is also congruent to one.

The next example changes the representative from one to minus one. The parity of the exponent now matters.

Worked example 2: using a negative representative

Question. Find the least non-negative residue of $6^{25}+6$ modulo seven.

Plan. Replace six by minus one and use the odd exponent.

\begin{aligned} 6&\equiv-1\pmod7 &&6-(-1)=7\\ 6^{25}+6&\equiv(-1)^{25}-1\pmod7 &&\text{substitute representatives}\\ &\equiv-2\equiv5\pmod7 &&\text{add seven} \end{aligned}

Why this step? Minus two is a convenient intermediate representative, but the requested least non-negative residue is five.

Answer. The residue is $5$ .

Check. $6^{25}\equiv6\pmod7$ , and $6+6=12\equiv5\pmod7$ .

Keep equality for identical integers and congruence for identical remainders.

Watch out

Wrong: $6=-1$ . Right: $6\equiv-1\pmod7$ . Also, the modulus stays fixed through a chain of modular calculations; a statement modulo seven cannot simply be added to one modulo five.

Use the same shortcut with a different modulus.

Linear congruences and inverses

Solving $ax\equiv b\pmod n$ means finding every integer $x$ for which $ax-b$ is a multiple of $n$ .

For $3x\equiv2\pmod7$ , adding sevens to the right side gives $2,9,16,23,\ldots$ . The value nine is divisible by three, giving $x=3$ . All numbers congruent to three modulo seven also work.

An inverse provides a quicker version of this search.

Multiplicative inverse modulo n

An integer $u$ is an inverse of $a$ modulo $n$ if $au\equiv1\pmod n$ . Such an inverse exists exactly when $\operatorname{hcf}(a,n)=1$ . For example, $3\times5=15\equiv1\pmod7$ , so five is an inverse of three modulo seven. Two has no inverse modulo six, since every multiple of two is even.

Multiplying $ax\equiv b\pmod n$ by an inverse $u$ gives $x\equiv ub\pmod n$ . This inverse method and its coprimality condition are not in the formula booklet: learn them. Find an inverse by trying multiples, or by finding an integer combination $au+nv=1$ .

The inverse condition is also the condition for cancelling the same factor while keeping the modulus unchanged. Cancellation with a non-coprime factor belongs to the next part.

Worked example 3: multiplying by an inverse

Question. Determine the solution of $4x\equiv3\pmod{11}$ .

Plan. Find an inverse of four modulo eleven, multiply both sides by it, and reduce.

\begin{aligned} 4\times3&=12\equiv1\pmod{11} &&\text{inverse is }3\\ x&\equiv3\times3=9\pmod{11} &&\text{multiply by the inverse} \end{aligned}

Why this step? Multiplying by an inverse turns the coefficient of $x$ into one without changing the modulus.

Answer. $x\equiv9\pmod{11}$ , or $x=11k+9$ for $k\in\mathbb Z$ .

Check. $4(11k+9)-3=44k+33=11(4k+3)$ .

The next example changes only the right side. The same inverse can be reused.

Worked example 4: the same inverse with a new right side

Question. Determine the solution of $4x\equiv7\pmod{11}$ .

Plan. Multiply by three, the inverse of four, and reduce the resulting residue.

\begin{aligned} 3(4x)&\equiv3\times7\pmod{11} &&\text{multiply both sides}\\ x&\equiv21\equiv10\pmod{11} &&12\equiv1\pmod{11} \end{aligned}

Why this step? An inverse depends on the coefficient and modulus, not on the right side of the equation.

Answer. $x=11k+10$ , where $k\in\mathbb Z$ .

Check. $4(11k+10)-7=44k+33$ , a multiple of eleven.

A congruence describes a whole class, even when you write one small representative.

Watch out

Wrong: “The only solution is $x=10$ .” Right: $x\equiv10\pmod{11}$ , meaning every integer $11k+10$ . If the question asks for a representative in a stated range, give that representative as well.

Show how you obtain the residue in an OCR “Determine” question: an unexplained calculator answer does not display the required reasoning.

When a coefficient is not invertible

A non-coprime coefficient can produce several residue classes or no solutions at all.

For example, $2x\equiv2\pmod6$ means $2x-2=6k$ , so $x-1=3k$ . Thus $x\equiv1\pmod3$ , which represents the two classes $x\equiv1,4\pmod6$ . Dividing the equation has divided the modulus as well.

Reducing a linear congruence

Let $d=\operatorname{hcf}(a,n)$ . The congruence $ax\equiv b\pmod n$ has solutions if and only if $d\mid b$ . When $d\mid b$ and $n/d\ge2$ , it is equivalent to

\frac ad x\equiv\frac bd\pmod{n/d}

The reduced coefficient and modulus are coprime. There is one class modulo $n/d$ , giving $d$ classes modulo the original modulus $n$ . If $n/d=1$ and $d\mid b$ , every integer $x$ is a solution.
Not in the formula booklet: learn it.

To see the obstruction, write $ax-b=nk$ . Every term except possibly $b$ is divisible by $d$ , so $b$ must be too. If it is, division by $d$ gives the reduced congruence, where an inverse exists unless the condition has become automatic. For example, $5x\equiv0\pmod5$ holds for every integer $x$ ; $5x\equiv2\pmod5$ has no solutions.

This is a decision to make before searching for an inverse.

Worked example 5: several classes in the original modulus

Question. Determine all solutions of $6x\equiv9\pmod{15}$ , giving the residue classes modulo fifteen.

Plan. Divide the coefficient, right side and modulus by their common factor, then solve the reduced congruence.

\begin{aligned} \operatorname{hcf}(6,15)&=3,\qquad3\mid9 &&\text{solutions are possible}\\ 2x&\equiv3\pmod5 &&\text{divide all three by }3\\ x&\equiv9\equiv4\pmod5 &&2^{-1}\equiv3\pmod5 \end{aligned}

Why this step? The reduced modulus is five, so increasing $x$ by five gives another solution before reaching the original modulus fifteen.

Answer. $x=5k+4$ , where $k\in\mathbb Z$ . Modulo fifteen the classes are $x\equiv4,9,14\pmod{15}$ .

Check. $6\times4,6\times9,6\times14$ leave remainders $9,9,9$ , respectively, on division by fifteen.

The next example changes only the right side. The common factor now rules out every candidate.

Worked example 6: proving that no solution exists

Question. Determine all solutions of $6x\equiv8\pmod{15}$ .

Plan. Test whether the highest common factor of the coefficient and modulus divides the right side.

\begin{aligned} 6x&=8+15k &&\text{integer form of the congruence}\\ 3(2x-5k)&=8 &&\text{rearrange} \end{aligned}

The left side is divisible by three, but the right side is not.

Why this step? Checking a common factor rules out infinitely many integers at once; a long unsuccessful search would not prove insolubility.

Answer. There are no integer solutions.

Check. The possible residues of $6x$ modulo fifteen are $0,3,6,9,12$ , none of which is eight.

The right side decides whether a non-invertible coefficient is an obstruction or a route to a smaller modulus.

Watch out

Wrong: $6x\equiv9\pmod{15}\Rightarrow2x\equiv3\pmod{15}$ . Right: the new modulus is five. Keeping fifteen would discard valid solutions.

Apply the same common-factor test before attempting any cancellation.

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.02e–8.02h - Modular arithmetic and congruences

Arithmetic with remainders

Linear congruences and inverses

When a coefficient is not invertible

Continue this lesson.

Learn faster with Nova