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, 12:58 PMtttcomraderGCD 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, 10:17 PMkalagota