# Prove divisibility in modular arithmetic

I know that a, b, n, and s are all integers and that $as \equiv b \mod n$. I want to prove that gcd(a,n) divides b. I think I have most of the pieces figured out, but I am not sure how to complete the proof. All $k_i$ are integers. From $as \equiv b \mod n$, I know that $as \equiv k_1 n +b$ . gcd(a,n) = d and d divides $a$ or $d|a$ and $d|n$, so $d|as$ and $d|k_1 n$ . Then $as = k_2 d$ and $k_1 n = k_3 d$. From there, $as = k_3 d + b$ and so $(as)/(k_3 d) = b$. I see that this isn't what I'm trying to prove. How do I continue, or am I even on the right track?

You've got $as = k_2 d$ but you haven't used it.
You can go about this with much less pain if you don't bother using these $k_i$. Just from the fact that $as + kn = b$, and since $d \mid as$ and $d \mid kn$, so $d \mid (as + kn)$.