Maths Olympiad Prep

Library / /698 of 841

Number theory Difficulty 5.4 AIME, harder Find the answer

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 Land and Uon on N.If. If 0<L N\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. Fractions can be typed as 3/2, and spacing doesn't matter.

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 φ(k)\varphi(k)primitive primitive k\text{k} {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 μ(n)=\mu(n)={0 if n is not squarefree (1)r if n has r distinct prime factors. \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..Itturnsoutthatif. It turns out that if f(n)=df(n)=\sum_{d \mid} n} g(d),then, then g(n)=dg(n)=\sum_{d \mid} n} μ(d)f(nd)\mu(d) f\left(\frac{n}{d}\right).Usingthisfact,since. Using this fact, since n=dn=\sum_{d \mid} n} φ(d)\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 k=12012d\sum_{k=1}^{2012} \sum_{d \mid} k} μ(d)kd\mu(d) \frac{k}{d}.Let. Let a=kda=\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 d\sum_{d \mid} n} μ(d)=\mu(d)={1 if n=10 otherwise \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 \left\{\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 d=1μ(d)d2=6π2\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 reproduced verbatim; metadata (topic, difficulty) added by this project.