Menu Close

use-the-Chinese-Remainder-theorem-to-find-x-such-that-x-2-mod-3-2x-3-mod-5-3x-4-mod-7-




Question Number 86240 by Rio Michael last updated on 27/Mar/20
use the Chinese Remainder theorem to find    x such that   x ≡ 2(mod 3)  2x ≡ 3(mod 5)   3x≡ 4( mod 7)
$$\mathrm{use}\:\mathrm{the}\:\mathrm{Chinese}\:\mathrm{Remainder}\:\mathrm{theorem}\:\mathrm{to}\:\mathrm{find} \\ $$$$\:\:{x}\:\mathrm{such}\:\mathrm{that} \\ $$$$\:{x}\:\equiv\:\mathrm{2}\left(\mathrm{mod}\:\mathrm{3}\right) \\ $$$$\mathrm{2}{x}\:\equiv\:\mathrm{3}\left(\mathrm{mod}\:\mathrm{5}\right) \\ $$$$\:\mathrm{3}{x}\equiv\:\mathrm{4}\left(\:\mathrm{mod}\:\mathrm{7}\right) \\ $$
Answered by mr W last updated on 28/Mar/20
x=3k+2  2x=6k+4=5h+3⇒5h−6k=1   ...(i)  3x=9k+6=7j+4⇒7j−9k=2   ...(ii)  (i):  k=5n−1, h=6n−1  (ii):  k=7m−1, j=9m−1  5n−1=7m−1 ⇒5n−7m=0   ...(iii)  (iii):  n=7p, m=5p  ⇒k=5n−1=35p−1  ⇒x=3k+2=105p−1=104, 209, 314, ...
$${x}=\mathrm{3}{k}+\mathrm{2} \\ $$$$\mathrm{2}{x}=\mathrm{6}{k}+\mathrm{4}=\mathrm{5}{h}+\mathrm{3}\Rightarrow\mathrm{5}{h}−\mathrm{6}{k}=\mathrm{1}\:\:\:…\left({i}\right) \\ $$$$\mathrm{3}{x}=\mathrm{9}{k}+\mathrm{6}=\mathrm{7}{j}+\mathrm{4}\Rightarrow\mathrm{7}{j}−\mathrm{9}{k}=\mathrm{2}\:\:\:…\left({ii}\right) \\ $$$$\left({i}\right): \\ $$$${k}=\mathrm{5}{n}−\mathrm{1},\:{h}=\mathrm{6}{n}−\mathrm{1} \\ $$$$\left({ii}\right): \\ $$$${k}=\mathrm{7}{m}−\mathrm{1},\:{j}=\mathrm{9}{m}−\mathrm{1} \\ $$$$\mathrm{5}{n}−\mathrm{1}=\mathrm{7}{m}−\mathrm{1}\:\Rightarrow\mathrm{5}{n}−\mathrm{7}{m}=\mathrm{0}\:\:\:…\left({iii}\right) \\ $$$$\left({iii}\right): \\ $$$${n}=\mathrm{7}{p},\:{m}=\mathrm{5}{p} \\ $$$$\Rightarrow{k}=\mathrm{5}{n}−\mathrm{1}=\mathrm{35}{p}−\mathrm{1} \\ $$$$\Rightarrow{x}=\mathrm{3}{k}+\mathrm{2}=\mathrm{105}{p}−\mathrm{1}=\mathrm{104},\:\mathrm{209},\:\mathrm{314},\:… \\ $$

Leave a Reply

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