Question and Answers Forum

All Questions      Topic List

Others Questions

Previous in All Question      Next in All Question      

Previous in Others      Next in Others      

Question Number 66832 by Rio Michael last updated on 20/Aug/19

solve the system of congruence {: ((x≡ 1 (mod 5))),((x ≡ 2 (mod 7))),((x≡ 3(mod 9))),((x ≡ 4( mod 11))) }

$${solve}\:{the}\:{system}\:{of}\:{congruence} \\ $$$$\:\:\:\left.\begin{matrix}{{x}\equiv\:\mathrm{1}\:\left({mod}\:\mathrm{5}\right)}\\{{x}\:\equiv\:\mathrm{2}\:\left({mod}\:\mathrm{7}\right)}\\{{x}\equiv\:\:\mathrm{3}\left({mod}\:\mathrm{9}\right)}\\{{x}\:\equiv\:\mathrm{4}\left(\:{mod}\:\mathrm{11}\right)}\end{matrix}\right\} \\ $$

Answered by mr W last updated on 26/Aug/19

x=5h+1 ...(1) x=7i+2 ...(2) x=9j+3 ...(3) x=11k+4 ...(4) x=11k+4=(11k+1)+3=^(!) 9j+3 ⇒11k+1=9j ⇒9j−11k=1 ⇒j=11m+5 ^(∗∗)) ⇒k=9m+4 x=9(11m+5)+3=(99m+46)+2=^(!) 7i+2 ⇒99m+46=7i ⇒7i−99m=46 ⇒i=99l+49 ^(∗∗)) ⇒m=7l+3 x=7(99l+49)+2=(693l+344)+1=^(!) 5h+1 ⇒693l+344=5h ⇒5h−693l=344 ⇒h=693n+346 ^(∗∗)) ⇒l=5n+2 x=5(693n+346)+1=3465n+1731 ⇒general solution is x=3465n+1731 with n=0,1,2,3,....

$${x}=\mathrm{5}{h}+\mathrm{1}\:\:\:\:...\left(\mathrm{1}\right) \\ $$$${x}=\mathrm{7}{i}+\mathrm{2}\:\:\:...\left(\mathrm{2}\right) \\ $$$${x}=\mathrm{9}{j}+\mathrm{3}\:\:\:...\left(\mathrm{3}\right) \\ $$$${x}=\mathrm{11}{k}+\mathrm{4}\:\:\:...\left(\mathrm{4}\right) \\ $$$$ \\ $$$${x}=\mathrm{11}{k}+\mathrm{4}=\left(\mathrm{11}{k}+\mathrm{1}\right)+\mathrm{3}\overset{!} {=}\mathrm{9}{j}+\mathrm{3} \\ $$$$\Rightarrow\mathrm{11}{k}+\mathrm{1}=\mathrm{9}{j} \\ $$$$\Rightarrow\mathrm{9}\boldsymbol{{j}}−\mathrm{11}\boldsymbol{{k}}=\mathrm{1} \\ $$$$\Rightarrow{j}=\mathrm{11}{m}+\mathrm{5}\:\:\:\:^{\left.\ast\ast\right)} \\ $$$$\Rightarrow{k}=\mathrm{9}{m}+\mathrm{4} \\ $$$$ \\ $$$${x}=\mathrm{9}\left(\mathrm{11}{m}+\mathrm{5}\right)+\mathrm{3}=\left(\mathrm{99}{m}+\mathrm{46}\right)+\mathrm{2}\overset{!} {=}\mathrm{7}{i}+\mathrm{2} \\ $$$$\Rightarrow\mathrm{99}{m}+\mathrm{46}=\mathrm{7}{i} \\ $$$$\Rightarrow\mathrm{7}\boldsymbol{{i}}−\mathrm{99}\boldsymbol{{m}}=\mathrm{46} \\ $$$$\Rightarrow{i}=\mathrm{99}{l}+\mathrm{49}\:\:\:\:^{\left.\ast\ast\right)} \\ $$$$\Rightarrow{m}=\mathrm{7}{l}+\mathrm{3} \\ $$$$ \\ $$$${x}=\mathrm{7}\left(\mathrm{99}{l}+\mathrm{49}\right)+\mathrm{2}=\left(\mathrm{693}{l}+\mathrm{344}\right)+\mathrm{1}\overset{!} {=}\mathrm{5}{h}+\mathrm{1} \\ $$$$\Rightarrow\mathrm{693}{l}+\mathrm{344}=\mathrm{5}{h} \\ $$$$\Rightarrow\mathrm{5}\boldsymbol{{h}}−\mathrm{693}\boldsymbol{{l}}=\mathrm{344} \\ $$$$\Rightarrow{h}=\mathrm{693}{n}+\mathrm{346}\:\:\:\:^{\left.\ast\ast\right)} \\ $$$$\Rightarrow{l}=\mathrm{5}{n}+\mathrm{2} \\ $$$$ \\ $$$${x}=\mathrm{5}\left(\mathrm{693}{n}+\mathrm{346}\right)+\mathrm{1}=\mathrm{3465}{n}+\mathrm{1731} \\ $$$$ \\ $$$$\Rightarrow{general}\:{solution}\:{is} \\ $$$$\boldsymbol{{x}}=\mathrm{3465}\boldsymbol{{n}}+\mathrm{1731}\:{with}\:{n}=\mathrm{0},\mathrm{1},\mathrm{2},\mathrm{3},.... \\ $$

