Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$...
Anybody can calrify please?
Cheers! :)
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$.
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.
