Sunday, 21 August 2016

proof verification - 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?


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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...