Sunday, 21 August 2016

proof verification - Prove divisibility in modular arithmetic



I know that a, b, n, and s are all integers and that asbmodn. 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 asbmodn, I know that ask1n+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 das and dkn, so d(as+kn).


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...