1964 AHSME Problems/Problem 16
Contents
[hide]Problem
Let and let be the set of integers . The number of members of such that has remainder zero when divided by is:
Solution
Note that for all polynomials , .
Proof: If , then . In the second equation, we can use the binomial expansion to expand every term, and then subtract off all terms that have a factor of or higher, since subtracting a multiple of will not change congruence . This leaves , which is , so .
So, we only need to test when has a remainder of for . The set of numbers will repeat remainders, as will all other sets. The remainders are .
This means for , is divisible by . Since is divisible, so is for , which is values of that work. Since is divisible, so is for , which is more values of that work. The values of will also generate solutions each, just like . This is a total of values of , for an answer of
Solution 2
- We know that,
= + + is congruent modulo 6 that implies or/and is congruent modulo .The numbers are of the form and for some integer and due to restrictions of number of elements in the set we get the inequality .Then we calculate the possible combinations to get as answer i.e. option .
THE above solution does not give you the answer there are more cases, = + + is congruent to modulo 6 this has 4 cases, When,
- ≡ (mod 6)
- ≡ (mod 6)
- ≡ (mod 6), ≡ (mod 6)
- ≡ (mod 6), then ≡ (mod 6), which satisfies.
Therefore by solvin' these cases we get 17.
See Also
1964 AHSC (Problems • Answer Key • Resources) | ||
Preceded by Problem 15 |
Followed by Problem 17 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 | ||
All AHSME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.