## Sunday, March 11, 2007

### Da Roots. Topic: Algebra/Complex Numbers Level: AIME.

Problem: (2007 Mock AIME 6 - #7) Let $P_n(x) = 1+x+x^2+\cdots+x^n$ and $Q_n(x) = P_1 \cdot P_2 \cdots P_n$ for all integers $n \ge 1$. How many more distinct complex roots does $Q_{1004}$ have than $Q_{1003}$?

Solution: Well, $P_n(x)$ is familiar. Rewrite as

$P_n(x) = \frac{x^{n+1}-1}{x-1}$,

i.e. the $(n+1)-$th roots of unity except $1$. Since $Q_{1004}$ just contains a $P_{1004}$ term that $Q_{1003}$ doesn't have, we only need to think about that term in relation to the previous ones. So we want to find out how many of the $1004+1 = 1005$th roots of unity are not $k$-th roots of unity for any $k < 1005$. Well, recalling that any $k$-th root of unity can be written as

$e^{2 \pi i \frac{p}{k}} = \cos{\left(2 \pi \frac{p}{k}\right)}+i \sin{\left(2 \pi \frac{p}{k}\right)}$

for $p = 0, 1, \ldots, k-1$, it remains to find the number of $p$ such that $\frac{p}{1005}$ does not reduce. But this, of course, is simply $\phi(1005) = 1005\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{67}\right) = 2 \cdot 4 \cdot 66 = 528$. QED.

--------------------

Comment: Definitely one of my favorite problems on the test because it has a really nice and clean solution once you see it. And it wasn't too difficult to see either; combining a little knowledge of roots of unity with a little knowledge of the $\phi$ function made it a good problem. Furthermore, it offers the nice generalization that

$Q_n$ has $\phi(n+1)$ more distinct roots than $Q_{n-1}$.

--------------------

Practice Problem: (2007 Mock AIME 6 - #8) A sequence of positive reals is defined by $a_0 = x$, $a_1 = y$, and $a_n \cdot a_{n+2} = a_{n+1}$ for all integers $n \ge 0$. Given that $a_{2007}+a_{2008} = 3$ and $a_{2007} \cdot a_{2008} = \frac{1}{3}$, find $x^3+y^3$.

#### 1 comment:

1. The solution's immediate with cyclotomic polynomials =D