# Number Theory proofs relating to gcd and mod

How do you prove that the congruence $ax \equiv b \pmod m$ has exactly $d = (a,m)$ solutions?

I know that this proof is false but I can't come up with any counterexamples. Any ideas?

-

## 2 Answers

Let $(a,m)>1$ and $(a,m) \mid b$. We define:

$$d=(a,m) , a_1=\frac{a}{d}, b_1=\frac{b}{d}, m_1=\frac{m}{d}$$

Then, $ax \equiv b \pmod m$ is equivalent to $a_1 x \equiv b_1 \pmod {m_1} (1)$

As $(a_1,m_1)=1$ , (1) has exactly one solution.So,there is a solution $\xi_0$ of (1).

And as $ax \equiv b \pmod m$ is equivalent to (1),the solutions of $ax \equiv b \pmod m$ are the elements of the set: $$[\xi]_{m_1}=\{ \xi | \xi_0 \equiv 0 \pmod {m_1}\}=\{qm_1+\xi_0 | q \in \mathbb{Z} \}$$

Now we have to check how many of them are inequivalent $\pmod m$.

We have:

$$q'm_1+\xi_0 \equiv q''m_1+\xi_0 \pmod m \Leftrightarrow q'm_1 \equiv q''m_1 \pmod {dm_1} \Leftrightarrow q' \equiv q'' \pmod d$$

So the solutions $qm_1+\xi_0$,that are inequivalent $\pmod m$ come from the values of $q$,that are inequivalent $\pmod d$.Such values of $q$ are elements of a complete system of residues modulo d,for example of this one: $\{ 0,1, \dots , d-1 \}$.

We conclude that the $d=(a,m)$ numbers:

$$\xi_0, m_1+ \xi_0, \dots, (d-1)m_1+\xi_0$$

are inequivalent $\pmod m$ solutions of $ax \equiv b \pmod m$ and that each other solution is equivalent $\pmod m$ to one of them.

-

If $(a,m)\mid b$ then we can divide the congruence by $(a,m)$ to get $\frac{a}{(a,m)}x\equiv\frac{b}{(a,m)}$ mod $\frac{m}{(a,m)}$.

Since $(\frac{a}{(a,m)},\frac{m}{(a,m)})=\frac{(a,m)}{(a,m)}=1$ we know $\frac{a}{(a,m)}$ is a unit mod $\frac{m}{(a,m)}$, so we can divide to get

$$x\equiv \left(\frac{a}{(a,m)}\right)^{-1}\frac{b}{(a,m)}\mod{\frac{m}{(a,m)}}.$$

Any residue mod $m'$ lifts up to $\frac{m}{m'}$ residues mod $m$, so there are $m/\hskip -0.06in \frac{m}{(a,m)}=(a,m)$ solutions.

Conversely given a solution, multiplying both sides by $\frac{m}{(a,m)}$ yields $m\mid b\frac{m}{(a,m)}\Rightarrow (a,m)\mid b$, so this condition is necessary for there to be any solution at all.

-