How many integers between 200 and 500 inclusive leave a remainder 1 when divided by 7 and a remainder 3 when divided by 4?

Question

Find the smallest positive integer that leaves a remainder 5 when divided by 7, a remainder 6 when divided by 11, and a remainder 4 when divided by 13.

christian · Accepted Answer

446 divided by 11

Reiny · Answer

list multiples of 7 plus 1 past 200 :
204 211 218 225 232 239 246..

list multiples of 4 plus 3 past 200
203 207 211 215 219 223 227 231 235 239 AHHHH

239 is the smallest
this will happen again in 28 (multiply the 2 remainders)
so 239 267 295 323 ... 491
number of terms ??
consider it an arithmetic sequence where a = 239, d - 28 and n = ?
t(n) = a+(n-1)d
491 = 239 + (n-1)(28)
252 = 28n - 28
280 = 28n
n = 10

remainder of 5 when divided by 7 ---- 5 mod 7
remainder of 6 when divided by 11 --- 6 mod 11
remainder of 4 when divided by 13 --- 4 mod 13

we could do the same thing:
12 19 26 33 40 47 54 61 68 75 82 89 96 103 110 117 124 131 138 ...
6 17 28 39 50 61 72 83 94 105 116 127 138 149...
4 17 30 43 56 69 82 95 108 121 134 147...

mmmhh?

Let's try something completely different:
"The Chinese Remainder Theorem"
Google it to get several examples, there is a good Youtube

Z = 5 mod 7
Z = 6 mod 11
Z = 4 mod 13

X = 5b1 c1 + 6 b2 c2 + 4b3 c3
to get b's, multiply the mods
7x11x13 = 1001
b1 = 1001/7 = 143
b2 = 1001/11 = 91
b3 = 1001/13 = 77

sofar we have
X = 5(143) c1 + 6(91)c2 + 4(77)c3

now the tricky part
143(c1) = 1 mod 7
3c1 = 1 mod 7
3c1 = 8mod7
-4c1 = 8 mod 7
c1 = -2

91c2 = 1 mod 11
3c2 = 1mod11
3c2 = 12 mod 11
c2 = 4

77c3 = 1 mod 13
12 c3 = 1 mod 13
12c3 = -12 mod 13
c3 = -1

so X = 5(143)(-2) + 6(91)(4) + 4(77)(-1)
= 446 mod 1001

so the smallest such number is 446

check: 446/7 = 63 remainder 5
446/11 = 40 remainder 6
446/13 = 34 remainder 4

How about that, we could have gone for quite a bit using the simple method of just listing.