Imagine a scenario where you’re lost, lost in a big city full of number theorists, and you wish to ask someone for directions to get home. You approach someone and to your surprise they want you to work for the directions! In particular they want you to produce all the solutions of the linear congruence .
How do you go about getting the directions you so desperately need? Well, to solve a general linear congruence of the form it is important to remember the following theorem.
Theorem: has a solution iff .
Let us write and formulate an algorithm to solve our congruence – If you ever visit a city of number theorists I strongly recommend memorising this.
(1) – To even wish of having a solution we have to check that .
(2) – Supposing , use the Euclidean Algorithm to find such that .
(3) – By using there exists such that so we have and rearranging gives so meaning is a solution to our congruence.
(4) – To get the other solutions we translate by where . This will exhaust all possible solutions mod which are .
You are now in a position to get home if you ever find yourself in such a scenario.