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?


2 Answers 2


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.


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$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .