1964 AHSME Problems/Problem 16

Problem

Let $f(x)=x^2+3x+2$ and let $S$ be the set of integers $\{0, 1, 2, \dots , 25 \}$ . The number of members $s$ of $S$ such that $f(s)$ has remainder zero when divided by $6$ is:

$\textbf{(A)}\ 25\qquad \textbf{(B)}\ 22\qquad \textbf{(C)}\ 21\qquad \textbf{(D)}\ 18 \qquad \textbf{(E)}\ 17$

Solution $1$

Note that for all polynomials $f(x)$ , $f(x + 6) \equiv f(x) \pmod 6$ .

Proof: If $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ , then $f(x+6) = a_n(x+6)^n + a_{n-1}(x+6)^{n-1} +...+ a_0$ . 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 $6^1$ or higher, since subtracting a multiple of $6$ will not change congruence $\pmod 6$ . This leaves $a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ , which is $f(x)$ , so $f(x+6) \equiv f(x) \pmod 6$ .

So, we only need to test when $f(x)$ has a remainder of $0$ for $0, 1, 2, 3, 4, 5$ . The set of numbers $6, 7, 8, 9, 10, 11$ will repeat remainders, as will all other sets. The remainders are $2, 0, 0, 2, 0, 0$ .

This means for $s=1, 2, 4, 5$ , $f(s)$ is divisible by $6$ . Since $f(1)$ is divisible, so is $f(s)$ for $s=7, 13, 19, 25$ , which is $5$ values of $s$ that work. Since $f(2)$ is divisible, so is $f(s)$ for $s=8, 14, 20$ , which is $4$ more values of $s$ that work. The values of $s=4, 5$ will also generate $4$ solutions each, just like $f(2)$ . This is a total of $17$ values of $s$ , for an answer of $\boxed{\textbf{(E)}}$

Solution 2

We have $f($ x $)$ = $x$ ^ $2$ + $3$ $x$ + $2$ and $S$ = { $0$ , $1$ , $2$ ,... , $25$ }.We need equiv $f$ ( $s$ )=0 mod 6 $. That implies we need numbers of the form 6$ k $+$ 5 $and 6$ k $+$ 4 $also due to restriction on number of elements of set we need$ k $<= 3 . Calculate the number of possibble combinations to get$ 17 $as answer.$ Ans.$$ (Error compiling LaTeX. Unknown error_msg)\boxed{\textbf{(E)}}$.

Solution by$ (Error compiling LaTeX. Unknown error_msg)GEOMETRY-WIZARD$.

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.

Page

Toolbox

Search

1964 AHSME Problems/Problem 16

Contents

Problem

Solution $1$

Solution 2

See Also