2024 AIME II Problems/Problem 13

Problem

Let $\omega\neq 1$ be a 13th root of unity. Find the remainder when $\prod_{k=0}^{12}(2-2\omega^k+\omega^{2k})$ is divided by 1000.

Solution 1

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

Now, we consider the polynomial $x^{13} - 1$ whose roots are the 13th roots of unity. Taking our rewritten product from $0$ to $12$ , we see that both instances of $\omega^k$ cycle through each of the 13th roots. Then, our answer is: