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 and Answers Forum

All Questions Topic List
Number Theory Questions
Previous in All Question Next in All Question
Previous in Number Theory Next in Number Theory
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$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum