# 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. – André Nicolas May 15 '13 at 22:07
Fair enough, but by are there precisely "d" solutions? – MrD May 15 '13 at 22:07
Will write an answer if no one else does soon. – André Nicolas May 15 '13 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=im_1$ 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 '13 at 22:59
Anyway, think I've understood it, thanks :D – MrD May 15 '13 at 23:00
@user1876047: It means there was a typo, it was supposed to be $a=a_1d$. Corrected. Thanks for finding it. – André Nicolas May 15 '13 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 '13 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. – André Nicolas May 15 '13 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 '13 at 22:38