Difference between revisions of "1964 AHSME Problems/Problem 16"
Talkinaway (talk | contribs) (Created page with "==Problem== Let <math>f(x)=x^2+3x+2</math> and let <math>S</math> be the set of integers <math>\{0, 1, 2, \dots , 25 \}</math>. The number of members <math>s</math> of <math...") |
Talkinaway (talk | contribs) (→Solution) |
||
Line 15: | Line 15: | ||
Proof: | Proof: | ||
− | If <math>f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, then <math>f(x+6) = a_n(x+6)^n + a_{n-1}(x | + | If <math>f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, then <math>f(x+6) = a_n(x+6)^n + a_{n-1}(x+6)^{n-1} +...+ a_0</math>. 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 <math>6^1</math> or higher, since subtracting a multiple of <math>6</math> will not change congruence <math>\pmod 6</math>. This leaves <math>a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, which is <math>f(x)</math>, so <math>f(x+6) \equiv f(x) \pmod 6</math>. |
So, we only need to test when <math>f(x)</math> has a remainder of <math>0</math> for <math>0, 1, 2, 3, 4, 5</math>. The set of numbers <math>6, 7, 8, 9, 10, 11</math> will repeat remainders, as will all other sets. The remainders are <math>2, 0, 0, 2, 0, 0</math>. | So, we only need to test when <math>f(x)</math> has a remainder of <math>0</math> for <math>0, 1, 2, 3, 4, 5</math>. The set of numbers <math>6, 7, 8, 9, 10, 11</math> will repeat remainders, as will all other sets. The remainders are <math>2, 0, 0, 2, 0, 0</math>. |
Latest revision as of 20:31, 23 July 2019
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
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.