If d divides n, then xn-1 is divisible by xd-1. We can always set d = 1, even when n is prime, hence xn-1 is never irreducible. You can adjoin y to create a field extension, but the irreducible polynomial associated with y is a proper factor of xn-1. Let's try to find this irreducible polynomial.
Let ζn(x) be the product of x-yj, for all primitive nth roots of 1. Recall that yj is a primitive nth root iff j is relatively prime to n. Thus there are φ(n) terms in the product, and ζ(x) has degree φ(n).
Don't confuse this function with the Riemann zeta function; they are unrelated.
Apply any automorphism to ζ(x), as a polynomial. The automorphism permutes primitive roots, hence it permutes the factors in the product. We are merely multiplying them in a different order. The result is the same. Thus ζ(x) is fixed by every automorphism. It is fixed by the automorphisms of F/K, which is galois, hence the coefficients of ζ(x) all lie in K. If K is based on the integers, the coefficients are integers. And if K = Zp, the coefficients lie in Zp.
Here is a recursive procedure to build ζn, even if the nth roots are not well characterized.
Let ζ1 = x-1. Then let ζn equal xn-1 divided by ζd for every d < n that divides n.
Instead of a formal proof, I'll illustrate with n = 12. The polynomial xn-1 includes all the roots of 1, primitive and nonprimitive alike. Divide by x-1, ζ1, when d = 1, and take away the root that has order 1. Divide by x+1 and remove the root whose order is precisely 2. Divide by ζ3, x2+x+1, to take away the two roots with order 3. Do the same for the roots of order 4, and 6, and you are left with the four roots having order 12.
This algorithm works over the integers, or Zp. In fact, the former polynomial, with coefficients in Z, can be reduced mod p to produce the latter polynomial.
Here is another formula for ζn that is not recursive, hence it is more efficient. It uses the mobius function, denoted μ(n).
For every d that divides n, raise xn/d-1 to the μ(d) power. Multiply these together to build ζn. Let's ssee why this works.
first let n be prime, so that d is either 1 or n. This gives xn-1 to the 1 power times x-1 to the -1 power, or (xn-1)/(x-1), which is indeed ζn.
Next let n be composite. By induction this formula gives the right answer for all lesser values of n.
Set d = 1 to get the numerator xn-1. Now we need to divide by ζc for every divisor c ≥ 1 and < n.
Focus on a divisor d, and let e = n/d. The factor xe-1 appears in ζj when e divides j properly divides n, having exponent μ(j/e). for instance, if j = 3e then 3 is one of the divisors, and ζj includes xe to the μ(3) power. This happenes whenever e divides j divides n, but we want to exclude j = n, because we don't want to divide by ζn. That's not part of the recursive formula.
Let j run over the multiples of e that are also divisors of n, from e up to n, and take the sum of μ(j/e). But this is the sum of μ(w) for all w dividing n/e, which is known to be 0. Since j was not suppose to include n, the sum is in fact -μ(n/e) = -μ(d). This factor is in the denominator, so the exponent on xe-1 is μ(d), as it should be.
If n is odd, φ(n) = φ(2n). Hence ζn and ζ2n have the same degree. In fact there is a deeper connection.
Let y be a primitive root of ζn. Adjoining this polynomial also brings in -y, which is a primitive root of order 2n. You get the 2n roots for free.
Think of ζn as the product of x-yj, over the primitive nth roots of 1. Replace each yj with -yj to find the primitive roots of order 2n. This builds ζ[2n]. The lead coefficient of the product is still 1. The next coefficient, the sum of the roots, has been negated. The next coefficient, the sum of the pairwise products of the roots, is unchanged. The next coefficient is negated, and so on down the line.
Let's illustrate with 5 and 10. Since 5 is prime, ζ5 = x4+x3+x2+x+1. Using the mobius formula, we have:
ζ[10] =
(x10-1) × (x-1) / (x5-1) / (x2-1) =
(x5+1) / (x+1) =
x4-x3+x2-x+1
At first it appears that all the cyclotomic coefficients are 0 or ±1. Derive the first 20 or so and you'll see what I mean. But don't try to prove it, because it's not true. The smallest counterexample is n = 105.
Our carefully crafted cyclotomic polynomial ζ need not be irreducible. Consider the 8th roots of 1 over Z3. The cyclotomic polynomial has degree φ(8) = 4, but a 2 dimensional extension of Z3 produces the finite field of order 9, which includes all 8 roots of 1. Here is the factorization of ζ8.
x4+1 = (x2+x+2) × (x2+2x+2)
Note that either quadratic on the right can be used to bring in the 8 roots of 1. In either case the field is isomorphic to the unique field of order 9.