2024 AIME II Problem 13

Question

Let

\omega \neq 1

be a

13

th root of unity. Find the remainder when

\prod_{k=0}^{12} \left(2 - 2\omega^k + \omega^{2k}\right)

is divided by

1000.

Answer

Factor

2 - 2x + x^2

= (x - (1+\mathrm{i}))(x - (1-\mathrm{i})),

and use

\prod_k (x - \omega^k) = x^{13} - 1

over all

13

th roots of unity

(1+\mathrm{i})^2 = 2\mathrm{i}

makes

(1+\mathrm{i})^{13}

easy to compute; the whole product becomes

\left(1 - (1+\mathrm{i})^{13}\right)\left(1 - (1-\mathrm{i})^{13}\right)

Since

2 - 2x + x^2 = (x - 1)^2 + 1

= (x - (1+\mathrm{i}))(x - (1-\mathrm{i})),

each factor of the product splits, and as

k

runs from

0

to

12,

\omega^k

runs over all

13

th roots of unity. Because

\prod_k (x - \omega^k) = x^{13} - 1,

for any

\alpha

we get

\prod_k (\omega^k - \alpha) = (-1)^{13}(\alpha^{13} - 1)

= 1 - \alpha^{13}.

Hence the product equals

\left(1 - (1+\mathrm{i})^{13}\right)\left(1 - (1-\mathrm{i})^{13}\right).

Since

(1+\mathrm{i})^2 = 2\mathrm{i},

we get

(1+\mathrm{i})^{13} = (1+\mathrm{i})(2\mathrm{i})^6

= -64(1 + \mathrm{i}) = -64 - 64\mathrm{i},

and by conjugation

(1-\mathrm{i})^{13} = -64 + 64\mathrm{i}.

So the product is

\begin{gathered} (65 + 64\mathrm{i})(65 - 64\mathrm{i}) \\ = 65^2 + 64^2 = 4225 + 4096 \\ = 8321, \end{gathered}

whose remainder upon division by

1000

is

321.

Problem 13 in other years