Friday

April 18, 2014

April 18, 2014

Posted by **Jimmy** on Friday, October 19, 2012 at 8:52pm.

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.

- Math -
**Reiny**, Saturday, October 20, 2012 at 12:24amlist 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.

**Related Questions**

Math - How many integers bewteen 200 and 500 inclusive leave a remainder 1 when ...

math - How many (distinct) numbers between 0 and 1 (inclusive) can be expressed ...

Math - How many Positive integers are between 200-500 that are divisible by the ...

Math - How many Positive integers are between 200-500 that are divisible by the ...

Math - The sum of the integers from 40 to 60, inclusive, is 1050. what is the ...

Math - The sum of the integers from 40 to 60, inclusive, is 1050. what is the ...

math - list the integers between -5 and 2, inclusive.

math - set S contains all integers from 100 to 200, inclusive. if x is a number ...

discrete math - Find how many positive integers with exactly four decimal digits...

Math ( Number Theory ) - How many numbers from 1 to 1000 inclusive can be ...