Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There's a proof in a section in my book on modular arithmetic I don't really understand. On linear congruences:

$ax \equiv b \text{ (mod $m$)}$

Suppose that $\gcd({a,m}) = d > 1$ and $b$ is divisible by $d$. We can divide both sides of the linear congruence by $d$:

$\frac{a}{d}x \equiv \frac{b}{d}$ (mod $\frac{m}{d}$), gcd($\frac{a}{d}$, $\frac{m}{d}$) $= 1$.

This last linear congruence has exactly one solution $r \in$ $\mathbb{N}[0, \frac{m}{d}-1]$. Therefore the solutions to $ax \equiv$ $b$ (mod $m$) are $r + t\frac{m}{d}$ with $t \in \mathbb{N}[0,d-1]$.

I understand everything except the last sentence. I have an intuition on why this might be true, but how can it be proven?

share|cite|improve this question
up vote 1 down vote accepted

Here is a different approach.

Suppose that $r'\in\Bbb N\cap[0,m-1]$ is a solution to the first congruence. Notice that $r'$ must also be a solution to the second congruence. If $r'\in\Bbb N\cap[0,{m\over d}-1],$ then we are done (and $r=r'$). Otherwise, there must exist some integer $s<0$ such that $r'+s{m\over d}\in\Bbb N\cap[0,{m\over d}-1].$ Set $r=r'+s{m\over d}.$ Then $r$ is obviously the unique solution to the second congruence in the mentioned interval, and we have $r'=r+t{m\over d}$ with $t=-s.$

Notice also that $|t{m\over d}|=|r-r'|< m,$ which implies that $|t|=t< d.$

Thus any solution $r'$ of the first congruence has the given form. Conversely, it is easy to show that every $r'=r+t{m\over d},$ with $r$ a solution to the second congruence, is a solution to the first.

share|cite|improve this answer

Let $S:\{r\}$ is a complete residue $\pmod M,$ where $0 \le r<M$.

Now let us consider $T:\{A\cdot s\}$ where $0 \le r<M$ and $(A,M)=1$

If $A\cdot s_i\equiv A\cdot s_j\pmod M$ where $0\le s_i<s_j<M$

$\implies M\mid A(s_i-s_j)\implies M\mid(s_i-s_j)$

But $M\not\mid (s_i-s_j)$ as $0<s_j-s_i<M$

So, $T$ is also a complete residue and each element of $T$ is congruent to exactly one element of $S$.

Hence, we have exactly one solution of $A\cdot x\equiv B\pmod M$ for $(A,M)=1$

So, the solution is $\frac BA\pmod M=\frac BA+tM$ where $t$ is any integer.

We consider two roots to be different, if they are in-congruent $\pmod m$

If $\frac aA=\frac mM=d=(a,m),$

and $\frac BA+t_1M\equiv \frac BA+t_2M\pmod m\iff m\mid M(t_2-t_1)\implies t_1\equiv t_2\pmod{\frac mM}$

So, there are exactly $\frac mM=d=(a,m)$ in-congruent solutions $\pmod m$ of the form $\frac BA+t\cdot M=\frac BA+t\cdot \frac md$ where $0\le t<d$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.