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.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s