Maths Olympiad Prep

Library / /14 of 71

Number theory Difficulty 4.7 AIME Find the answer United States

Problem:
Let NN be the number of distinct roots of k=12012(xk1)\prod_{k=1}^{2012}\left(x^{k}-1\right). Give lower and upper bounds LL and UU on NN. If 0<LNU0<L \leq N \leq U, then your score will be 23(U/L)1.7\left\lfloor\frac{23}{(U / L)^{1.7}}\right\rfloor. Otherwise, your score will be 0.

Solution

Solution:
For xx to be such a number is equivalent to xx being a kthk^{\text{th}} root of unity for some kk up to 20122012. For each kk, there are φ(k)\varphi(k) primitive kthk^{\text{th}} roots of unity, so the total number of roots is k=12012φ(k)\sum_{k=1}^{2012} \varphi(k).

We will give a good approximation of this number using well known facts about the Möbius function, defined by μ(n)={0 if n is not squarefree (1)r if n has r distinct prime factors \mu(n)=\left\{\begin{array}{ll}0 & \text{ if } n \text{ is not squarefree } \\ (-1)^{r} & \text{ if } n \text{ has } r \text{ distinct prime factors }\end{array}\right.. It turns out that if f(n)=dng(d)f(n)=\sum_{d \mid n} g(d), then g(n)=dnμ(d)f(nd)g(n)=\sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right). Using this fact, since n=dnφ(d)n=\sum_{d \mid n} \varphi(d), we have that φ(n)=dnμ(d)nd\varphi(n)=\sum_{d \mid n} \mu(d) \frac{n}{d}. Now we have reduced the problem to estimating k=12012dkμ(d)kd\sum_{k=1}^{2012} \sum_{d \mid k} \mu(d) \frac{k}{d}. Let a=kda=\frac{k}{d}, so we obtain k=12012dkaμ(d)\sum_{k=1}^{2012} \sum_{d \mid k} a \mu(d).

We can interchange the order of summation by writing
d=12012a=12012daμ(d)d=12012μ(d)12(2012d)2d=12012μ(d)201222d2=201222d=12012μ(d)d2201222d=1μ(d)d2 \begin{aligned} \sum_{d=1}^{2012} \sum_{a=1}^{\left\lfloor\frac{2012}{d}\right\rfloor} a \mu(d) & \approx \sum_{d=1}^{2012} \mu(d) \frac{1}{2}\left(\left\lfloor\frac{2012}{d}\right\rfloor\right)^{2} \\ & \approx \sum_{d=1}^{2012} \mu(d) \frac{2012^{2}}{2 d^{2}} \\ & =\frac{2012^{2}}{2} \sum_{d=1}^{2012} \frac{\mu(d)}{d^{2}} \\ & \approx \frac{2012^{2}}{2} \sum_{d=1}^{\infty} \frac{\mu(d)}{d^{2}} \end{aligned}
The Möbius function also satisfies the property that dnμ(d)={1 if n=10 otherwise \sum_{d \mid n} \mu(d)=\left\{\begin{array}{ll}1 & \text{ if } n=1 \\ 0 & \text{ otherwise }\end{array}\right., which can be seen as a special case of the theorem above (letting f(n)=1,g(n)={1 if n=10 otherwise f(n)=1, g(n)=\left\{\begin{array}{ll}1 & \text{ if } n=1 \\ 0 & \text{ otherwise }\end{array}\right. ). We can then see that (d=1μ(d)d2)(c=11c2)=112=1\left(\sum_{d=1}^{\infty} \frac{\mu(d)}{d^{2}}\right)\left(\sum_{c=1}^{\infty} \frac{1}{c^{2}}\right)=\frac{1}{1^{2}}=1, so d=1μ(d)d2=6π2\sum_{d=1}^{\infty} \frac{\mu(d)}{d^{2}}=\frac{6}{\pi^{2}}. Therefore, we have k=12012φ(k)3π220122=\sum_{k=1}^{2012} \varphi(k) \approx \frac{3}{\pi^{2}} \cdot 2012^{2}= 1230488.266... 2012 is large enough that all of our approximations are pretty accurate and we should be comfortable perturbing this estimate by a small factor to give bounding values.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.