CYclotomic polynomials

LaTeX4Web 1.4 OUTPUT In section "Angles in circle" we could see that somehow we can relate primitive roots and generators to roots of unity by also representing them in the unit circle. Roots of unity are any complex number that if we raise it to a positive integer n it is equal to 1. So roots of unity are any a that satisfies za = 1. The following picture illustrates the 7th roots of unity:
LaTeX4Web 1.4 OUTPUT You can observe that they are distributed forming a regular heptagon, and therefore the angle of every root of unity is a multiple of 2 p / 7. This is explained with Euler¢s formula eix = cos(x) + isin(x). We can also define the primitive roots of unity, which are any a such that za = 1 and is not a kth root of unity for any k < n. However, note that the primitive roots of unity are the generators! Which means that they are the numbers coprime to n. For example, the following picture illustrates the primitive roots of 12 (the ones that are circled). Among the 12th roots of unity, only 4 are primitive, because f(12)=4. As you can see in the circle, they are 1, 5, 7 and 11, which are the numbers smaller than 12 that are coprime to 12.
LaTeX4Web 1.4 OUTPUT Then a question arises: if for each integer n there is a polynomial, namely xn -1, whose roots are the roots of unity of n, is it possible to find a polynomial whose roots are the generators of n? The answer is yes and they are called cyclotomic polynomials. Hence, the roots of the nth cyclotomic polynomial are the numbers coprime to n. The cyclotomic polynomials are found recursively by applying the following property and using the fact that F1(x) = x-1:
Õd|n Fd(x) = xn - 1.
This way we can find the first cyclotomic polynomials:
F_2(x) = x2 -1/ F_1(x) = x2 -1 / x-1 = x+1
F_3(x) = x3 -1/ F_1(x) = x3 -1/x-1 = x2 +x+1
F_4(x) = x4 -1/ F_1(x) F_2(x) = x4 -1/x2 -1 = x2 +1
LaTeX4Web 1.4 OUTPUT Hence, we realize that to compute the nth cyclotomic polynomial we need to find all the divisors of n and the cyclotomic polynomial of each divisor. For this reason it is not fast to compute cyclotomic polynomials. However, we observe that there are three cases in which the nth cyclotomic polynomial can be computed directly without recursion:
1. If n is a prime, then Fp(x) = 1 + x + ·s + xp-2 + xp-1 since this is the result of dividing xp -1 by x-1.
2. If n is of the form 2p, then F2p(x) = 1 - x + x2 - ... + xp-1 .
3. If n is of the form pk , then Fpk (x) = 1 + x +... + xn-2p + xn-p .
Now we want to analyze if there is any relationship between cyclotomic polynomials and primitive roots. The answer is again yes, and by using the aforementioned property of cyclotomic polynomials we see that if we evaluate the primitive roots of n in Ff(n)(x) modulo n the result will be zero. For instance, we know that 2 is a primitive root of 5. Then, f(5) = 4 and the 4th cyclotomic polynomial is x2 + 1. By substituting x by 2 in this polynomial modulo 5 we obtain 0:
F_4(2) = 22 + 1 = 5 º 0 mod 5.
LaTeX4Web 1.4 OUTPUT Therefore, we conclude that another way of finding the primitive roots of n is by computing Ff(n)(x), evaluate x from 2 to n-1 modulo n and see for which integers this is equal to 0. However, as we have seen, finding a cyclotomic polynomial recursively is quite long, so we conclude that this method is only effective if f(n) is of the form 2p or pk , because then we can find the cyclotomic polynomial instantly.