FP2 5.6 - Solving congruence equations | Edexcel A-Level Further Mathematics

Decide whether a linear congruence has solutions, find multiplicative inverses using Bezout's identity, and solve with the correct modulus. Describe every solution, including the multiple residue classes that occur when the coefficient and modulus are not coprime.

Check the coefficient and modulus before trying to solve

Why does $42x\equiv30\pmod{66}$ have six solution residues modulo $66$ , while changing $30$ to $31$ leaves none? Multiplication can merge remainder classes, so a congruence equation need not behave like an ordinary equation with one answer. The common factor of the coefficient and modulus controls what is possible.

You already know

$a\equiv b\pmod n$ means $n\mid(a-b)$ . Euclid finds the positive highest common factor $\gcd(a,n)$ , and back substitution expresses it as an integer combination of $a,n$ . Cancelling a factor while keeping the modulus is safe only when that factor is coprime to the modulus. A residue class $x\equiv r\pmod n$ means all integers $r+kn$ , $k\in\mathbb Z$ .

In a linear congruence $ax\equiv b\pmod n$ , the unknown is an integer $x$ , the coefficient and right-hand side are integers, and the modulus here is an integer $n\ge2$ . Asking for solutions modulo $n$ means identifying which classes of integers satisfy the condition, usually using representatives $0,1,\ldots,n-1$ .

Existence of solutions

Let $d=\gcd(a,n)>0$ . Then

ax\equiv b\pmod n \quad\text{has an integer solution exactly when}\quad d\mid b

When solutions exist, there are exactly $d$ distinct solution classes modulo $n$ .

Not in the formula booklet: learn it.

Here is why the existence test works. The congruence is equivalent to $ax+ny=b$ for some integer $y$ . Since $d$ divides both $a,n$ , it must divide $b$ : this is necessary.

Conversely, suppose $b=dh$ . Bezout gives integers $u,v$ with $au+nv=d$ . Multiply this identity by $h$ :

a(uh)+n(vh)=dh=b

Thus $x=uh$ is a solution. The condition is sufficient too. We will justify the count of $d$ classes when reducing the modulus below.

For the opening equation, $d=\gcd(42,66)=6$ . This divides $30$ , so solutions exist, but does not divide $31$ , so the changed equation has none. Having no multiplicative inverse of $42$ modulo $66$ does not rule out every right-hand side.

Key idea

Find $\gcd(a,n)$ , using the coefficient and the modulus. Check whether it divides the right-hand side before attempting an inverse or searching for a residue.

Test the condition on a new equation.

Read a multiplicative inverse from an identity equal to one

To undo multiplication by $a$ while keeping modulus $n$ , seek an integer $u$ with $au\equiv1\pmod n$ . Then multiplying a congruence by $u$ turns its coefficient into $1$ .

Multiplicative inverse

An inverse of $a$ modulo $n\ge2$ exists exactly when $\gcd(a,n)=1$ . If Bezout's identity gives

au+nv=1

then

au\equiv1\pmod n

and $u$ is a multiplicative inverse of $a$ . Any integer congruent to $u$ is also an inverse.

Not in the formula booklet: learn it.

The identity proves sufficiency. For necessity, $au\equiv1\pmod n$ gives an integer combination of $a,n$ equal to $1$ , so their highest common factor is $1$ . This is why $1/a$ as an ordinary fraction is not a substitute for finding an integer inverse.

Worked example 1: a negative Bezout coefficient

Question. Use Bezout's identity to find a multiplicative inverse of $17$ modulo $43$ , giving the least nonnegative representative.

Plan. Use Euclid and back substitution to express $1$ in terms of $17,43$ , then reduce the coefficient of $17$ .

\begin{aligned} 43&=2(17)+9\\ 17&=9+8\\ 9&=8+1\\ 8&=8(1)+0 && \text{highest common factor is }1 \end{aligned}

\begin{aligned} 1&=9-8 && \text{last nonzero remainder}\\ &=9-(17-9)=2(9)-17 && \text{replace }8\\ &=2(43-2(17))-17 && \text{replace }9\\ &=2(43)-5(17) && \text{original inputs only} \end{aligned}

Why this step? The coefficient of $17$ , not the coefficient of the modulus, is the inverse. A negative coefficient is allowed.

