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 \equiv 2 (\mod 3)

2 x \equiv 3 (\mod 5)

3 x \equiv 4 (\mod 7)

Answered by mr W last updated on 28/Mar/20

x = 3 k + 2

2 x = 6 k + 4 = 5 h + 3 \Rightarrow 5 h - 6 k = 1 \dots (i)

3 x = 9 k + 6 = 7 j + 4 \Rightarrow 7 j - 9 k = 2 \dots (i i)

(i) :

k = 5 n - 1, h = 6 n - 1

(i i) :

k = 7 m - 1, j = 9 m - 1

5 n - 1 = 7 m - 1 \Rightarrow 5 n - 7 m = 0 \dots (i i i)

(i i i) :

n = 7 p, m = 5 p

\Rightarrow k = 5 n - 1 = 35 p - 1

\Rightarrow x = 3 k + 2 = 105 p - 1 = 104, 209, 314, \dots

Facebook Tweet Pin