Mock AIME I 2012 Problems/Problem 4

Revision as of 17:33, 7 April 2012 by Esque (talk | contribs) (Created page with "==Problem== Consider the polynomial <math>p(x)=3x^2+2x+1</math>. Let <math>p^n (x) = p(p^{n-1}(x))</math> and <math>p^1 (x) = p(x)</math>. The product of the roots of <math>p^5 (...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


Consider the polynomial $p(x)=3x^2+2x+1$. Let $p^n (x) = p(p^{n-1}(x))$ and $p^1 (x) = p(x)$. The product of the roots of $p^5 (x)$ can be expressed in the form $\dfrac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find the remainder when $m$ is divided by $1000$.


Let $a_n$ be the leading coefficient of $p^n(x)$ and let $b_n$ be the constant coefficient of $p^n(x)$. Therefore, we would like to find $\frac{b_n}{a_n}$ in reduced form.

It is easy to see that we have the following recursive relations: $a_n = 3a_{n-1}^2, b_n = 3b_{n-1}^2+2b_{n-1}+1$.

Notice that $a_1 = 3, b_1 = 1$. It is quickly deduced that $a_5 = 3^{31}$. Now let us evaluate $b_n$.

Notice that $b_2 = 6, b_3 = 121, b_4 = 44166$ from some computations. Note that $3|b_4$. Therefore $b_5 = 3b_4^2+2b_4 + 1 \equiv 1 \mod 3$, so $\gcd(b_5, a_5) =  \gcd\left(b_5, 3^{31}\right)= 1$. So then it suffices to evaluate $b_5 \mod 1000$.

Note that $b_4 \equiv 166 \mod 1000$, so $b_5 \equiv 3\cdot 166^2+2\cdot 166+1 \equiv 1 \mod 1000$, since $3\cdot 166^2 + 2\cdot 166 = 166\cdot (3\cdot 166+2) = 166 \cdot (1000)$. Therefore we have that $b_5 \equiv 1 \mod 1000$, so our answer is $\boxed{001}$.

Invalid username
Login to AoPS