## Saturday, July 28, 2012

### Remainders and number theory for grades 6-12

Mr. Canastar had 3 identical decks of cards, and told his class that each contained more than 100 but less than 200 cards. He told Yohan to count the 1st deck by 3's and there were 2 left over. He told Matt to count the 2nd deck by 5's and there were 3 left over. CC counted the 3rd deck by 7's and there were 2 left.

He challenged the rest of the class to figure out how many cards were in each deck. Can you? And explain your method too!

If interested in purchasing my NEW 2012 Math Challenge Problem/Quiz book, Revised Version 1.1, click on BUY NOW at top of right sidebar. 175 problems divided into 35 quizzes with answers at back. There are now detailed solutions, hints and strategies for the first 8 quizzes. Suitable for SAT I, Math I/II Subject Tests, Math Contest practice and Daily/Weekly Problems of the Day. Includes multiple choice, case I/II/III type and constructed response items. Special Limited Price \$7.99. Secured pdf will be emailed when purchase is verified. DON'T FORGET TO SEND ME AN EMAIL (dmarain "at gmail dot com") FIRST SO THAT I CAN SEND THE ATTACHMENT!

Auntie Ann said...

From the 5R3, you know the number has to end in 3 or 8. Because: factors of 5 end in 0 or 5, adding three to that means 3 or 8.

From the 3R2 rule, guess that it ends in 8 (because the number - 2 would give 6, which is divisible by 3.) In order to have the number divisible by 3 with R=2, the hundreds and the tens digit must add up to something divisible by 3: it has to be 128, 158, or 188. All of those follow the 3R2 rule.

Using the 7R2 rule, the only one of those that works is 128.

128 / 3 = 42 R 2
128 / 5 = 25 R 3
128 / 7 = 18 R 2

Check the assumption that it ended in 8 by assuming it ends in 3: That means, in order to follow the 3R2 rule, the (number - 2) would have to equal either 111, 141 or 171. So the number would have to be one of: 113, 143, or 173 to follow the 3R2 and 5R3 rules.

Checking each of those by the 7R2 rule gives: 16R1, 20R3, and 24R3 respectively. None works for the 7R2 rule.

Dave Marain said...

Very nice explanation, Auntie Ann! Are you an educator?

shoover said...

This problem type sounded like something out of Vinogradov's Elements of Number Theory. I went looking for my ancient copy of the book, but was unable to locate it, so I ended up doing something manual and tedious like Auntie Ann's solution.

However, I have since discovered that the relevant pages of the Congruences chapter are visible via Google Books, so off I went today, and I have a more elegant solution.

We are given:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

We can multiply through to put the LCM in the mod side:
35x ≡ 70 (mod 105)
21x ≡ 63 (mod 105)
15x ≡ 30 (mod 105)

Subtract the third congruence from the first, and retain the second congruence:
20x ≡ 40 (mod 105)
21x ≡ 63 (mod 105)

Of these, subtract the first from the second:
x ≡ 23 (mod 105)

Putting into algebraic terms:
x = 105(t) + 23

We are given that 100 < x < 200, so t must be 1, and we have x = 105(1) + 23 = 128.

This book should be suitable for advanced high schoolers; at least, I was working through it at about ages 14-16. I think it might still be available as a Dover Publication.