# Linear congruences

In this post we investigate the solution of linear congruences. Linear congruences are those of the form below, in which ${m}$ is a given positive integer, ${a}$ and ${b}$ are given integers and ${x}$ is an unknown integer.

$\displaystyle a x \equiv b \mod m. \ \ \ \ \ (1)$

This congruence is equivalent to the equation ${[a]_m [x]_m = [b]_m}$, so every integer which is congruent to a solution modulo ${m}$ is also a solution. This equation is simply a linear equation in the ring ${{\mathbb Z}_m}$ and therefore it can be solved in the same way: find an inverse of ${[a]_m}$ and multiply both sides by this inverse, thus cancelling out ${[a]_m}$ from the left-hand side and leaving just ${[x]_m}$ there. This gives the solution ${[x]_m = [r]_m [b]_m}$ where ${r}$ is an integer such that ${[r]_m}$ is the inverse of ${[a]_m}$, or, writing this as a congruence,

$\displaystyle x \equiv r b \mod m. \ \ \ \ \ (2)$

There is, in fact, a simple condition for determining whether the inverse of ${[a]_m}$ exists. For every integer ${b}$, ${[b]_m}$ is the inverse of ${[a]_m}$ if and only if ${[a]_m [b]_m = [1]_m}$, i.e. ${a b}$ is congruent to 1 modulo ${m}$. That means there is an integer ${q}$ such that ${a b = q m + 1}$, i.e. ${a b - q m = 1}$. But this means 1 is a linear combination of ${a}$ and ${m}$, and the smallest positive linear combination of ${a}$ and ${m}$ is ${\gcd(a, m)}$. This proves the following proposition.

Proposition 1 For every integer ${a}$, ${[a]}$ is invertible if and only if ${a}$ is relatively prime to ${m}$ (i.e. ${\gcd(a, m) = 1)}$), and if it is invertible, its inverse is the congruence class of the coefficient of ${a}$ in the expression of ${\gcd(a, m)}$ as a linear combination of ${a}$ and ${m}$ (which can be found using Euclid’s algorithm).

Therefore, solving the equation in the case where ${\gcd(a, m) = 1}$ is simply a matter of applying Euclid’s algorithm. Now, if ${\gcd(a, m) \ne 1}$, we cannot be sure that no solutions exist. In fact, if ${\gcd(a, m) \mid b}$, the congruence

$\displaystyle a' x \equiv b' \mod m', \ \ \ \ \ (3)$

where ${a' = a / \gcd(a, m)}$, ${b' = b / \gcd(a, m)}$ and ${m' = m / \gcd(a, m)}$, has the same set of solutions as (1). This is because for every pair of integers ${a}$ and ${b}$ and every integer ${n}$, ${a}$ is congruent to ${b}$ modulo ${m}$ if and only if ${n a}$ is congruent to ${n b}$ modulo ${m n}$, because for every integer ${q}$, ${a = q m + b}$ if and only if ${n a = q m n + b n}$. And (3) can be solved by Euclid’s algorithm because ${\gcd(a', m') = \gcd(a / \gcd(a, m), m / \gcd(a, m)) = \gcd(a, m) / \gcd(a, m) = 1}$. This gives the solution

$\displaystyle x \equiv r' b' \mod m', \ \ \ \ \ (4)$

where ${r'}$ is an integer such that ${[r']_{m'}}$ is the inverse of ${[a']_{m'}}$. Note that the modulus here is ${m'}$ rather than ${m}$. The solutions are all congruent modulo ${m'}$, but there may be solutions which are non-congruent modulo ${m}$. In fact, for every solution ${x}$, ${m' + x}$, ${2 m' + x}$, \textellipsis and ${(\gcd(a, m) - 1) m' + x}$ are also solutions (since these are all congruent to ${x}$ modulo ${m'}$), yet these are all non-congruent modulo ${m}$, because ${m'}$, ${2 m'}$, \textellipsis and ${(\gcd(a, m) - 1) m' = m - \gcd(a, m)}$ are all less than ${m}$ and hence not divisible by ${m}$. However, every solution is congruent to one of these solutions modulo ${m}$, because every solution has the form ${q m' + x}$ where ${q}$ is an integer, and if we let ${R}$ be the remainder of ${\gcd(a, m)}$ in ${q}$, then ${q = Q \gcd(a, m) + R}$ for some integer ${Q}$, which means the solution has the form ${(Q \gcd(a, m) + R) m' + x = Q m + R m' + x}$, which is congruent to ${R \gcd(a, m) m' + x}$ modulo ${m}$, and since ${0 \le R < \gcd(a, m)}$, ${0 \le R m' < m}$. So the set of congruence classes of solutions modulo ${m}$ is finite, and its ${\gcd(a, m)}$ members can be listed:

$\displaystyle \{[x]_m, [m' + x]_m, [2 m' + x]_m, \dotsc, [(\gcd(a, m) - 1) m' + x]_m\}.$

As for the case where ${\gcd(a, m) \nmid b}$, it can be easily proven that there are no solutions: for if ${x}$ is a solution of (1), there is an integer ${q}$ such that ${a x = q m + b}$, hence ${b = a x - q m}$, which is a linear combination of ${a}$ and ${m}$ and hence divisible by ${\gcd(a, m)}$.