I know that a, b, n, and s are all integers and that as≡bmodn. 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 ki are integers. From as≡bmodn, I know that as≡k1n+b . gcd(a,n) = d and d divides a or d|a and d|n, so d|as and d|k1n . Then as=k2d and k1n=k3d. From there, as=k3d+b and so (as)/(k3d)=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=k2d but you haven't used it.
You can go about this with much less pain if you don't bother using these ki. Just from the fact that as+kn=b, and since d∣as and d∣kn, so d∣(as+kn).
No comments:
Post a Comment