Commented by mr W last updated on 21/Aug/19

are there any easier and more direct ways to solve? to understand ^(∗∗)) in my solution see also my explanation in Q19198.

$${are}\:{there}\:{any}\:{easier}\:{and}\:{more}\:{direct} \\ $$$${ways}\:{to}\:{solve}? \\ $$$$ \\ $$$${to}\:{understand}\:\:^{\left.\ast\ast\right)} \:{in}\:{my}\:{solution} \\ $$$${see}\:{also}\:{my}\:{explanation}\:{in}\:{Q}\mathrm{19198}. \\ $$

Commented by Rio Michael last updated on 21/Aug/19

okay sir l′ll check but thanks for this

$${okay}\:{sir}\:{l}'{ll}\:{check}\:{but}\:{thanks}\:{for}\:{this} \\ $$

Commented by Rasheed.Sindhi last updated on 22/Aug/19

Sir mr W, I think it can be solved by ′Chinese remainder theorm′,but unfortinuately at the moment I′ve forgotten it.

$${Sir}\:{mr}\:{W},\:{I}\:{think}\:{it}\:{can}\:{be}\:{solved} \\ $$$${by}\:'{Chinese}\:{remainder}\:{theorm}',{but} \\ $$$${unfortinuately}\:{at}\:{the}\:{moment}\:{I}'{ve}\:{forgotten}\:{it}. \\ $$

Commented by Prithwish sen last updated on 22/Aug/19

By chinese remainder theorem ∵ 5,7,9,11 are pairwise prime let m = 5.7.9.11 = 3465 ∴ M_1 =(m/5) = 693, M_2 = (m/7) = 495, M_3 = (m/9) = 385 M_4 =(m/(11)) = 315 gcd(693,5)=1 ⇒693u+5v=1⇒u=2 v=−277 ∴693x≡1(mod5)has unique soln. x≡2(mod5) gcd(495,7)=1⇒495u+7v=1⇒u=3 v=−212 ∴495x≡1(mod7)has unique soln. x≡3(mod7) gcd(385,9)=1⇒385u+9v=1⇒u=4 v=−171 ∴385x≡1(mod9)has unique soln.x≡4(mod9) gcd(315,11)=1⇒315u+11v=1⇒u=−3 v=86 ∴315x≡1(mod11)has unique soln.x≡−3(mod11) i.e x≡8(mod11) ∴ x_0 = 1.(693.2)+2.(495.3)+3.(385.4)+4.(315.8) = 19056 ∴ The soln. is x ≡ 19056 (mod 3465) i.e x ≡ 1731 (mod 3465)

