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(xk−1)\prod_{k=1}^{2012}\left(x^{k}-1\right). Give lower and upper bounds LL and UU on NN. If 0<L≤N≤U0<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)=∑d∣ng(d)f(n)=\sum_{d \mid n} g(d), then g(n)=∑d∣nμ(d)f(nd)g(n)=\sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right). Using this fact, since n=∑d∣nφ(d)n=\sum_{d \mid n} \varphi(d), we have that φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d \mid n} \mu(d) \frac{n}{d}. Now we have reduced the problem to estimating ∑k=12012∑d∣kμ(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=12012∑d∣kaμ(d)\sum_{k=1}^{2012} \sum_{d \mid k} a \mu(d).

We can interchange the order of summation by writing
∑d=12012∑a=1⌊2012d⌋aμ(d)≈∑d=12012μ(d)12(⌊2012d⌋)2≈∑d=12012μ(d)201222d2=201222∑d=12012μ(d)d2≈201222∑d=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 ∑d∣nμ(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=1∞1c2)=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π2⋅20122=\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.