Menu Close

Solve-the-equation-x-3-mod-5-x-4-mod-7-x-2-mod-3-

Tinku Tara 0 Comments
Pin




Question Number 86791 by TawaTawa1 last updated on 31/Mar/20
Solve the equation: x ≡ 3 (mod 5) x ≡ 4 (mod 7) x ≡ 2 (mod 3)
$$\mathrm{Solve}\:\mathrm{the}\:\mathrm{equation}: \\ $$$$\:\:\:\:\mathrm{x}\:\:\equiv\:\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{5}\right) \\ $$$$\:\:\:\:\mathrm{x}\:\:\equiv\:\:\mathrm{4}\:\left(\mathrm{mod}\:\mathrm{7}\right) \\ $$$$\:\:\:\:\mathrm{x}\:\:\equiv\:\:\mathrm{2}\:\left(\mathrm{mod}\:\mathrm{3}\right) \\ $$
Answered by mr W last updated on 31/Mar/20
x=5k+3 x=7h+4 x=3i+2 5k+3=7h+4 5k−7h=1 ⇒k=7m−4 ⇒x=5(7m−4)+3=35m−17 ⇒h=5m−3 35m−17=3i+2 35m−3i=19 ⇒m=3n+2 ⇒i=35n+17 ⇒x=35(3n+2)−17=105n+53
$${x}=\mathrm{5}{k}+\mathrm{3} \\ $$$${x}=\mathrm{7}{h}+\mathrm{4} \\ $$$${x}=\mathrm{3}{i}+\mathrm{2} \\ $$$$\mathrm{5}{k}+\mathrm{3}=\mathrm{7}{h}+\mathrm{4} \\ $$$$\mathrm{5}{k}−\mathrm{7}{h}=\mathrm{1} \\ $$$$\Rightarrow{k}=\mathrm{7}{m}−\mathrm{4}\:\Rightarrow{x}=\mathrm{5}\left(\mathrm{7}{m}−\mathrm{4}\right)+\mathrm{3}=\mathrm{35}{m}−\mathrm{17} \\ $$$$\Rightarrow{h}=\mathrm{5}{m}−\mathrm{3} \\ $$$$\mathrm{35}{m}−\mathrm{17}=\mathrm{3}{i}+\mathrm{2} \\ $$$$\mathrm{35}{m}−\mathrm{3}{i}=\mathrm{19} \\ $$$$\Rightarrow{m}=\mathrm{3}{n}+\mathrm{2} \\ $$$$\Rightarrow{i}=\mathrm{35}{n}+\mathrm{17} \\ $$$$\Rightarrow{x}=\mathrm{35}\left(\mathrm{3}{n}+\mathrm{2}\right)−\mathrm{17}=\mathrm{105}{n}+\mathrm{53} \\ $$
Commented by TawaTawa1 last updated on 31/Mar/20
How sir please. Please sir. It is the geimetry question i want you to help me. Thanks for your time sir.
$$\mathrm{How}\:\mathrm{sir}\:\mathrm{please}. \\ $$$$\mathrm{Please}\:\mathrm{sir}.\:\mathrm{It}\:\mathrm{is}\:\mathrm{the}\:\mathrm{geimetry}\:\mathrm{question}\:\mathrm{i}\:\mathrm{want}\:\mathrm{you}\:\mathrm{to}\:\mathrm{help}\:\mathrm{me}. \\ $$$$\mathrm{Thanks}\:\mathrm{for}\:\mathrm{your}\:\mathrm{time}\:\mathrm{sir}. \\ $$
Commented by TawaTawa1 last updated on 31/Mar/20
I got x = 53 for the congruence sir.
$$\mathrm{I}\:\mathrm{got}\:\:\mathrm{x}\:\:=\:\:\mathrm{53}\:\:\mathrm{for}\:\mathrm{the}\:\mathrm{congruence}\:\mathrm{sir}. \\ $$
Commented by Joel578 last updated on 31/Mar/20
Sorry sir, it should be 2, 5, 8, 11, 14, 17, ...
$$\mathrm{Sorry}\:\mathrm{sir},\:\mathrm{it}\:\mathrm{should}\:\mathrm{be} \\ $$$$\mathrm{2},\:\mathrm{5},\:\mathrm{8},\:\mathrm{11},\:\mathrm{14},\:\mathrm{17},\:… \\ $$
Commented by mr W last updated on 31/Mar/20
thanks! now fixed.
$${thanks}!\:{now}\:{fixed}. \\ $$
Answered by Joel578 last updated on 31/Mar/20
with Chinese Remainder Theorem a_1 = 3, m_1 = 5 a_2 = 4, m_2 = 7 a_3 = 2, m_3 = 3 ⇒ m = (m_1 )(m_2 )(m_3 ) = 105 ⇒ M_1 = (m/m_1 ) = 21, M_2 = (m/m_2 ) = 15, M_3 = (m/m_3 ) = 35 Now find invers modulus of M_k mod m_k , or in other words, find y_k such that M_k y_k ≡ 1 (mod m_k ) ⇒ y_1 = 1, y_2 = 1, y_3 = 2 ⇒ y = a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 = 63 + 60 + 140 = 263 ⇒ x ≡ y mod 105 ⇒ x = 53 → smallest positive value
$$\mathrm{with}\:\mathrm{Chinese}\:\mathrm{Remainder}\:\mathrm{Theorem} \\ $$$${a}_{\mathrm{1}} \:=\:\mathrm{3},\:{m}_{\mathrm{1}} \:=\:\mathrm{5} \\ $$$${a}_{\mathrm{2}} \:=\:\mathrm{4},\:{m}_{\mathrm{2}} \:=\:\mathrm{7} \\ $$$${a}_{\mathrm{3}} \:=\:\mathrm{2},\:{m}_{\mathrm{3}} \:=\:\mathrm{3} \\ $$$$\Rightarrow\:{m}\:=\:\left({m}_{\mathrm{1}} \right)\left({m}_{\mathrm{2}} \right)\left({m}_{\mathrm{3}} \right)\:=\:\mathrm{105} \\ $$$$\Rightarrow\:{M}_{\mathrm{1}} \:=\:\frac{{m}}{{m}_{\mathrm{1}} }\:=\:\mathrm{21},\:{M}_{\mathrm{2}} \:=\:\frac{{m}}{{m}_{\mathrm{2}} }\:=\:\mathrm{15},\:{M}_{\mathrm{3}} \:=\:\frac{{m}}{{m}_{\mathrm{3}} }\:=\:\mathrm{35} \\ $$$$ \\ $$$$\mathrm{Now}\:\mathrm{find}\:\mathrm{invers}\:\mathrm{modulus}\:\mathrm{of}\:\:{M}_{{k}} \:\mathrm{mod}\:{m}_{{k}} ,\:\mathrm{or}\:\mathrm{in}\:\mathrm{other}\:\mathrm{words}, \\ $$$$\mathrm{find}\:{y}_{{k}} \:\mathrm{such}\:\mathrm{that}\:{M}_{{k}} {y}_{{k}} \:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:{m}_{{k}} \right) \\ $$$$\Rightarrow\:{y}_{\mathrm{1}} \:=\:\mathrm{1},\:{y}_{\mathrm{2}} \:=\:\mathrm{1},\:{y}_{\mathrm{3}} \:=\:\mathrm{2} \\ $$$$ \\ $$$$\Rightarrow\:{y}\:=\:{a}_{\mathrm{1}} {M}_{\mathrm{1}} {y}_{\mathrm{1}} \:+\:{a}_{\mathrm{2}} {M}_{\mathrm{2}} {y}_{\mathrm{2}} \:+\:{a}_{\mathrm{3}} {M}_{\mathrm{3}} {y}_{\mathrm{3}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:=\:\mathrm{63}\:+\:\mathrm{60}\:+\:\mathrm{140}\:=\:\mathrm{263} \\ $$$$\Rightarrow\:{x}\:\equiv\:{y}\:\mathrm{mod}\:\mathrm{105}\:\Rightarrow\:{x}\:=\:\mathrm{53}\:\rightarrow\:\mathrm{smallest}\:\mathrm{positive}\:\mathrm{value} \\ $$
Commented by TawaTawa1 last updated on 31/Mar/20
God bless you sir
$$\mathrm{God}\:\mathrm{bless}\:\mathrm{you}\:\mathrm{sir} \\ $$
Commented by Ar Brandon last updated on 08/Apr/20
��
Answered by Rio Michael last updated on 31/Mar/20
another method (algebraic) x ≡ 3 (mod 5)......(i) x ≡ 4 (mod 7) ......(ii) x ≡ 2( mod 3).......(iii) from (i) x = 5k + 3 , k ∈ Z .....(i) in (ii) 5k + 3 ≡ 4 (mod 7) 5k ≡ 1( mod 7) by trial and error k ≡ 3 (mod 7) ⇒ k = 7s + 3 , s ∈Z ⇒ x = 5(7s + 3) + 3 x = 35s + 18 ⇒ 35s + 18 ≡ 2 (mod 3) 35s ≡ −16 (mod 3) but −16≡ 2 (mod 3) ⇒ 35s ≡ 2 (mod 3) so s ≡ 1 (mod 3) ⇒ s = 3t + 1 x = 35(3t + 1) + 18 ⇒ x = 105t + 53 there for x ≡ 53 (mod 105)
$$\mathrm{another}\:\mathrm{method}\:\left(\mathrm{algebraic}\right) \\ $$$$\:{x}\:\equiv\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{5}\right)……\left(\mathrm{i}\right) \\ $$$$\:{x}\:\equiv\:\mathrm{4}\:\left(\mathrm{mod}\:\mathrm{7}\right)\:……\left(\mathrm{ii}\right) \\ $$$$\:{x}\:\equiv\:\mathrm{2}\left(\:\mathrm{mod}\:\mathrm{3}\right)…….\left(\mathrm{iii}\right) \\ $$$$\:\mathrm{from}\:\left(\mathrm{i}\right)\:\:{x}\:=\:\mathrm{5}{k}\:+\:\mathrm{3}\:,\:{k}\:\in\:\mathbb{Z}\:…..\left(\mathrm{i}\right)\:\mathrm{in}\:\left(\mathrm{ii}\right) \\ $$$$\:\:\mathrm{5}{k}\:+\:\mathrm{3}\:\equiv\:\mathrm{4}\:\left(\mathrm{mod}\:\mathrm{7}\right) \\ $$$$\:\:\:\mathrm{5}{k}\:\equiv\:\mathrm{1}\left(\:\mathrm{mod}\:\mathrm{7}\right)\:\mathrm{by}\:\mathrm{trial}\:\mathrm{and}\:\mathrm{error}\:\: \\ $$$$\:\:\:{k}\:\equiv\:\mathrm{3}\:\left(\mathrm{mod}\:\mathrm{7}\right)\:\Rightarrow\:{k}\:=\:\mathrm{7}{s}\:+\:\mathrm{3}\:\:,\:{s}\:\in\mathbb{Z}\:\:\Rightarrow\:{x}\:=\:\mathrm{5}\left(\mathrm{7}{s}\:+\:\mathrm{3}\right)\:+\:\mathrm{3} \\ $$$$\:{x}\:=\:\mathrm{35}{s}\:+\:\mathrm{18} \\ $$$$\:\Rightarrow\:\mathrm{35}{s}\:+\:\mathrm{18}\:\equiv\:\mathrm{2}\:\left(\mathrm{mod}\:\mathrm{3}\right) \\ $$$$\:\:\:\:\:\:\:\mathrm{35}{s}\:\equiv\:−\mathrm{16}\:\left(\mathrm{mod}\:\mathrm{3}\right)\: \\ $$$$\:\:\:\:\:\:\mathrm{but}\:−\mathrm{16}\equiv\:\mathrm{2}\:\left(\mathrm{mod}\:\mathrm{3}\right)\:\Rightarrow\:\:\mathrm{35}{s}\:\equiv\:\mathrm{2}\:\left(\mathrm{mod}\:\mathrm{3}\right)\:\: \\ $$$$\mathrm{so}\:{s}\:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:\mathrm{3}\right)\:\Rightarrow\:{s}\:=\:\mathrm{3}{t}\:+\:\mathrm{1} \\ $$$$\:{x}\:=\:\mathrm{35}\left(\mathrm{3}{t}\:+\:\mathrm{1}\right)\:+\:\mathrm{18}\:\:\:\Rightarrow\:{x}\:=\:\mathrm{105}{t}\:+\:\mathrm{53} \\ $$$$\mathrm{there}\:\mathrm{for}\:{x}\:\equiv\:\mathrm{53}\:\left(\mathrm{mod}\:\mathrm{105}\right) \\ $$$$ \\ $$
Commented by TawaTawa1 last updated on 31/Mar/20
God bless you sir
$$\mathrm{God}\:\mathrm{bless}\:\mathrm{you}\:\mathrm{sir} \\ $$
Commented by Rio Michael last updated on 31/Mar/20
you too sir
$$\mathrm{you}\:\mathrm{too}\:\mathrm{sir} \\ $$
Commented by TawaTawa1 last updated on 31/Mar/20
I am a girl sir
$$\mathrm{I}\:\mathrm{am}\:\mathrm{a}\:\mathrm{girl}\:\mathrm{sir} \\ $$
Commented by Rio Michael last updated on 31/Mar/20
oh welcome madam
$$\mathrm{oh}\:\mathrm{welcome}\:\mathrm{madam} \\ $$
Answered by mind is power last updated on 31/Mar/20
2x=1(5) 2x=1(3) 2x=1(7) ⇒3,5,7∣(2x−1) dince (3,5,7) are coprimes ⇒3.5.7∣2x−1⇒2x−1=0(15.7)=0(105) ⇒2x−1=0(105) ⇒2x=1(105) 2.x.53=53(105)⇒x=53(105)
$$\mathrm{2}{x}=\mathrm{1}\left(\mathrm{5}\right) \\ $$$$\mathrm{2}{x}=\mathrm{1}\left(\mathrm{3}\right) \\ $$$$\mathrm{2}{x}=\mathrm{1}\left(\mathrm{7}\right) \\ $$$$\Rightarrow\mathrm{3},\mathrm{5},\mathrm{7}\mid\left(\mathrm{2}{x}−\mathrm{1}\right) \\ $$$${dince}\:\left(\mathrm{3},\mathrm{5},\mathrm{7}\right)\:{are}\:{coprimes} \\ $$$$\Rightarrow\mathrm{3}.\mathrm{5}.\mathrm{7}\mid\mathrm{2}{x}−\mathrm{1}\Rightarrow\mathrm{2}{x}−\mathrm{1}=\mathrm{0}\left(\mathrm{15}.\mathrm{7}\right)=\mathrm{0}\left(\mathrm{105}\right) \\ $$$$\Rightarrow\mathrm{2}{x}−\mathrm{1}=\mathrm{0}\left(\mathrm{105}\right) \\ $$$$\Rightarrow\mathrm{2}{x}=\mathrm{1}\left(\mathrm{105}\right) \\ $$$$\mathrm{2}.{x}.\mathrm{53}=\mathrm{53}\left(\mathrm{105}\right)\Rightarrow{x}=\mathrm{53}\left(\mathrm{105}\right) \\ $$
Commented by TawaTawa1 last updated on 31/Mar/20
God bless you sir
$$\mathrm{God}\:\mathrm{bless}\:\mathrm{you}\:\mathrm{sir} \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *