Answer to Question #96786 in Combinatorics | Number Theory for Dina Patel

Question

Part 1: Prove that the system of linear congruences in one variable
x ≡ b1 mod m1
x ≡ b2 mod m2
is solvable if and only if (m1, m2)|b1 − b2. In this case prove that the solution is unique modulo [m1, m2].
Hint: follow the proof of the Chinese Remainder Theorem.
Part 2: Solve the system of congruences
x ≡ 3 mod 4
x ≡ 1 mod 6

Answer 1

If the given system has a solution, then

$x ≡ b_1\ mod\ m_1,\ x ≡ b_2\ mod\ m_2,$

therefore

$x=b_1+k_1m_1,\ x=b_2+k_2m_2$ for some integers $k_1\ and\ k_2$

$b_1-b_2=k_2m_2-k_1m_1$

$(m_1,m_2)$ divides $m_1$ and $m_2$ $\implies$

$b_1-b_2=k_2l_2(m_1,m_2)-k_1l_1(m_1,m_2)$ for some integers $l_1\ and \ l_2$

$b_1-b_2=(m_1,m_2)(k_2l_2-k_1l_1)$

this means $(m_1,m_2)|b_1-b_2$ .

\

If $(m_1,m_2)|b_1-b_2$ ,then

$b_1-b_2=k(m_1,m_2)$

Using Bezout's identity

$(m_1,m_2)=am_1+bm_2$ for some integers $a\ and\ b$

$b_1-b_2=k(am_1+bm_2)\implies$

$b_1-kam_1=b_2+kbm_2$

Now, if we set $x=b_1-kam_1=b_2+kbm_2$, then $x$ is the solution of the given congruence.

If $x_1\ and \ x_2$ are two solutions of the given congruence, then

$x_1=b_1+k_1m_1,\ x_2=b_2+k_2m_2\implies$

$x_1-x_2=b_1-b_2+k_1m_1-k_2m_2$

$(m_1,m_2)$ divides $m_1\ and\ m_2$ and we proved that $(m_1,m_2)|(b_1-b_2)$, therefore

$x_1-x_2$ is divisible by $(m_1,m_2)$

and the solution is unique modulo $(m_1,m_2).$

\

x ≡ 3 mod 4

x ≡ 1 mod 6

3x ≡ 9 mod 12

2x ≡ 2 mod 12

3x-2x=x≡7 mod 12

x=7 is the solution of the given congruence.

Answer: x=7.