Let u and v be angles such that 0 ≤ u ≤ v ≤ 90°. Let w = v-u. Let p be the point on the unit circle that marks the angle u, and let q mark the angle v. Draw segments from the origin to p and q, defining a slice of pie with angle w. Then draw a line segment from p to q, the chord that cuts the crust off the slice of pie.
Let the chord pq be the hypotenuse of a right triangle that is aligned with the axes. In other words, the sides of the triangle run parallel to the x and y axes. Thus the corner of the triangle, t, has the x coordinate of q and the y coordinate of p, also known as cos(v),sin(u). The lengths of the sides of the right triangle are cos(u)-cos(v) and sin(v)-sin(u). Compute the square of the length of the hypotenuse using the pythagorean theorem. After some algebra and trig simplification you should get:
2 - 2cos(u)cos(v) - 2sin(u)sin(v)
[ radii from origin to p and q, angles u and v, with angle w between the two radii, chord from p to q, point t at the corner of the right triangle tpq ]
Now build another right triangle. Draw segment from q perpendicular to the radius from 0 to p. Let these perpendicular segments meet at the point s. Now spq forms another right triangle, with pq as hypotenuse. The altitude of this triangle has length sin(w), while the base is 1-cos(w). Apply the pythagorean theorem again to get the square of the hypotenuse.
2 - 2cos(w)
Set this equal to the earlier expression to obtain the angle subtraction formula:
cos(v-u) = cos(u)cos(v) + sin(u)sin(v)
[ radii from origin to p and q, angles u and v, with angle w between the two radii, chord from p to q, point s along the first radius and at the corner of the right triangle spq ]
This is great, but u and v are rather constrained. Let v stray past 90°. Its cosine becomes negative, but cos(u)-cos(v) is still correct for the length of the base of the first triangle, the distance from t to p.
As v-u exceeds 90°, s slides back along its radius and through the origin, and winds up behind the origin. The cosine of w goes negative, yet 1-cos(w) is still the length of the base of the second right triangle, the distance from s to p.
Eventually q is lower than p. The first right triangle points down, rather than up, and t is actually outside the circle. Now sin(v)-sin(u) is the opposite of the length of the altitude, but the length is squared in the pythagorean formula, so this doesn't matter.
When v passes 180°, its sine is negative, yet sin(v)-sin(u) still gives the length of the altitude of the first triangle, at least in absolute value. Our formula holds for any u between 0° and 90°, and any v between u and u+180°.
When v goes beyond u+180°, reflect the picture through the line x = y. This reproduces the earlier case, where our formula holds. The reflection swaps sine and cosine for u and v, which changes the right side of the equation not at all. It also replaces w with 360°-w, which changes its cosine not at all. Thus the formula holds for all v between u and u+360°, which is all v.
If u is an angle in the second quadrant, subtract 90° from u and v, leaving w unchanged. Now u is in the first quadrant and the formula works. This rotation moves sine to cosine and cosine to -sine, for both u and v. This changes the formula not at all. Perform a similar rotation when u is in the third or fourth quadrant. Therefore the angle subtraction formula works for all angles u and v.
Replace v with -v to get the angle addition formula:
cos(u+v) = cos(u)cos(v) - sin(u)sin(v)
In the above formula, hold u fixed and let v be a variable. Take the derivative with respect to v. This gives the angle addition for sines.
sin(u+v) = cos(u)sin(v) + sin(u)cos(v)
Replace v with -v to get the angle subtraction formula for sines.
sin(u-v) = sin(u)cos(v) - cos(u)sin(v)
There is a tangent addition formula. It's easiest to start with the answers, given below, and work backwards. Replace each tangent with sine over cosine and simplify. I'll leave the details to you.
tan(u+v) = (tan(u) + tan(v)) / (1 - tan(u)tan(v))
tan(u-v) = (tan(u) - tan(v)) / (1 + tan(u)tan(v))
Set u = v in the angle addition formulas to get the double angle formulas.
sin(2u) = 2sin(u)cos(u)
cos(2u) = cos2(u) - sin2(u)
The latter is sometimes written:
cos(2u) = 2×cos2(u) - 1
cos(2u) = 1 - 2×sin2(u)
There is of course a triple angle formula. Expand sin(2u+u) using the angle addition formula, then expand cos(2u) and sin(2u) using the double angle formulas. Do this again to get the quadruple angle formula, the quintuple angle formula, and so on.
sin(3u) = 3sin(u)cos2(u) - sin3(u)
cos(3u) = cos3(u) - 3cos(u)sin2(u)
sin(4u) = 4sin(u)cos3(u) - 4sin3(u)cos(u)
cos(4u) = cos4(u) - 6cos2(u)sin2(u) + sin4(u)
If you are familiar with the binomial theorem, you will recognize a pattern. Let c and s represent cosine and sine respectively, and expand (c+s)n. Take every other term starting with cn; this is the cosine of nu. Well almost; you have to negate every other term in this series. To find the sine of nu, Take every other term in the expansion, starting with ncn-1s, and again, negate every other term in this series.
Look at our last example, sine and cosine of 4u. Expand (c+s)4 and put the minus signs where they belong. The cosine is every other term starting with c4, and the sine is every other term starting with 4c3s.
c4 + 4c3s - 6c2s2 - 4cs3 + s4
Prove the formula, in general, by induction on n. Apply the angle addition formula to u + nu. Imagine cosine and sine of nu written together, as above. It looks like the nth row of Pascal's triangle, except some of the entries have been negated. Now move on to the next level.
The sine is s times the previous formula for cosine plus c times the previous formula for sine. This adds adjacent terms from the previous row, in pairs, giving every other entry in the next row of Pascal's triangle. Similarly, the cosine is c times the previous formula for cosine minus s times the previous formula for sine. This fills in the rest of the row, and all the minus signs are where they belong. By induction, the formula holds for all n.
Of course there is a much simpler proof based on complex exponentiation. Write enθi = eθi to the n, then expand the right side by the binomial theorem. Since eθi = c+si, Equate real and imaginary terms, and you're done.
The double angle formula asserts:
cos(2θ) = 2cos2(θ) - 1
cos(2θ) = 1 - 2sin2(θ)
Reverse these to derive the half angle formulas.
cos(½θ) = sqrt(½(1+cos(θ)))
sin(½θ) = sqrt(½(1-cos(θ)))
Notice that sine squared + cosine squared is still 1, as required.
Let's try 15°, which is half of 30°, which has a cosine of sqrt(3)/2. After some algebra,
cos(15°) = sqrt(2+sqrt(3))/2 = 0.9659
sin(15°) = sqrt(2-sqrt(3))/2 = 0.2588
In this case we could have derived the sine and cosine via angle subtraction. That is, cos(45°-30°) = sqrt(1/2) × (1/2+sqrt(3)/2). Oddly enough, this different looking formula produces the exact same number.
As an exercise, use the half angle formula to show the tangent of 22.5° is sqrt(2)-1.
When multiplying two complex numbers, z1×z2, it is sometimes convenient to convert to polar coordinates. Multiplication is then implemented by adding angles and multiplying radii. This is Demoivre's formula.
[ Two vectors u and v into the first quadrant, v further around and longer than u, then u×v in the second quadrant, longer than u or v, and angle the sum of the other two angles ]
Assume z1 = a1+b1i = r1,θ1, and z2 = a2+b2i = r2,θ2.
The new radius is r1r2, and the new angle is θ1+θ2. Convert the product back to rectangular coordinates as follows.
x ← r1r2×cos(θ1+θ2)
y ← r1r2×sin(θ1+θ2)
Expand using the angle addition formulas. Replace r1cos(θ1) and r1sin(θ1) with a1 and b1, and similarly for a2 and b2, and get x = a1a2 - b1b2 and y = a1b2 + a2b1. This is the formula for multiplication of complex numbers in rectangular coordinates. Therefore Demoivre's formula is valid.
This formula provides efficient procedures for complex exponentiation. If z is 3 units from the origin, at 45°, then z4 is -81.
Reverse this process to take roots. The 6 sixth roots of 64 all have radius 2, lying on a circle 2 units from the origin. Every angle that is a multiple of 60°, when multiplied by 6, becomes a multiple of 360°, and lands on the positive x axis, which is what we want. Thus the 6 roots are at angles 0° 60° 120° 180° 240° 300°, radius 2. The root at 60° is 1+sqrt(3)i.
The word cyclotomic comes from the Greek. Its literal meaning is, "cut the circle into pieces", and that's what a cyclotomic extension does.
Draw the unit circle in the complex plane, then let p be the nth root of 1. By Demoivre's formula, the distance from p to the origin, when raised to the n, is 1, hence p lies on the unit circle. Also, the angle of p, when multiplied by n, equals 360°, i.e. back around to the x axis, hence p makes an angle of 360/n. Actually, any multiple of this angle will do. There are n distinct angles, n points on the unit circle, and n roots of 1. These are the powers of p.
The n roots of 1 cut the unit circle into equal arcs and define a regular n-gon. When n = 6, for instance, the 6 sixth roots of 1 lie on the unit circle at 60° intervals, and define an inscribed hexagon.
If n = 3, you still get the sixth roots of 1, because minus the cube root of 1, when cubed, is -1, hence minus the cube root of 1 is a sixth root of 1. We discovered this earlier with the Eisenstein integers. Adjoin the cube root of 1, or the sixth root of 1, the result is the same. If n is odd, you can extend by n or 2n, at your convenience.
[ second picture from chapter 1 Eisenstein Integers ]
Remember that the roots of 1 come from an integer polynomial, something like xn-1, and all you need to define this polynomial is the integers. So if a ring R contains Z, or Z/m, and you want to adjoin y the nth root of 1 to R, you can adjoin it to the integers first, then bring in the rest of R. In other words, the rest of R doesn't really affect the cyclotomic extension. It is enough to adjoin Y to the integers first and see what happens, then bring in the rest of R.
If m = a×b, where a and b are relatively prime, then Z/m is the direct product of Z/a and Z/b. This is the chinese remainder theorem. An nth root y in the direct product implies an nth root in each component, (reduce everything mod a or mod b), and nth roots in the two components join together to produce an nth root in Z/m. Therefore we can restrict attention to prime powers.
Subsequent sections will consider Z/p, because that's a field. It is also the homomorphic image of Z/pk, so we may be able to work our way back to prime powers later, and then back to Z/m.
In the field Q, or Z/p, y satisfies some polynomial g(y) of minimum degree. Take the gcd of g(x) and xn-1, and the result has y as a root, and has to be g, since g is minimal. With g as gcd, xn-1 is a multiple of g. In other words, g(x) is a factor of xn-1.
By Gauss' lemma, xn-1 factors over Q the same way it factors over Z. Thus g has integer coefficients, and still divides into xn-1. We saw an example of this when adjoining the cube roots of 1. Start with x3-1; but 1 is a root, and not very interesting, because 1 is already part of the integers, so divide by x-1 and find x2+x+1. This is g(x), the minimum polynomial for y the cube root of 1. Any smaller polynomial would be linear, and would put the cube roots back into Z, hence x2+x+1 is minimal for the cube roots of 1 over Z.
In fact the same polynomial is minimal for the cube roots of 1 over z/p, or any other ring, assuming the cube roots of 1 are not already there to start with. Z/7 contains all 3 cube roots of 1, so not much to do there, x3-1 = (x-1) * (x-2) * (x-4), but one can meaningfully adjoin x to Z/5 mod x2+x+1, and find a quadratic cyclotomic extension bringing in the other two cube roots of 1.
In the same way, the minimum polynomial for i, in the gaussian integers, is x2+1. This is a factor of x4-1, adjoining the fourth roots of 1.
In the complex plane, the n roots of 1 cut the circle into n pieces. The first one counterclockwise from the x axis generates all the others. This is a primitive nth root of 1, which I have denoted y. All the others are powers of y. That takes care of Z, is there a primitive root over Z/p?
Let n = p×t. The polynomial xn-1 is now xt-1 raised to the p power. The roots of xt-1 are adjoined p times over. This doesn't make much sense, so assume p does not divide n.
Adjoin all the roots of xn-1 to get a finite field F. Let b be primitive in F, so that we can take logs base b. Let m be the order of F, minus 1, so that logs wrap around mod m.
Since p does not divide n, use formal derivatives to show all the roots are distinct. There are n such roots; let y have the smallest log base b. The next root, y2, has twice the log of y. If this is reduced mod m then it is smaller than y, which is a contradiction. The same holds for y3, y4, and so on up to yn, which is 1, with log 0. This makes y a primitive nth root of 1. The log of y is m/n, and m is a multiple of n. Remember that some of these roots, i.e. some of the powers of y, could lie in the base field Z/p.
Unfortunately the term "primitive root" is overloaded. Let y be the fourth root of 1 over Z/3. Here -1 is 2, and 2 has no square root, so y is outside the base field. The extension is quadratic and has order 9. Yes indeed, y is primitive relative to our cyclotomic extension x4-1, since y generates all four fourth roots, but y is not a primitive root of the entire finite field F. Let b = y+2, so that b2 = y. Now b has order 8, and is a primitive root of F. There is a primitive root of 1 and a primitive root of F; sorry for the ambiguity.
By convention, a cyclotomic extension adjoins y - not just any old nth root of 1, but a primitive root of 1. It's true that -1 is a fourth root of 1, but when we adjoin the fourth root of 1, we're really talking about i, the primitive fourth root of 1 that generates all the others. Of course -i would do just as well.
So how many primitive roots are there? The powers of yj step through n distinct values, iff j and n are coprime. Thus there are φ(n) primitive roots.
An extension contains all the nth roots of 1 iff it contains a primitive nth root of 1. Let F be the smallest such extension, i.e. the extension generated by y. If the base field is Z/p, what is the dimension d of such an extension? As shown earlier, n divides m, hence n divides pd-1. Reduce mod n, and remember that p is coprime to n, so some power of p is 1. This is the order of p within the units mod n, and it becomes the dimension of the extension. F has order pd, m = pd-1, n divides m, and y is the element with log m/n. Recall the earlier example, wherein the fourth root of 1 was adjoined to Z/3. 3 has order 2 mod 4, that is, 3 squared is 1 mod 4, hence a quadratic extension is sufficient to bring in all the fourth roots of 1.
If you are adjoining y to L, some other finite field, and l has dimension e, then the new field has dimension lcm(d,e).
There is a reason I put the chapters on cyclotomics and finite fields back to back. Every finite field is a cyclotomic extension. If b is primitive for F, then b is an nth root of 1, where n is 1 less than the order of F, and b is a primitive root for a cyclotomic extension of Z/p, or L. The order of p mod n tells us how big this extension has to be. These connections will become important in algebraic number theory.
An automorphism on a cyclotomic extension takes y to something else whose powers yield all the nthroots of 1, that is, another primitive root. The converse is not always true. In an extreme example, look at the cube roots of 1 mod 7. These are 1 2 and 4, with 2 and 4 primitive. If you only care about multiplication, then yes, 2 and 4 can change places. Map 3 to 5, and everything follows from there. However, the word automorphism, taken in context, usually applies to the entire structure, whatever that structure is. If multiplication and addition are both well defined, then both operations should be preserved. A field automorphism has to fix 1, and all the integers, thus there is no field automorphism of Z/7, and the cube roots of 1 must stay put.
Furthermore, an automorphism of an "extension", as opposed to the field itself, has to fix the base, whatever that is. An automorphism on L[y] moves y to another primitive root, but fixes L.
If L = Q, the rationals, there is no trouble. If n is odd, no power of y is -1. If n is even, then yes, yn/2 = -1, but n/2 is not coprime to n, and -1 is not primitive. All the primitive roots lie in the complex plane, and off the x axis. Move y to anything else primitive and it defines the automorphism, and it leaves Q alone. Of course I'm skating past something very important; y and yj have to satisfy the same irreducible polynomial. Otherwise it's not an isomorphism. Sure they both satisfy xn-1, but that's not irreducible. What if y and yj belong to different irreducible factors of xn-1? They don't - they belong to the same irreducible factor, and I'll cover that below. Thus each of the primitive roots defines a unique automorphism. Of course mapping y to y gives the trivial automorphism.
[ Unit circle with the 8 roots of one marked around, y in the first quadrant, arrows from y around the circle to y3, y5 and y7 ]
Compose two automorphisms, y → yi, and y → yj, and the result is y → yij. Exponents are multiplied, and ij is still coprime to n. Composition of automorphisms is commutative, and it looks just like multiplication mod n.
If F is a finite field L[y], and y is cyclotomic primitive, the automorphisms are drawn from the commutative group described above, i.e. y → yj, but they have to be automorphisms of F as well, and they have to fix the base field L (usually the integers). The automorphisms of F are all frobenius, raising everything to the p, or to some power of p if L lies above the integers. We can't use any old yj, it has to be yp, again and again and again, until you get back to y. This is, as we saw before, the order of p mod n. If pd brings us back to start, then the dimension of the extension is d, and there are d automorphisms running in a cycle.
If the extension is F/L, where L is dimension e, then the dimension of F/L is d/e. At the same time, the F automorphisms that fix L start with pe, not p. There are only d/e of these, before you return to start. The cyclotomic extension over L has dimension d/e, with d/e automorphisms running in a circle.
Let's illustrate with the 24th roots of 1 over Z/5. Let F be the finite field of order 25. Every nonzero element of F is now a 24th root of 1. If y is a primitive element of F, also a primitive root of the cyclotomic, then the valid F automorphisms raise y to the fifth power. Do this twice and you're done. Yes, 7 is coprime to 24, but you can't map y → y7 - only y → y5, carried along by the frobenius automorphism on F.
Let y be the root of an irreducible polynomial q(x). The frobenius automorphism carries y to another primitive root, and fixes the coefficients on q. The conjugates of y move around in a cycle, just as the automorphisms form a cycle, and all these conjugates are roots of q. The degree of q is the dimension of the extension, is the length of the cycle of automorphisms. All this holds over a base field L; the cycles are just shorter.
Let L be the rationals or the integers mod p, or some higher finite field. Let F be L(y), adjoining the nth root of 1. Remember that L(y)[x] is a ufd.
Every linear binomial, such as x-c, is both prime and irreducible. In particular, x-y is one of the prime factors of xn-1. The same holds for x-y2, and every x-yj. Thus xn-1 splits over L(y). Since the powers of y are distinct,the linear factors are distinct, and this is a complete prime factorization of xn-1 over L(y).
xn-1 = (x-y) * (x-y2) * (x-y3) * … * (x-1)
Of course some of these factors clump together to become irreducible polynomials over L. For instance, x4-1 splits in the gaussian integers, x-1 times x+1 times x-i times x+i, but over the rationals you get x-1 times x+1 times x2+1. One of the irreducibles over L has root y and defines the extension.
Multiply all the factors x-yj, to get xn-1, and note that the coefficient on xn-1 is 0. Therefore the sum of all nth roots of 1 is 0. The coefficient on xn-2 is also 0, hence the sum of the pairwise products of the nth roots of 1 is also 0. This continues all the way down the line, until the product of the roots of 1 yields -1. Verify this for the cube roots of 1 in the complex plane. They sum to 0, their pairwise products sum to 0, and their product is -1.
[ Unit circle with the 3 cube roots of 1 marked ]
Consider the product of the factors s-tyj, where s and t are arbitrary symbols, and j runs from 1 to n. As shown above, all the coefficients, other than the first and last, drop to 0. Therefore the product is sn-tn.
If n is odd, replace t with -t. Thus the product over s+tyj yields sn+tn.
As you recall, xn-1 brings in all the nth roots of 1. Is this polynomial irreducible? If not, what is its factorization?
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.
Here is a recursive procedure to build ζn.
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. Each root has an order, how long to get to 1. The order is always a factor of 12. Divide by x-1, ζ1, when d = 1, and take away the root 1, having order 1. Divide by x+1 and remove the root -1, 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 Z/p. In fact the former polynomial, with coefficients in Z, can be reduced mod p to produce the latter polynomial. But are the coefficients always integers?
Suppose ζn is the first polynomial that does not have integer coefficients. A lesser polynomial ζj consists of some of the roots of n, and divides evenly into xn-1. ζj has integer coefficients, so by synthetic division, the quotient is well defined in the rationals. By Gauss' lemma, this can be moved back into the integers. Since ζj already starts with a lead coefficient of 1, that is, 1 times a power of x, we can't divide this polynomial by c and multiply the other one by c to clear denominators. Therefore there are no denominators to clear. The quotient has integer coefficients, and begins with 1. Therefore ζn has integer coefficients and is monic.
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 dividing n, raise xn/d-1 to the μ(d) power. Multiply these together to build ζn. Let's see 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 ζ polynomials.
Set d = 1 to get the numerator xn-1. Now we need to divide by ζj for every divisor j ≥ 1 and < n.
Focus on a divisor d, and let e = n/d. Which of the lesser ζ polynomials bring in xe-1? The factor xe-1 appears in ζj when e divides j, properly divides n. Let c = j/e. The exponent on xe-1, used to build ζj, is μ(c). This happens 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). This is the sum of μ(c) for all c dividing n/e, which is equal to 0. Since j was not suppose to include n, take that out and get -μ(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 y 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. Raise any of these to the n and get -1, then square to get 1, thus each has 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.
I'll illustrate with 5 and 10. Since 5 is prime, ζ5 = x4+x3+x2+x+1. Compute ζ10 by the mobius formula.
(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.
ζ looks somewhat unpredictable, but if n is prime, ζn = xn-1 + xn-2 + … + x2 + x + 1. ζ2n is the aforementioned sum with alternating signs.
ζ is also well understood when n is a power of 2. Use the mobius formula above. The only divisors that are squarefree are 1 and 2. Thus xn-1 is divided by xn/2-1, giving xn/2 + 1. We saw this when adjoining the eighth roots of 1. The adjoined root y satisfies x4 + 1 = 0.
Our carefully crafted cyclotomic polynomial ζ need not be irreducible. Consider the 8th roots of 1 over Z/3. The cyclotomic polynomial has degree φ(8) = 4, but a 2 dimensional extension of Z/3 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)
Either quadratic on the right can be used to bring in the 8 roots of 1. Adjoin y, a root of the first quadratic, and linear combinations of 1 and y are sufficient to span all the roots of 1. Apply the automorphism y → y3 to get another primitive root. Apply this again to get back to y. The other quadratic has y5 and y7 as roots, also conjugates of each other.
In the last section we built a cyclotomic polynomial over Z/3 that was not irreducible. However, all cyclotomic polynomials are irreducible over the integers. Here is the proof, courtesy of Gauss.
Let y be a primitive nth root and let p be any prime not dividing n. Suppose ζ factors into g * h, with h irreducible, and h has the root y. Remember that there is a minimum polynomial with root y, which divides every other polynomial having root y. Since h is irreducible, h is the minimum polynomial with root y.
Since p and n are coprime, yp is another primitive root. Suppose yp is a root of g(x). This means y is a root of g(xp).
Since h also has root y, and h is irreducible, h is a factor of g(xp). Say g(xp) = h * k.
Reduce all coefficients mod p, giving the following polynomial equation. Both g and h are monic, so the polynomials do not disappear when reduced mod p.
h * k = g(xp) = g(x)p
Some irreducible factor of h, possibly h itself, now divides g.
h1 * h2 = g ( over Z/p )
h1 * h2 * k = h1p * h2p
Each polynomial above is a factor of xn-1. Split all of these polynomials over Z/p adjoin its cyclotomic roots. Let z be a root of h1, thus x-z is a factor of h1. Now x-z appears p times on the right, and by unique factorization, x-z appears p times on the left. However, the left is g(x), a factor of xn-1, and all the roots of g(x) are distinct. This contradiction means yp is not a root of g(x).
Since yp is not in g(x), it belongs to h(x), as does y to the p2, and p3, and so on.
Let's look at a specific primitive root yj. If p2 divides j, raise y to the p, and then to the p again. This is a primitive root that lies in h. Then, if q divides j, raise this root to the q and find another primitive root in h. Continue through the primes of j, until yj lies in h. With j coprime to n, all the primes of j are coprime to n, and there is no trouble.
Since h contains all the primitive roots, it is equal to ζn, which is built from these same primitive roots, hence ζn is irreducible.
By gauss' lemma, ζn(x) is irreducible over Q, or any subring of Q, such as Z localized about p.
Adjoining an nth root of 1 to Q is an extension of order φ(n), as per the degree of ζn, which is irreducible.
You can map y to any other primitive root, since they are all conjugates of the same irreducible polynomial. The automorphisms of the extension are the integers coprime to n, and composition of automorphisms is multiplication mod n.
When n is prime, ζn, which is the sum of the powers of x up to xn-1, is irreducible. This result generalizes to xn-dn over x-d, for any nonzero integer d, via the following argument.
Let p q and r be polynomials with coefficients in a field F, such that p = q * r. If v is a nonzero constant taken from F, then substituting x → vx is a ring automorphism. In other words, it commutes with addition and multiplication. Therefore p(x) is reducible iff p(vx) is reducible. Turn this around and p(x) is irreducible iff p(vx) is irreducible.
The cyclotomic polynomial, xn-1 + xn-2 + … + x3 + x2 + x + 1, is irreducible over the rationals. The same is true when x is replaced with x/d. Multiply this by dn-1, which is a unit in Q, and the following is irreducible.
xn-1 + dxn-2 + d2xn-3 + … + dn-2x + dn-1
This is the quotient xn-dn over x-d, and we're done.
Set d = -1 to show the alternating sum of the powers of x is irreducible.
Let G be the gaussian integers, that is, the integers adjoin i. Is ζ still irreducible over G?
Remember that G is a ufd, so ζ factors over G iff it factors over the fraction field of G. These are the rational points in the complex plane.
As mentioned earlier, a polynomial is irreducible iff the same polynomial, with x scaled by a constant, is irreducible. In particular, ζn(x) is irreducible iff ζn(-x) is irreducible. With n odd, the second ixpression is ζ2n(x). Therefore it is enough to prove irreducibility for n even.
Next let n be even, but not divisible by 4. Q(i)(y) is the same field extension as Q(y)(i). Call this extension F. Since i is not in Q(y), F/Q has dimension 2×φ(n). Thus F/Q(i) has dimension φ(n). The polynomial of y has degree φ(n), therefore it is irreducible over Q(i).
Finally, when n is divisible by 4, ζ always factors. Adjoin i first, then y, to create a composite extension of dimension φ(n). The first has dimension 2, so the irreducible polynomial associated with y, relative to G, has degree φ(n)/2. The same thing happens if you select a different primitive root, from the other half of ζn. Thus ζ factors precisely into two irreducible pieces, each having half the degree.
Let's illustrate with n = 8. ζ(8) = x4+1. This does not split in the integers, but bring in i, and it becomes (x2+i) × (x2-i). The first has roots y3 and y7, and the second has roots y and y5.
Adjoin y, and build an extension E of dimension d over Q or over Z/p. Here d is φ(n), or perhaps a factor of φ(n) in the finite case. There are d conjugates of y, and they are all primitive. There are d automorphisms, taking y to each of these conjugates.
Let the norm of s be the product of its d conjugates. This is familiar territory.
The norm of st is the product of the conjugates of st, and if c is one of these automorphisms, c(st) = c(s)c(t). Regroup terms, and |st| = |s|*|t|. Thus norm is a multiplicative homomorphism, but what is the range?
Apply c to the norm of s, and you simply rearrange the factors; the outcome is the same. Thus the norm lives in the field that is fixed by all the automorphisms of E. This fixed field is the base field Q, or Z/p, though that is far from obvious.
Take the finite case first. The automorphisms are frobenius, and if |s| is fixed by all of them it is fixed by the first one; raising everything to the p. If x is fixed by this automorphism then xp = x. There are p solutions to this polynomial, namely the integers from 0 to p-1. Therefore |s| is an integer.
If the base is a larger finite field L, then the first automorphism raises everything to some power of p, commensurate with the order of L. This automorphism fixes L, and no more than L. Once again the norm lies in L.
Now turn to Q. Like the finite case, anything that is fixed by all the automorphisms lives in the base field Q. I offer this without proof for now, but it is a result of galois theory, which is coming soon. For now let's just say that |s| lies in Q.
More than just Q, the norm is an integer. Assuming s is nonzero, the norm is the product of nonzero elements in an integral domain, and |s| is not zero. Remember that s is a linear combination of powers of y. Write |s| as a product of conjugates, and the result is another linear combination of powers of y, where each coefficient is a polynomial in the original coefficients of s. Recall the polynomial that implements norm when n = 8. A similar polynomial can be built for any n, though it becomes quite unwieldy. Assuming the coefficients of s are integers, i.e. s belongs to Z[y], then the coefficients of |s| are also integers. With |s| belonging to Q, the coefficients on y and higher powers of y are 0, and |s| is an integer.
In fact the norm is a positive integer. Group various conjugates of s together in pairs. Remember that each conjugate is y replaced with some power of y. so y → y1 and y → yn-1 go together. These two images of s are conjugates in the complex plane, reflections through the x axis. Their product lies on the positive x axis. If n is odd, put y → y2 and y → yn-2 together. Their product lies on the positive x axis. If n is not divisible by 3, put y → y3 and y → yn-3 together. Do this for all the conjugates of s, and |s| lies on the positive x axis. If s belongs to Z[y], then |s| is a positive integer.
From here the familiar theorems come rolling in: s is a unit iff |s| = 1, and s is irreducible when |s| is prime.
If y is an nth root of 1, the powers of y are all units in the cyclotomic extension. Can we identify any other units?
Let i and j be integers such that gcd(i,n) = gcd(j,n). Let r be the ratio (1-yi) / (1-yj). Use synthetic division to expand the quotient, giving the following:
1 + yj + y2j + y3j + … + yk
The quotient terminates because there is some k such that jk = i mod n. Divide through by the common gcd, whence j/g becomes a unit mod n/g, and some k times j/g gives i/g, another unit mod n/g.
The inverse, (1-yj) / (1-yi), is also a polynomial in y, hence r is invertible.
Some of these expressions produce old familiar units. When n = 5, (1-y2) / (1-y3) = 1+y3+y+y4, or -y2. Others are new, such as (1-y2) / (1-y) = 1+y. This is not on the unit circle, not ± a power of y.
If n is prime, what is the norm of 1-y? We already solved this when n = 3. y is a cube root of 1; plot it on the unit circle, 120 degrees around. That puts 1-y in the fourth quadrant, 30 degrees down from the x axis. The conjugate 1-y2 is also the complex conjugate, 30 degrees up from the x axis. Their product is 3, hence the norm is 3. Furthermore, 1-y over 1-y2 is a ratio unit, thus 1-y and 1-y2 are associates. Therefore 3 is a ramified prime, (1-y)2 times some unit. Happily, the same thing is going to happen for all n.
Since n is prime, 1-y over 1-yj is a ratio unit, hence all the conjugates of 1-y are associates of 1-y. The norm of y is a unit away from (1-y)n-1.
Remember that the product of x-yj, as j runs from 1 to n, is xn-1. Divide this by x-1 to get ζn: xn-1 + x n-2 + … + x + 1. Replace x with 1 to get the desired product; the answer is n. Therefore |1-y| = n.
Since the norm is prime, 1-y is irreducible. All its conjugates are also associates, hence (1-y)n-1 = n, or at least a unit times n, and n is a ramified prime.
The same thing happens when n is a power of 2. The cyclotomic polynomial ζn is xn/2+1, so replace x with 1 and get 2. The norm of 1-y is 2, hence 1-y is irreducible. The conjugates of y are y raised to any odd power. Quotients of these conjugates are ratio units, and these conjugates are all associates of each other. Thus 2 is ramified, equal to (1-y)n/2.
A complete characterization of primes over primes is coming, once we have more machinery in place. One of my professors remarked, "If you like algebraic number theory, then you can never know enough about the cyclotomics."