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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...