Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME I 2012 Problems/Problem 4"

(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 (...")
 
m (see also box)
 
Line 12: Line 12:
  
 
Note that <math>b_4 \equiv 166 \mod 1000</math>, so <math>b_5 \equiv 3\cdot 166^2+2\cdot 166+1 \equiv 1 \mod 1000</math>, since <math>3\cdot 166^2 + 2\cdot 166 = 166\cdot (3\cdot 166+2) = 166 \cdot (1000)</math>. Therefore we have that <math>b_5 \equiv 1 \mod 1000</math>, so our answer is <math>\boxed{001}</math>.
 
Note that <math>b_4 \equiv 166 \mod 1000</math>, so <math>b_5 \equiv 3\cdot 166^2+2\cdot 166+1 \equiv 1 \mod 1000</math>, since <math>3\cdot 166^2 + 2\cdot 166 = 166\cdot (3\cdot 166+2) = 166 \cdot (1000)</math>. Therefore we have that <math>b_5 \equiv 1 \mod 1000</math>, so our answer is <math>\boxed{001}</math>.
 +
 +
==See Also==
 +
*[[Mock AIME I 2012 Problems/Problem 5| Next Problem]]
 +
*[[Mock AIME I 2012 Problems/Problem 3| Previous Problem]]
 +
*[[Mock AIME I 2012 Problems]]

Latest revision as of 09:56, 11 March 2025

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

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_4&oldid=244733"