Does an $x \in \mathbb Z$ with $xa\equiv_nb$ exist, if $gcd(a,n) $ divides $b$?

Question

Does an $x \in \mathbb Z$ with $xa\equiv_nb$ exist, if $gcd(a,n) $ divides $b$ ?

My idea: \begin{aligned} & xa &\equiv_n& \quad b \cr \Leftrightarrow \quad& x& \equiv_n& \quad b \cdot a^{-1} & \qquad \text { } a^{-1} \text{ ex., } \quad ggT(a,n) | b \cr \Rightarrow \quad& x&=& \quad \frac{kn + b}{a} & \qquad \text { } \exists k \in \mathbb Z \cr \end{aligned}

Does $a^{-1}$ always exist when $gcd(a,n) $ divides $b$ ?

Answer 1

I'll give it another try: $$a,b,x,k,p \in \mathbb Z \qquad n\in \mathbb N, n\geq2$$

In general: $$xa \equiv_n b \quad \Leftrightarrow \quad n |(xa-b) \quad \Leftrightarrow \quad nk = xa -b $$

So:

$$ \begin{aligned}& gcd(a,n) | b \cr \Leftrightarrow \quad & (kn+xa) | b \cr \Leftrightarrow \quad & p(kn+xa) = b \cr \Leftrightarrow \quad & knp +xap = b \cr \Leftrightarrow \quad & knp = b - xap \cr \Leftrightarrow \quad & n(-kp) = xap - b \cr \Leftrightarrow \quad & n|(xa-b) \cr \Leftrightarrow \quad & xa \equiv_n b \end{aligned}$$