# If $a \neq 0$ and $b$ are elements in $\mathbb{ Z}_n$ and $ax = b$ has no solutions in $\mathbb{ Z}_n$, then $a$ is a zero divisor?

If $a \neq 0$ and $b$ are elements in $\mathbb{ Z}_n$ and $ax = b$ has no solutions in $\mathbb{ Z}_n$, then $a$ is a zero divisor?

Is this question essentially saying that if $ax = b$ has no solution then $ax =0$ must have a solution?

-
add comment

## 2 Answers

Suppose that $ax\equiv b \mod n$ has no solutions, for some integers $a,b$ and $n>1$. Then $\gcd(a,n)\neq 1$, because if the gcd was $1$, then $a$ would be a unit in $\mathbb{Z}/n\mathbb{Z}$, there would exist $a'\in\mathbb{Z}$ such that $aa'\equiv 1 \bmod n$, and therefore $x\equiv a'b \bmod n$ would be a solution to $ax\equiv b \bmod n$.

Hence, $d=\gcd(a,n)>1$. Let $n=d\cdot m$ and $a=d\cdot t$. Then $$a\cdot m \equiv (d\cdot t) \cdot m \equiv t\cdot(d\cdot m)\equiv t \cdot n \equiv 0 \bmod n.$$ Hence $x\equiv m\bmod n$ is a solution to $ax\equiv 0 \bmod n$. Since $d>1$, the number $m$ is a proper divisor of $n$, and $m\not\equiv 0 \bmod n$. Hence $a$ is a zero divisor.

-
Thanks, I noticed you're a professor, what do you suggest I do in order to such problems quickly on my own? –  grayQuant Feb 22 '13 at 2:51
Also is there a solution that does not involve solving a modular equation? I'm asking because none of the examples in my book involve the solution of a modular equation and I'm afraid of missing something. –  grayQuant Feb 22 '13 at 3:09
You need a good book in elementary number theory and/or abstract algebra and read and study it carefully. What book are you using? –  Álvaro Lozano-Robledo Feb 22 '13 at 15:33
add comment

Hint $\ ax\!=\!b\,$ solvable $\!\iff\! x\overset{h}\to ax$ onto $\!\iff\!\! \,h\,\ 1$-$1\!\iff\!\ker h = 0\!\iff\! a\,$ non-zero-divisor

-
add comment