In this post we investigate the solution of linear congruences. Linear congruences are those of the form below, in which is a given positive integer, and are given integers and is an unknown integer.
This congruence is equivalent to the equation , so every integer which is congruent to a solution modulo is also a solution. This equation is simply a linear equation in the ring and therefore it can be solved in the same way: find an inverse of and multiply both sides by this inverse, thus cancelling out from the left-hand side and leaving just there. This gives the solution where is an integer such that is the inverse of , or, writing this as a congruence,
There is, in fact, a simple condition for determining whether the inverse of exists. For every integer , is the inverse of if and only if , i.e. is congruent to 1 modulo . That means there is an integer such that , i.e. . But this means 1 is a linear combination of and , and the smallest positive linear combination of and is . This proves the following proposition.
Proposition 1 For every integer , is invertible if and only if is relatively prime to (i.e. ), and if it is invertible, its inverse is the congruence class of the coefficient of in the expression of as a linear combination of and (which can be found using Euclid’s algorithm).
Therefore, solving the equation in the case where is simply a matter of applying Euclid’s algorithm. Now, if , we cannot be sure that no solutions exist. In fact, if , the congruence
where , and , has the same set of solutions as (1). This is because for every pair of integers and and every integer , is congruent to modulo if and only if is congruent to modulo , because for every integer , if and only if . And (3) can be solved by Euclid’s algorithm because . This gives the solution
where is an integer such that is the inverse of . Note that the modulus here is rather than . The solutions are all congruent modulo , but there may be solutions which are non-congruent modulo . In fact, for every solution , , , \textellipsis and are also solutions (since these are all congruent to modulo ), yet these are all non-congruent modulo , because , , \textellipsis and are all less than and hence not divisible by . However, every solution is congruent to one of these solutions modulo , because every solution has the form where is an integer, and if we let be the remainder of in , then for some integer , which means the solution has the form , which is congruent to modulo , and since , . So the set of congruence classes of solutions modulo is finite, and its members can be listed:
As for the case where , it can be easily proven that there are no solutions: for if is a solution of (1), there is an integer such that , hence , which is a linear combination of and and hence divisible by .