Saturday, 7 September 2013

elementary number theory - Using two congruences and gcd

Prove that if $b_1, b_2 \in \mathbb Z$ and $d_1, d_2 \in \mathbb Z^+$, then there exists at least one solution $x \in \mathbb Z$ satisfying simultaneously:



$x \equiv b_1 ($mod $d_1)$



$x \equiv b_2 ($mod $d_2)$



if and only if gcd$(d_1,d_2)|(b_1-b_2)$.




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



$x \equiv b_1 ($mod $d_1) \Rightarrow x = b_1 + k_1d_1$, some $k_1 \in \mathbb Z$



$x \equiv b_2 ($mod $d_2) \Rightarrow x = b_2 + k_2d_2$, some $k_2 \in \mathbb Z$



Rearrange to get: $(b_1 - b_2) + k_1d_1 = k_2d_2$



But now I'm stuck.

No comments:

Post a Comment