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?

Printable View

- Feb 7th 2008, 11:58 AMtttcomraderGCD Congruence problem
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? - Feb 8th 2008, 09:17 PMkalagota