# Number of Solutions for Congruency Equations

I'm leaning congruency equations, so for example: $$ax \equiv b \pmod m$$ I have that the number of solutions will be equal to $d$, where $$d = \gcd(a, m).$$ And the solutions ae: $$x, x+m/d, x+2m/d, x+3m/d, \ldots , x+(d-1)m/d$$ Now, having understood how I solve the equation, I am still not entirely sure as to why the number of solutions is given by $d$...

Cheers! :)

• If $d$ does not divide $b$, there are no solutions. May 15, 2013 at 22:07
• Fair enough, but by are there precisely "d" solutions?
– MrD
May 15, 2013 at 22:07
• Will write an answer if no one else does soon. May 15, 2013 at 22:09

Let $$d$$ be a common divisor of $$a$$ and $$m$$. If the congruence $$ax\equiv b\pmod{m}$$ has a solution, then $$ax-b$$ is a multiple of $$m$$. Since $$d$$ divides both $$m$$ and $$a$$, it must divide $$b$$. In particular, if $$d$$ is the gcd of $$a$$ and $$m$$, the congruence has no solutions unless $$d$$ divides $$b$$. So from now on we suppose that $$d$$ divides $$b$$. Let $$a=a_1d$$, $$m=m_1d$$, and $$b=b_1d$$.

The congruence $$a_1dx\equiv b_1d\pmod{m_1d}$$ holds if and only if $$m_1d$$ divides $$a_1d x -b_1d$$. This is the case if and only if $$m_1$$ divides $$a_1 x-b_1$$, that is, if and only if $$a_1x\equiv b_1\pmod{m_1}$$.

So now consider the congruence $$a_1x\equiv b_1\pmod{m_1}$$. Since $$d$$ is the greatest common divisor of $$a$$ and $$m$$, it follows that the numbers $$a_1$$ and $$m_1$$ are relatively prime.

Because $$a_1$$ and $$m_1$$ are relatively prime, the congruence $$a_1x\equiv b_1\pmod{m_1}$$ has a unique solution modulo $$m$$. For a proof of uniqueness, we can use the fact that $$a_1$$ has an inverse $$c$$ modulo $$m_1$$. Then $$ax\equiv b\pmod{m_1}$$ if and only if $$ca_1x\equiv cb_1\pmod{m_1}$$, that is, if and only if $$x\equiv cb_1\pmod{m_1}$$. (One can also give a direct proof of uniqueness without using the inverse.)

So now we ask: given the unique solution $$x$$ modulo $$m_1$$, which numbers are congruent to $$x$$ modulo $$m$$? Certainly the numbers $$x+\frac{im}{d}$$ are, where $$i$$ ranges from $$0$$ to $$d-1$$. For these are the numbers $$x+im_1$$, and they are all congruent to $$x$$ modulo $$m_1$$.

Are there any others? Suppose that $$y\equiv x\pmod{m_1}$$. Then $$m_1$$ divides $$y-x$$. So the possible remainders when $$y-x$$ is divided by $$m$$ are $$0, m_1,2m_1,\dots, (d-1)m_1$$. It follows that $$y-x \equiv im_1 \pmod{m}$$ for some $$i$$ where $$0\le i\le d-1$$. This just says that $$y\equiv x+im_1 \pmod{m}$$, that is, $$y\equiv x+\frac{mi}{d}\pmod{m}$$, for some $$i$$ ranging from $$0$$ to $$d-1$$.

Remark: The important part was the uniqueness modulo $$m_1$$. The rest is straightforward, and you know it well. To give a simple numerical example, suppose that we know that $$x\equiv 3\pmod{16}$$. What can we say about $$x$$ modulo $$80$$? We can say that $$x$$ is congruent to one of $$3$$, $$19$$, $$35$$, $$51$$, $$67$$.

• Hi, just a question (may be I've been doing maths for too long), what does a = 1(1) mean in the first paragraph?
– MrD
May 15, 2013 at 22:59
• Anyway, think I've understood it, thanks :D
– MrD
May 15, 2013 at 23:00
• @user1876047: It means there was a typo, it was supposed to be $a=a_1d$. Corrected. Thanks for finding it. May 15, 2013 at 23:02
• Also, hm, I understand d is gcd(a,m), but shouldn't it divide a and m for them to be relatively prime? If it multiplies it then they would both could be divided by d^2?
– MrD
May 15, 2013 at 23:02
• If $d$ is the gcd, and $a=a_1d$, $m=m_1d$, then $a_1$ and $m_1$ must be relatively prime, for if they had a non-trivial common divisor $e$, then $de$ would divide $a$ and $m$, so $d$ would not be their gcd. May 15, 2013 at 23:06

If you scroll down on this pdf you will find a complete proof of this http://www.math.niu.edu/~richard/Math420/lin_cong.pdf

I couldn't be bothered to type it up. Sorry.

• I'm sorry, but I still don't understand :S I see the range of solutions, but I don't see why it has to stop at gcd(a,m)-1...
– MrD
May 15, 2013 at 22:38