Primitive Roots of Unity
Primitive roots of unity are roots of unity whose multiplicative order is They are the roots of the cyclotomic polynomial, and are central in many branches of number theory, especially algebraic number theory.
Definition
Let be a positive integer. A primitive root of unity is an root of unity that is not a root of unity for any positive That is, is a primitive root of unity if and only if
There are four roots of unity given by Two of these, namely are primitive. The other two are not: and
Basic Properties
The primitive roots of unity are the complex numbers
There are primitive roots of unity, where is Euler's totient function.
Let Recall that the roots of unity are the distinct powers So it remains to show that is primitive if and only if and are coprime.
The key fact is that is a primitive root of unity, since its first powers are distinct. A standard order argument shows that if and only if since writing gives but this is impossible unless
If then it is easy to check that so if then is not primitive. In fact, it is not hard to show that is a primitive root of unity.
If and then but and are coprime so This shows that is a primitive root of unity, because the first positive power of that equals is
Euler's totient function counts the number of positive integers that are coprime to which are precisely the exponents that produce primitive roots of unity, so this is the number of primitive th roots of unity.
Classify the roots of unity by their multiplicative order.
Let Then the powers of are classified according to the GCD of the exponent and as in the above proof, is a root of unity.
are primitive roots of unity. Note
are primitive roots of unity.
are primitive roots of unity.
are primitive roots of unity.
is a primitive root of unity.
is a primitive root of unity.
Note that the orders are the divisors of There are primitive roots of order for each Since this accounts for all of the roots of unity.
The above arguments show that the powers of a primitive root of unity enumerate all the primitive roots of unity, for all the divisors of
Let be a primitive root of unity, and
let be a primitive root of unity.
Then is a primitive root of unity for some positive integer
What can we say about in general?
Clarification: In the answer choices, and denote the greatest common divisor function and the lowest common multiple function, respectively.
Sum and Product
The product of the primitive roots of unity is unless This is because the set of primitive roots of unity, can be partitioned into pairs which multiply to give For this fails because and coincide.
The sum of the primitive roots of unity is where is the Möbius function; see that wiki for a proof.
In fact, there is an elegant formula for the sum of the powers of the primitive roots of unity:
The sum of the powers of the primitive roots of unity is
where
The extremal examples of the theorem are when and when
When taking powers permutes the primitive roots of unity, so the sum should still be Indeed, so
When the powers are all so the sum is In this case so as desired.
Here is an outline: the sum is a sum of primitive roots of unity, and it runs over all of them. But there are repetitions: the sum has terms and there are primitive roots of unity, so they are each counted times. The sum of the primitive roots of unity is so the result follows.
Group Structure
The roots of unity form a cyclic group under multiplication, generated by This group is isomorphic to the additive group of the integers mod under the isomorphism In this context, the primitive roots of unity correspond via this isomorphism to the other generators of the group. This is the set of multiplicative units which has elements
The roots of unity are isomorphic to The primitive roots of unity, and correspond to the elements in respectively. These are the elements which generate additively. E.g. the multiples of are
Every element in is on that list.
Cyclotomic Polynomials
The polynomial is a polynomial in known as the th cyclotomic polynomial. It is of great interest in algebraic number theory. For more details and properties, see the wiki on cyclotomic polynomials.