Answer. An inverse is $-5\equiv38\pmod{43}$ , so the requested representative is $38$ .

Check. $17(38)=646=15(43)+1$ .

Keep modulus $43$ ; change only the coefficient from $17$ to $18$ .

Worked example 2: recalculate the inverse after changing the coefficient

Question. Find the least nonnegative inverse of $18$ modulo $43$ using Bezout's identity.

Plan. Recompute the remainder chain and substitute backwards; the inverse of $17$ cannot be reused.

\begin{aligned} 43&=2(18)+7\\ 18&=2(7)+4\\ 7&=4+3\\ 4&=3+1\\ 3&=3(1)+0 \end{aligned}

\begin{aligned} 1&=4-3=4-(7-4) && \text{replace }3\\ &=2(4)-7 && \text{collect terms}\\ &=2(18-2(7))-7 && \text{replace }4\\ &=2(18)-5(7)\\ &=2(18)-5(43-2(18)) && \text{replace }7\\ &=12(18)-5(43) \end{aligned}

Why this step? Reducing this identity modulo $43$ removes its $43$ -term and leaves $12(18)\equiv1$ .

Answer. The inverse is $12$ .

Check. $18(12)=216=5(43)+1$ .

The inverse is a residue class, so $-5$ and $38$ are equally valid during working in the first example. A requested least nonnegative answer must be in $0$ to $42$ .

Watch out

Wrong: take $2$ as the inverse of $17$ from $1=2(43)-5(17)$ . Right: take $-5$ , the coefficient multiplying $17$ , then reduce it if a representative is requested.

Change the coefficient by one again.

Multiply by the inverse and state the full residue class

When $\gcd(a,n)=1$ , an inverse $u$ gives

ax\equiv b\pmod n \quad\Longleftrightarrow\quad x\equiv ub\pmod n

The forward step multiplies by $u$ ; the reverse step multiplies by $a$ . Thus the method preserves all solutions, not just one candidate. This solving rule follows from the inverse and is not separately printed in the formula booklet.

There is one solution class modulo $n$ , containing infinitely many integers. A bare integer is only one representative unless the question asks for a single value in a specified range.

Worked example 3: use the inverse already found

Question. Solve $17x\equiv9\pmod{43}$ , giving all integer solutions.

Plan. Multiply both sides by the inverse $38$ , reduce the right-hand side, then write the full class.

\begin{aligned} 38(17x)&\equiv38(9)\pmod{43} && \text{multiply both sides}\\ x&\equiv342\equiv41\pmod{43} && 342=7(43)+41 \end{aligned}

Why this step? The modulus stays $43$ because multiplying by an inverse is reversible. No division by $17$ as an ordinary fraction is used.

Answer. $x\equiv41\pmod{43}$ , or $x=41+43k$ for $k\in\mathbb Z$ .

Check. $17(41)-9=688=16(43)$ . Increasing $x$ by $43$ changes $17x$ by a multiple of $43$ , so the whole class works.

Keep the coefficient and modulus fixed; change only the right-hand side from $9$ to $10$ .

Worked example 4: a changed right-hand side uses the same inverse

Question. Solve $17x\equiv10\pmod{43}$ .

Plan. Retain inverse $38$ and apply it to the new right-hand side.

\begin{aligned} x&\equiv38(10)=380\pmod{43} && \text{multiply by the inverse}\\ &\equiv36\pmod{43} && 380=8(43)+36 \end{aligned}

Why this step? The inverse depends on the coefficient and modulus, so changing only the right-hand side does not require a new Euclidean algorithm.

Answer. $x\equiv36\pmod{43}$ , equivalently $x=36+43k$ , $k\in\mathbb Z$ .

Check. $17(36)-10=602=14(43)$ .

The final statement must retain the modulus. It describes which repeated integer values work, rather than suggesting that $x$ equals just its smallest nonnegative representative.

Watch out

Wrong: finish “ $x=36$ ” when asked to solve over the integers. Right: state $x\equiv36\pmod{43}$ , or $x=36+43k$ with $k\in\mathbb Z$ .

Change only the right-hand side again.

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.6 - Solving congruence equations

Check the coefficient and modulus before trying to solve

Read a multiplicative inverse from an identity equal to one

Multiply by the inverse and state the full residue class

Continue this lesson.

Learn faster with Nova