Prove that if gcd (a,b) = c, then bx congruences c (mod a) for some integer x. Proof. we have cx=a, cw=b, and ai+bj=c. I need a|bx-c for some x. bx-c = cwx-c = aw-c = aw - ai - bj now, how do I get an a out of the bj?
Last edited by tttcomrader; February 7th 2008 at 06:32 PM.
Follow Math Help Forum on Facebook and Google+
Originally Posted by tttcomrader Prove that if gcd (a,b) = c, then bx congruences c (mod a) for some integer x. Proof. we have cx=a, cw=b, and ai+bj=c. I need a|bx-c for some x. bx-c = cwx-c = aw-c = aw - ai - bj now, how do I get an a out of the bj? let me try.. (a,b) = c implies ay + bx = c for some integers y and x.. now, bx - c = -ay = a(-y) for some integers y and x.. and so, a|bx - c..
View Tag Cloud