How to find a nth primitive root of unity over $\mathbb{Z}_2$?

Question

For instance, one can find 15th roots of unity by letting $f(x) := x^{15}-1 = (x + 1)(x^2 + x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1)$. Then roots of $f(x)$ are roots of its factors. e.g. When $\omega$ is a root of $(x^2 + x + 1)$, it is a root of $f(x)$. But how would one go further around with finding a "primitive" root?

Answer 1

First Approach

The roots of unity live on a unit circle and are equally spaced. If you let

$$ x = exp \left(i\theta\right)$$

Then you are greatly simplifying the problem, as you are only considering solutions on the unit circle. As a result:

$$ \exp \left(in\theta\right) - 1 = \exp \left(in\theta\right) - \exp\left( {2\pi ik} \right) $$

Now they are only roots when $\theta = {2 \pi k \over n}$. Which indicates that the roots are spread evenly around the unit circle.

Note $\exp\left(2\pi i k \right) = \cos(2\pi k) + i \sin(2\pi k) = 1$ always equals 1, since sin is zero for all multiples of $2\pi$.

Hope that helps.

Alternative Approach

Since $f(x) = x^{15} -1$, it is easy to show that $f(\bar x ) = f(x)$. This means that all roots must occur in conjugate pairs. As a result, the roots of unity must occur in pairs. If you expand these pairs, you always get quadratic terms.

n is odd

If n is odd, then we must have a factorisation:

$$x^n - 1 = (x-1)(x-\alpha_1)(x-\bar\alpha_1)...$$

n is even

If n is even, then we have two known roots:

$$x^n - 1 = (x-1)(x+1)(x-\alpha_1)(x-\bar\alpha_1)...$$

Hopefully that helps :)