Skip to main content

2017 AMC 12A Problem 21

Problem 21 of 25HarderAlgebraNumber TheoryProblem-Solving Techniques

A set SS is constructed as follows. To begin, S={0,10}.S=\{0,10\}. Repeatedly, as long as possible, if xx is an integer root of some polynomial anxn+an−1xn−1a_nx^n+a_{n-1}x^{n-1} +⋯+a1x+a0+\cdots+a_1x+a_0 for some n≥1,n\ge1, all of whose coefficients aia_i are elements of S,S, then xx is put into S.S. When no more elements can be added to S,S, how many elements does SS have?

Answer choices

Show solution

Solution

Using 10x+10,10x+10, the root −1-1 enters S.S. Then 11 enters as a root of −x10−x9−⋯−x+10,-x^{10}-x^9-\cdots-x+10, and −10-10 enters from x+10.x+10. Now x3+x−10x^3+x-10 has root 2,2, and x+2x+2 gives −2;-2; then 2x−102x-10 and 2x+102x+10 give ±5.\pm5. At this point S={0,±1,±2,±5,±10}.S=\{0,\pm1,\pm2,\pm5,\pm10\}. No further integer can appear. Inductively, every nonzero member of SS divides 10.10. If a polynomial used in the rule has constant term 0,0, factor out the largest possible power of x;x; any nonzero root is then a root of a polynomial whose constant term is the first nonzero original coefficient. The Rational Root Theorem shows that the root divides this coefficient, which by the inductive hypothesis divides 10.10. So SS has 99 elements. Thus, the correct answer is D.
AoPS wiki

Tagged: polynomial · divisibility · systematic listing

More practice