Skip to main content

Section 9.2 Solving linear equations modulo \(m\)

When can we solve \(ax = b\mod m\) for \(x\text{?}\) Before we even start, it's good to have a test to see if there is actually a solution:

An integer \(x\) is a solution to \(ax = b\mod m\) if and only if \(ax=b-my\) for some integer \(y\text{.}\) In other words, \(ax = b\mod m\) has a solution if and only if \(b\) can be written as \(ax + my\) for some integers \(x\) and \(y\text{.}\)

If \(b = ax+my\text{,}\) then the Linear Combination Lemma ensures that \(\gcd(a,m)\) divides \(b\text{.}\)

Conversely, assume that \(\gcd(a,m)\) divides \(b\text{,}\) so that \(b = h\gcd(a,m)\) for some integer \(h\text{.}\) Bezout's identity implies that there exist integers \(x'\) and \(y'\) such that \(\gcd(a,m)=ax'+my'\text{.}\) Hence if \(x = hx'\) and \(y=hy'\text{,}\) then

\begin{equation*} b = h\gcd(a,m) = ax + my\text{,} \end{equation*}

as desired.

Find \(x\in \{0,1,...,13\}\) so that \(18x = 10\mod 14\text{.}\)

We see that \(\gcd(18,14)=2\) divides \(10\text{,}\) so there is at least one solution. We can use the Euclidean Algorithm to express \(2\) as an integer linear combination: since \(18 - 14 = 4\text{,}\) and \(14 - 3\cdot 4 = 2\) is the gcd, so we can write

\begin{equation*} 2 = 14 - 3\cdot 4 = 4\cdot 14 - 3 \cdot 18\text{.} \end{equation*}

Multiplying this by \(5\text{,}\) we obtain

\begin{equation*} 10 = 20\cdot 14 - 15 \cdot 18\text{.} \end{equation*}

So \(-15\) is a solution, and so is \(3 = -15 \mod 18\text{.}\)

Note that when finding a solution to \(a = bx\mod m\text{,}\) any integer \(x\) is congruent modulo \(m\) to a number in \(\{0,1,...,m-1\}\text{.}\) Thus, whenever we ask for a solution, we prefer to write it as one of these integers.

Find \(x\) so that \(7x = 8\mod 12\text{.}\)

Solution.

Since \(\gcd(7,12)=1\text{,}\) we can use the Euclidean Algorithm:

\begin{equation*} 12-7 = 5 \ \ \text{ and } 7-5 = 2 \ \ \text{ and } 5-2\cdot 2 = 1\text{.} \end{equation*}

We find

\begin{equation*} 1 = 5 - 2\cdot 2 = 3\cdot 5 - 2\cdot 7 = 3\cdot 12 - 5\cdot 7\text{,} \end{equation*}

so by multiplying by \(8\text{,}\) we get

\begin{equation*} 8 = 24 \cdot 12 - 40 \cdot 7\text{.} \end{equation*}

Thus \(x = -40\) is a solution, and so is \(8 = -40 \mod 12\text{.}\)