Question #96786
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
1
Expert's answer
2019-10-18T13:27:34-0400

If the given system has a solution, then

xb1 mod m1, xb2 mod m2,x ≡ b_1\ mod\ m_1,\ x ≡ b_2\ mod\ m_2,

therefore

x=b1+k1m1, x=b2+k2m2x=b_1+k_1m_1,\ x=b_2+k_2m_2 for some integers k1 and k2k_1\ and\ k_2

b1b2=k2m2k1m1b_1-b_2=k_2m_2-k_1m_1

(m1,m2)(m_1,m_2) divides m1m_1 and m2m_2     \implies

b1b2=k2l2(m1,m2)k1l1(m1,m2)b_1-b_2=k_2l_2(m_1,m_2)-k_1l_1(m_1,m_2) for some integers l1 and l2l_1\ and \ l_2

b1b2=(m1,m2)(k2l2k1l1)b_1-b_2=(m_1,m_2)(k_2l_2-k_1l_1)

this means (m1,m2)b1b2(m_1,m_2)|b_1-b_2 .

\

If (m1,m2)b1b2(m_1,m_2)|b_1-b_2 ,then

b1b2=k(m1,m2)b_1-b_2=k(m_1,m_2)

Using Bezout's identity

(m1,m2)=am1+bm2(m_1,m_2)=am_1+bm_2 for some integers a and ba\ and\ b

b1b2=k(am1+bm2)    b_1-b_2=k(am_1+bm_2)\implies

b1kam1=b2+kbm2b_1-kam_1=b_2+kbm_2

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

If x1 and x2x_1\ and \ x_2 are two solutions of the given congruence, then

x1=b1+k1m1, x2=b2+k2m2    x_1=b_1+k_1m_1,\ x_2=b_2+k_2m_2\implies

x1x2=b1b2+k1m1k2m2x_1-x_2=b_1-b_2+k_1m_1-k_2m_2

(m1,m2)(m_1,m_2) divides m1 and m2m_1\ and\ m_2 and we proved that (m1,m2)(b1b2)(m_1,m_2)|(b_1-b_2), therefore

x1x2x_1-x_2 is divisible by (m1,m2)(m_1,m_2)

and the solution is unique modulo (m1,m2).(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.



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS