Question

Let $a,b,n$be integers with $n>1$and let $d=\left(a,n\right)$. If the equation $\left[a\right]x=\left[b\right]$has a solution in ${\mathrm{\mathbb{Z}}}_n$, prove that $d|b$.

Short answer

It is proved that $d|b$.

Step-by-step solution

Find the solution

It is given that $a,bandn$are integers with $n>1$.

Let $x=\left[r\right]$is the solution of $\left[a\right]x=\left[b\right]$, then

$$\begin{gathered} \left[a\right]⊝\left[r\right]-\left[b\right]=0 \\ \to n|\left(ar-b\right) \end{gathered}$$

This again gives that $ar-b=nk$, implying $ar-nk=b$.

Proof part

As d divides the left part, then it must also divide the right part, that is $d|b$.

Hence, the given statement is proved.