information:extraction, linguistic:voice_change
Roots of unity

Every nonzero element of a finite field is a root of unity, as x = 1 for every nonzero element of GF(q).

If n is a positive integer, an n th primitive root of unity is a solution of the equation x = 1 that is not a solution of the equation x = 1 for any positive integer m < n. If a is a n th primitive root of unity in a field F, then F contains all the n roots of unity, which are 1, a, a,..., a.

The field GF(q) contains a n th primitive root of unity if and only if n is a divisor of q − 1; if n is a divisor of q − 1, then the number of primitive n th roots of unity in GF(q) is φ (n) (Euler's totient function). The number of n th roots of unity in GF(q) is gcd(n, q − 1).

In a field of characteristic p, every (np) th root of unity is also a n th root of unity. It follows that primitive (np) th roots of unity never exist in a field of characteristic p.

On the other hand, if n is coprime to p, the roots of the n th cyclotomic polynomial are distinct in every field of characteristic p, as this polynomial is a divisor of X − 1, whose discriminant n is nonzero modulo p. It follows that the n th cyclotomic polynomial factors over GF(p) into distinct irreducible polynomials that have all the same degree, say d, and that GF(p) is the smallest field of characteristic p that contains the n th primitive roots of unity.