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

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?

share|cite|improve this question

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.

share|cite|improve this answer

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.

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.