Maths Olympiad Prep

Library / /709 of 860

Algebra Difficulty 5.4 AIME, harder Find the answer

Find the smallest positive integer kk such that z10+z9+z6+z5+z4+z+1z^{10}+z^{9}+z^{6}+z^{5}+z^{4}+z+1 divides zk1z^{k}-1.

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

Solution

Let Q(z)Q(z) denote the polynomial divisor. We need that the roots of QQ are kk-th roots of unity. With this in mind, we might observe that solutions to z7=1z^{7}=1 and z1z \neq 1 are roots of QQ, which leads to its factorization. Alternatively, we note that (z1)Q(z)=z11z9+z7z4+z21=(z4z2+1)(z71)(z-1) Q(z)=z^{11}-z^{9}+z^{7}-z^{4}+z^{2}-1=\left(z^{4}-z^{2}+1\right)\left(z^{7}-1\right) Solving for the roots of the first factor, z2=1+i32=±cisπ/3z^{2}=\frac{1+i \sqrt{3}}{2}= \pm \operatorname{cis} \pi / 3 (we use the notation cis(x)=cos(x)+isin(x))\operatorname{cis}(x)=\cos (x)+i \sin (x)) so that z=±cis(±π/6)z= \pm \operatorname{cis}( \pm \pi / 6). These are primitive 12 -th roots of unity. The other roots of Q(z)Q(z) are the primitive 7 -th roots of unity (we introduced z=1z=1 by multiplication.) It follows that the answer is lcm[12,7]=84\operatorname{lcm}[12,7]=84.

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.