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)}.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s