Solving Linear Congruences

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 $4x \equiv 36 \mbox{ (mod } 6 )$.

How do you go about getting the directions you so desperately need? Well, to solve a general linear congruence of the form $ax \equiv b \mbox{ (mod } n )$ it is important to remember the following theorem.

Theorem: $ax \equiv b \mbox{ (mod } n )$ has a solution iff $\gcd(a,n) | b$.

Let us write $d = \gcd(a,n)$ and formulate an algorithm to solve our congruence $ax \equiv b \mbox{ (mod } n )$ – 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 $d | b$.

(2) – Supposing $d | b$, use the Euclidean Algorithm to find $s,t \in \mathbb{Z}$ such that $sa + tn = d$.

(3) – By using $d | b$ there exists $u \in \mathbb{Z}$ such that $b = du$ so we have $sau + tnu = du = b$ and rearranging gives $sau - b = tnu$ so $asu \equiv b \mbox{ (mod } n )$ meaning $x_0 = su$ is a solution to our congruence.

(4) – To get the other solutions we translate $x_0$ by $\frac{nv}{d}$ where $v \in \mathbb{Z}$ . This will exhaust all possible solutions mod $n$ which are $x_0, x_0 + \frac{n}{d},..., x_0 + \frac{(d-1)n}{d}$.

You are now in a position to get home if you ever find yourself in such a scenario.