Mock AIME I 2012 Problems/Problem 4

Problem

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$ .

Solution

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}$ .

Page

Toolbox

Search

Mock AIME I 2012 Problems/Problem 4

Problem

Solution

See Also