How to prove $ax \equiv 0 \mod m$ has solutions $x \not\equiv 0$ if $\gcd(a,m) \not= 1$

Question

I'm thinking about

$ax \equiv 0 \mod m$ $\Leftrightarrow$ $m \mid (ax - 0) \Leftrightarrow m\mid ax$

Since $\gcd(a,m) \not= 1$, we have

$m \mid a \Rightarrow m\mid ax$

But I'm not tottaly sure about this. Any hints?

Answer 1

Just do it:

$ax \equiv 0 \mod m$ means there exist some integer $k$ so that $ax = km$. There are an infinite number of such $k$ because $ax = km\implies x = \frac {km}a$ and we can alway just choose $k$ to be a multiple of $a$.

Those would be trivial solutions. If $a|k$ then let $x = \frac ka $ and $ax = km$ is a multiple of $m$ and $x \equiv 0 \mod m$.

So this is a matter of finding $x = \frac {km}a\in \mathbb Z$ and $a\not \mid k$.

This means $m$ and $a$ have a non-trivial factor in common. Which... they do, of course. Let it be $d =\gcd(a,m) \ne 1$. Then

$x = \frac {km} {a} = \frac {k*\gcd(a,m) * (\frac m{\gcd(a,m)})}{\gcd(a,m)*\frac a{\gcd(a,m)}}=\frac {k*\frac m{\gcd(a,m)}}{\frac a{\gcd(a,m)}}= \frac{k}{\frac a{\gcd(a,m)}}\frac m{\gcd(a,m)}$

$k$ can be any multiple of $\frac {a}{\gcd(a,m)}$

....

In other words.

SOLUTION:

Let $d = \gcd(a,m)$. Let $a = a'd; m = m'd$. Then if $x = m'$:

$ax = am' = a'm'd = a'm \equiv 0 \mod m$.

If $d \ne 1$ then $1 < m' < m$ and $x = m' \not \equiv 0 \mod m$.

Answer 2

Let $d$ be the gcd of $a$ and $m$. Then $$ m\mid ax\implies m/d\mid|(a/d)x $$ But $m/d$ and $a/d$ are coprime. So what can we conclude?

Answer 3

Let $d=\gcd(a,m)$, $m/d$ is a solution since $a(m/d)=(a/d)m$ and $a/d$ is an integer.