Find-the-least-positive-integer-that-leaves-a-remainder-3-when-divided-by-7-4-when-divided-by-9-and-8-when-divided-by-11-

Question Number 133897 by bemath last updated on 25/Feb/21

Find the least positive integer

that leaves a remainder 3 when divided by 7

, 4 when divided by 9, and 8 when

divided by 11 .

Answered by john_santu last updated on 25/Feb/21

b y U s e C h i n e s e R e m a i n d e r t h e o r e m

\begin{array}{cccc} i & n_{i} & N_{i} & y_{i} N_{i} \equiv 1 m o d n_{1} & c_{i} & N_{i} y_{i} c_{i} \\ 1 & 7 & 9.11 & y_{1} . 9.11 \equiv 1 m o d 7 \to y_{1} = 1 & 3 & 297 \\ 2 & 9 & 7.11 & y_{2} . 7.11 \equiv 1 m o d 9 \to y_{2} = 2 & 4 & 616 \\ 3 & 11 & 7.9 & y_{3} . 7.9 \equiv 1 m o d 11 \to y_{3} = 7 & 8 & 3528 \end{array}

X = \sum_{i} N_{i} y_{i} c_{i} = 4441

w e h a v e x \equiv X m o d N \Rightarrow x \equiv 4441 (m o d 693)

x \equiv 283 (m o d 693) o r x = 693 k + 283; k \in Z

t h e n t h e l e a s t p o s i t i v e i n t e g e r i s x = 283

Commented by talminator2856791 last updated on 25/Feb/21

why is it called chinese remainder theorem ?

Answered by talminator2856791 last updated on 25/Feb/21

7 a + 3 = 9 b + 4 = 11 c + 8

7 a = 9 b + 1

b = 7 k - 4

9 b + 4 = 11 c + 8

9 b = 11 c + 4

c = 9 j - 2

9 (7 k - 4) = 11 (9 j - 2) + 4

63 k - 36 = 99 j - 18

63 k = 99 j + 18

7 k = 11 j + 2

j = 7 d - 4

9 (7 k - 4) = 11 (9 (3) - 2) + 4

63 k - 36 = 279

63 k = 315

k = 5

b = 7 k - 4

b = 31

9 b + 4 = 9 (31) + 4

= 283