Maths Olympiad Prep

Library / HMMT February /859 of 1302

HMMT February

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 zk−1z^{k}-1.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 z≠1z \neq 1 are roots of QQ, which leads to its factorization. Alternatively, we note that (z−1)Q(z)=z11−z9+z7−z4+z2−1=(z4−z2+1)(z7−1)(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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.