$$\mathrm{By}\:\mathrm{chinese}\:\mathrm{remainder}\:\mathrm{theorem} \\ $$$$\because\:\mathrm{5},\mathrm{7},\mathrm{9},\mathrm{11}\:\mathrm{are}\:\mathrm{pairwise}\:\mathrm{prime} \\ $$$$\mathrm{let}\:\mathrm{m}\:=\:\mathrm{5}.\mathrm{7}.\mathrm{9}.\mathrm{11}\:=\:\mathrm{3465} \\ $$$$\therefore\:\mathrm{M}_{\mathrm{1}} =\frac{\mathrm{m}}{\mathrm{5}}\:=\:\mathrm{693},\:\mathrm{M}_{\mathrm{2}} =\:\frac{\mathrm{m}}{\mathrm{7}}\:=\:\mathrm{495},\:\mathrm{M}_{\mathrm{3}} \:=\:\frac{\mathrm{m}}{\mathrm{9}}\:=\:\mathrm{385} \\ $$$$\mathrm{M}_{\mathrm{4}} =\frac{\mathrm{m}}{\mathrm{11}}\:=\:\mathrm{315} \\ $$$$\mathrm{gcd}\left(\mathrm{693},\mathrm{5}\right)=\mathrm{1}\:\Rightarrow\mathrm{693u}+\mathrm{5v}=\mathrm{1}\Rightarrow\mathrm{u}=\mathrm{2}\:\mathrm{v}=−\mathrm{277} \\ $$$$\therefore\mathrm{693x}\equiv\mathrm{1}\left(\mathrm{mod5}\right)\mathrm{has}\:\mathrm{unique}\:\mathrm{soln}.\:\mathrm{x}\equiv\mathrm{2}\left(\mathrm{mod5}\right) \\ $$$$\mathrm{gcd}\left(\mathrm{495},\mathrm{7}\right)=\mathrm{1}\Rightarrow\mathrm{495u}+\mathrm{7v}=\mathrm{1}\Rightarrow\mathrm{u}=\mathrm{3}\:\mathrm{v}=−\mathrm{212} \\ $$$$\therefore\mathrm{495x}\equiv\mathrm{1}\left(\mathrm{mod7}\right)\mathrm{has}\:\mathrm{unique}\:\mathrm{soln}.\:\mathrm{x}\equiv\mathrm{3}\left(\mathrm{mod7}\right) \\ $$$$\mathrm{gcd}\left(\mathrm{385},\mathrm{9}\right)=\mathrm{1}\Rightarrow\mathrm{385u}+\mathrm{9v}=\mathrm{1}\Rightarrow\mathrm{u}=\mathrm{4}\:\mathrm{v}=−\mathrm{171} \\ $$$$\therefore\mathrm{385x}\equiv\mathrm{1}\left(\mathrm{mod9}\right)\mathrm{has}\:\mathrm{unique}\:\mathrm{soln}.\mathrm{x}\equiv\mathrm{4}\left(\mathrm{mod9}\right) \\ $$$$\mathrm{gcd}\left(\mathrm{315},\mathrm{11}\right)=\mathrm{1}\Rightarrow\mathrm{315u}+\mathrm{11v}=\mathrm{1}\Rightarrow\mathrm{u}=−\mathrm{3}\:\mathrm{v}=\mathrm{86} \\ $$$$\therefore\mathrm{315x}\equiv\mathrm{1}\left(\mathrm{mod11}\right)\mathrm{has}\:\mathrm{unique}\:\mathrm{soln}.\mathrm{x}\equiv−\mathrm{3}\left(\mathrm{mod11}\right) \\ $$$$\mathrm{i}.\mathrm{e}\:\mathrm{x}\equiv\mathrm{8}\left(\mathrm{mod11}\right) \\ $$$$\therefore\:\boldsymbol{\mathrm{x}}_{\mathrm{0}} =\:\mathrm{1}.\left(\mathrm{693}.\mathrm{2}\right)+\mathrm{2}.\left(\mathrm{495}.\mathrm{3}\right)+\mathrm{3}.\left(\mathrm{385}.\mathrm{4}\right)+\mathrm{4}.\left(\mathrm{315}.\mathrm{8}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:=\:\mathrm{19056} \\ $$$$\therefore\:\boldsymbol{\mathrm{T}}\mathrm{he}\:\mathrm{soln}.\:\mathrm{is}\:\boldsymbol{\mathrm{x}}\:\equiv\:\mathrm{19056}\:\left(\boldsymbol{\mathrm{mod}}\:\mathrm{3465}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{i}}.\boldsymbol{\mathrm{e}}\:\boldsymbol{\mathrm{x}}\:\equiv\:\mathrm{1731}\:\left(\boldsymbol{\mathrm{mod}}\:\mathrm{3465}\right) \\ $$

Commented by mr W last updated on 22/Aug/19

thank you for your effort sir!

$${thank}\:{you}\:{for}\:{your}\:{effort}\:{sir}! \\ $$

Commented by Prithwish sen last updated on 23/Aug/19

you are welcome sir.

$$\mathrm{you}\:\mathrm{are}\:\mathrm{welcome}\:\mathrm{sir}. \\ $$

Commented by Rio Michael last updated on 25/Aug/19

thanks alot you all, i really want to learn this part of mathematics, how do i go about it? please help me.

$${thanks}\:{alot}\:{you}\:{all},\:{i}\:{really}\:{want}\:{to}\:{learn}\:{this}\:{part}\:{of}\:{mathematics},\:{how}\:{do}\:{i}\:{go} \\ $$$${about}\:{it}?\:{please}\:{help}\:{me}. \\ $$

Commented by mr W last updated on 25/Aug/19

at first please try not to write endless long rows in your posts sir. usually i ignore posts if i must scroll horizontally when i read them. back to your question, if you want to learn “chinese remainder” method, i can not help you. please refer to Wikipedia for more details. if you want to learn about my method, try to understand how to solve ax+by=c as i explained in question No 19198.

$${at}\:{first}\:{please}\:{try}\:{not}\:{to}\:{write} \\ $$$${endless}\:{long}\:{rows}\:{in}\:{your}\:{posts}\:{sir}. \\ $$$${usually}\:{i}\:{ignore}\:{posts}\:{if}\:{i}\:{must} \\ $$$${scroll}\:{horizontally}\:{when}\:{i}\:{read} \\ $$$${them}. \\ $$$${back}\:{to}\:{your}\:{question},\:{if}\:{you}\:{want} \\ $$$${to}\:{learn}\:``{chinese}\:{remainder}''\:{method}, \\ $$$${i}\:{can}\:{not}\:{help}\:{you}.\:{please}\:{refer}\:{to} \\ $$$${Wikipedia}\:{for}\:{more}\:{details}.\:{if} \\ $$$${you}\:{want}\:{to}\:{learn}\:{about}\:{my}\:{method}, \\ $$$${try}\:{to}\:{understand}\:\:{how}\:{to}\:{solve} \\ $$$${ax}+{by}={c}\:{as}\:{i}\:{explained}\:{in}\:{question} \\ $$$${No}\:\mathrm{19198}. \\ $$

Commented by Rio Michael last updated on 29/Aug/19

yes i know how to solve linear diophantine equations

$${yes}\:{i}\:{know}\:{how}\:{to}\:{solve}\:{linear}\:{diophantine}\:{equations}\: \\ $$

Commented by Rio Michael last updated on 29/Aug/19

i′ll visit wikipedia

$${i}'{ll}\:{visit}\:{wikipedia} \\ $$

Answered by Rasheed.Sindhi last updated on 22/Aug/19

An Arithmetic Way {: ((x≡ 1 (mod 5) ...(i))),((x ≡ 2 (mod 7)....(ii))),((x≡ 3(mod 9).....(iii))),((x ≡ 4( mod 11)...(iv))) } (i)⇒x=6,11,16,21,... Each number can be obtained by adding 5 in previous. We can see that 16 is also solution of (ii)(....mod 7) Any other such number(which is common solution to (i) & (ii)) will be 35 (lcm of 5 &7) greater than 16... 16,51,86,121,156,... 156 is also solution of (iii) (...mod 9) So next such solution is 315( lcm(5,7,9) ) greater than 156 156,471,786,1101,1416,1731 1731 is also solution of (iv)(....mod 11) Next such number is greater by any multiple of lcm(5,7,9,11)=3465. 1731,5196,8661,...

$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathbb{A}\mathrm{n}\:\mathbb{A}\mathrm{rithmetic}\:\mathbb{W}\mathrm{ay} \\ $$$$\:\:\:\left.\begin{matrix}{{x}\equiv\:\mathrm{1}\:\left({mod}\:\mathrm{5}\right)\:...\left({i}\right)}\\{{x}\:\equiv\:\mathrm{2}\:\left({mod}\:\mathrm{7}\right)....\left({ii}\right)}\\{{x}\equiv\:\:\mathrm{3}\left({mod}\:\mathrm{9}\right).....\left({iii}\right)}\\{{x}\:\equiv\:\mathrm{4}\left(\:{mod}\:\mathrm{11}\right)...\left({iv}\right)}\end{matrix}\right\}\: \\ $$$$\left({i}\right)\Rightarrow{x}=\mathrm{6},\mathrm{11},\mathrm{16},\mathrm{21},... \\ $$$${Each}\:{number}\:{can}\:{be}\:{obtained}\:{by}\: \\ $$$${adding}\:\mathrm{5}\:{in}\:{previous}. \\ $$$${We}\:{can}\:{see}\:{that}\:\mathrm{16}\:{is}\:{also}\:{solution}\:{of} \\ $$$$\left({ii}\right)\left(....{mod}\:\mathrm{7}\right)\: \\ $$$${Any}\:{other}\:{such}\:{number}\left({which}\:{is}\:{common}\right. \\ $$$$\left.{solution}\:{to}\:\left({i}\right)\:\&\:\left({ii}\right)\right)\:{will}\:{be}\:\mathrm{35}\:\left({lcm}\:{of}\right. \\ $$$$\left.\mathrm{5}\:\&\mathrm{7}\right)\:\:{greater}\:{than}\:\mathrm{16}... \\ $$$$\mathrm{16},\mathrm{51},\mathrm{86},\mathrm{121},\mathrm{156},... \\ $$$$\mathrm{156}\:{is}\:{also}\:{solution}\:{of}\:\left({iii}\right)\:\left(...{mod}\:\mathrm{9}\right) \\ $$$${So}\:{next}\:{such}\:{solution}\:{is}\:\mathrm{315}\left(\:{lcm}\left(\mathrm{5},\mathrm{7},\mathrm{9}\right)\:\right) \\ $$$${greater}\:{than}\:\mathrm{156} \\ $$$$\mathrm{156},\mathrm{471},\mathrm{786},\mathrm{1101},\mathrm{1416},\mathrm{1731} \\ $$$$\mathrm{1731}\:{is}\:{also}\:{solution}\:{of}\:\left({iv}\right)\left(....{mod}\:\mathrm{11}\right) \\ $$$${Next}\:{such}\:{number}\:{is}\:{greater}\:{by}\:{any} \\ $$$${multiple}\:{of}\:{lcm}\left(\mathrm{5},\mathrm{7},\mathrm{9},\mathrm{11}\right)=\mathrm{3465}. \\ $$$$\mathrm{1731},\mathrm{5196},\mathrm{8661},... \\ $$

