Menu Close

solve-the-system-of-congruence-x-1-mod-5-x-2-mod-7-x-3-mod-9-x-4-mod-11-

Tinku Tara 0 Comments
Pin




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}! \\ $$

Pin

Leave a Reply

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