Maths Olympiad Prep

Library / /710 of 860

Number theory Difficulty 5.4 AIME, harder Find the answer

Let NN be the number of distinct roots of \prod_{k=1}^{2012}\left(x^{k}-1\right).Givelowerandupperbounds. Give lower and upper bounds Land and Uon on N.If. If 0<L \leq N \leq U,thenyourscorewillbe[23(U/L)1.7, then your score will be \left[\frac{23}{(U / L)^{1.7}}\right\rfloor. Otherwise, your score will be 0 .

A number or a short expression. Spacing and $ signs are ignored.

Solution

For xx to be such a number is equivalent to xx being an kth k^{\text {th }} root of unity for some kk up to 2012. For each kk, there are \varphi(k)primitive primitive k^{\text {th }}rootsofunity,sothetotalnumberofrootsisk=12012φ(k) roots of unity, so the total number of roots is \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 \mu(n)=\left\{0 if n is not squarefree (1)r if n has r distinct prime factors. \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..Itturnsoutthatif. It turns out that if f(n)=\sum_{d \mid n} g(d),then, then g(n)=\sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right).Usingthisfact,since. Using this fact, since n=\sum_{d \mid n} \varphi(d),wehavethatφ(n)=dnμ(d)nd, we have that \varphi(n)=\sum_{d \mid n} \mu(d) \frac{n}{d}. Now we have reduced the problem to estimating \sum_{k=1}^{2012} \sum_{d \mid k} \mu(d) \frac{k}{d}.Let. Let a=\frac{k}{d},soweobtaink=12012dkaμ(d), so we obtain \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 \sum_{d \mid n} \mu(d)=\left\{1 if n=10 otherwise \begin{array}{ll}1 & \text { if } n=1 \\ 0 & \text { otherwise }\end{array}\right.,whichcanbeseenasaspecialcaseofthetheoremabove(letting, which can be seen as a special case of the theorem above (letting f(n)=1, g(n)=\left\{1 if n=10 otherwise \begin{array}{ll}1 & \text { if } n=1 \\ 0 & \text { otherwise }\end{array}\right.).Wecanthenseethat(d=1μ(d)d2)(c=11c2)=112=1 ). We can then see that \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 \sum_{d=1}^{\infty} \frac{\mu(d)}{d^{2}}=\frac{6}{\pi^{2}}.Therefore,wehavek=12012φ(k)3π220122=. Therefore, we have \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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.