Saturday, 7 September 2013

elementary number theory - Using two congruences and gcd

Prove that if b1,b2Z and d1,d2Z+, then there exists at least one solution xZ satisfying simultaneously:



xb1(mod d1)



xb2(mod d2)



if and only if gcd(d1,d2)|(b1b2).




So, so far what I have done is the following:



xb1(mod d1)x=b1+k1d1, some k1Z



xb2(mod d2)x=b2+k2d2, some k2Z



Rearrange to get: (b1b2)+k1d1=k2d2



But now I'm stuck.

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}...