Commented by Rasheed.Sindhi last updated on 22/Aug/19

Sir mr W I had solved the above problem in that way sometime ago(At that time I didn′t know chinese remainder theorm.)The above method didn′t use algebra..and it′s my own method.

$${Sir}\:{mr}\:{W}\: \\ $$$$\:\:{I}\:{had}\:{solved}\:{the}\:{above}\:{problem}\:{in}\: \\ $$$${that}\:{way}\:{sometime}\:{ago}\left({At}\:{that}\:{time}\:{I}\:{didn}'{t}\:{know}\right. \\ $$$$\left.{chinese}\:{remainder}\:{theorm}.\right){The}\:{above} \\ $$$${method}\:{didn}'{t}\:{use}\:{algebra}..{and}\:{it}'{s} \\ $$$${my}\:{own}\:{method}. \\ $$

Commented by mr W last updated on 22/Aug/19

Sir Rasheed, thank you very much for this new way! i appreciate it!

$${Sir}\:{Rasheed},\: \\ $$$${thank}\:{you}\:{very}\:{much}\:{for}\:{this}\:{new} \\ $$$${way}!\:{i}\:{appreciate}\:{it}! \\ $$

Commented by Rasheed.Sindhi last updated on 22/Aug/19

Thanks A Lot Sir!

$$\mathbb{T}\mathrm{han}\Bbbk\mathrm{s}\:\mathbb{A}\:\mathbb{L}\mathrm{ot}\:\mathbb{S}\mathrm{ir}! \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com