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?
Answer
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).
No comments:
Post a Comment