0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.