Chinese Remainder Theorem
Number Theory
Level
4
What is the sum 3 smallest positive integer such that when divided by 7 give remainder 3, divided by 11 give remainder 5, and divided by 13 give remainder 7.
The answer is 4272.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Note = equal to congruent,,
1)X = 3 Mod 7 or 7k + 3 2)X = 5 Mod 11 or 11l + 5 3)X = 7 Mod 13 or 13m + 7 With equation 1 and 2 7k + 3 = 5 Mod 11 7k = 2 Mod 11 k = 5 Mod 11 or 11n +5 7(11n + 5 ) +3 = 77n + 38 .....(4) With equation 4 and 3 77n + 38 = 7 Mod 13 77n = -31 Mod 13 -n = 8 Mod 13 n = 5 Mod 13 or 13p +5 77(13p +5) +38 = 1001p + 423 So X = 1001p + 423 Sum 3 smallest X ,,Is sum if P = 0,1,and 2 = 423 + 1424 + 2425 = 4272 So the answer is ( 4272 )