Roots of Unity Factoring

Notice that if we let $x = 10$ , then the number can be written as the polynomial $x^8 + x^7 + x^4 + x + 1$

Assuming that $\omega$ is any of the fifth roots of unity (in other words, $\omega^5 = 1$ ), then $\omega^8 + \omega^7 + \omega^4 + \omega + 1 = \omega^4 + \omega^3 + \omega^2 + \omega + 1 = 0$

In this way, we see that $(x-\omega_1)(x-\omega_2)(x-\omega_3)(x-\omega_4)(x-\omega_5) = x^4 + x^3 + x^2 + x + 1$ must divide $x^8 + x^7 + x^4 + x + 1$ .

Plugging $x = 10$ back into these polynomials and dividing, we get that $\frac{110010011}{11111} = \boxed{9901}$