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?


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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