Lecture 12 Cyclotomic Polynomials, Primes Congruent to 1 mod n Cyclotomic Polynomials - just as we have primitive roots mod p, we can have primitive nth roots of unity in the complex numbers. Recall that there are n distinct nth roots of unity - ie., solutions of z n = 1, in the complex numbers. We can write them as e2πij/n for j = 0, 1, . . . n − 1. They form a regular n-gon on the unit circle. We say that z is a primitive nth root of unity if z d 6= 1 for any d smaller than n. If we write z = e2πij/n , this is equivalent to saying (j, n) = 1. So there are φ(n) primitive nth roots of unity. Eg. 4th roots of 1 are solutions of z 4 − 1 = 0, or (z − 1)(z + 1)(z 2 + 1) = 0 ⇒ z = 1, −1 ± i Now 1 is a primitive first root of unity, −1 is a primitive second root of unity, and ±i are primtiive fourth roots of unity. Notice that ±i are roots of the polynomial z 2 + 1. In general, define Y Φn (x) = (x − e2πij/n ) (j,n)=1 1≤j≤n This is the nth cyclotomic polynomial. We’ll prove soon that Φn (x) is a polynomial with integer coefficients. Another fact is that it is irreducible, ie., cannot be factored into polynomials of smaller degree with integer coefficients (we won’t prove this, however). Anyway, here is how to compute Φn (x): take xn − 1 and factor it. Remove all factors which divide xd − 1 for some d|n and less than n. Eg. Φ6 (x). Start with x6 − 1 = (x3 − 1)(x3 + 1). Throw out x3 − 1 since 3|6 and 3 < 6. x3 + 1 = (x + 1)(x2 − x + 1). Throw out x + 1 which divides x2 − 1, since 2|6, 2 < 6. We’re left with x2 − x + 1 and it must be Φ6 (x) since it has the right degree 2 = ϕ(6) (the nth cyclotomic polynomial has degree ϕ(n), by definition). If you write down the first few cyclotomic polynomials you’ll notice that the coefficient seems to be 0 or ±1. But in fact, Φ105 (x) has −2 as a coefficient, and the coefficients can be arbitrarily large if n is large enough. These polynomials are very interesting and useful in number theory. For instance, we’re going to use them to prove that given any n, there are infinitely many primes congruent to 1 mod n. Eg. Φ4 (x) = x2 + 1 and the proof for primes ≡ 1 mod 4 used (2p1 . . . pn )2 + 1 1 Proposition 45. 1. xn − 1 = Q Φn (x) 2. Φn (x) has integer coefficients 3. For n ≥ 2, Φn (x) is reciprocal; ie., Φn ( x1 ) · xϕ(n) = Φn (x) (ie., coefficients are palindromic) Proof. 1. is easy - we have xn − 1 = Y (x − e2πij/n ) 1≤j≤n 0 0 If (j, n) = d then e2πij/n = e2πij /n where j 0 = dj , n0 = nd , and (j 0 , n0 ) = 1. 0 0 (x − e2πij /n ) is one of the factors of Φn0 (x) and n0 |n. Looking at all possible j, we recover all the factors of Φn0 (x), for every n0 dividing n, exactly once. So Y xn − 1 = Φn0 (x) n0 |n 2. By induction. Φ1 (x) = x − 1. Suppose true for n < m. Then   xm − 1 = Y Y   Φd (x)   Φd (x) = d|m ·Φm (x) d|m d 1 and so divisible by some prime p. First, note that p cannot equal pi for any i, since Φn (x) has constant term 1, and so pi divides every term except the last of Φn (lnp1 . . . pn ) ⇒ it doesn’t divide M . For the same reason we have p - n. In fact, (p, a) = 1 where a = lnp1 . . . pN . Now Φn (a) ≡ 0 mod p by definition, which means an ≡ 1 mod p. By the lemma, we cannot have am ≡ 1 mod p for any m|n, m < n. So the order of a mod p is exactly n, which means that n|p − 1 since ap−1 ≡ 1 mod p ⇒ p ≡ 1 mod n, exhibiting another prime which is ≡ 1 mod n. Contradiction. ( ) Note - we did not even need to assume that there’s a single prime ≡ 1 mod n; if N = q take the empty product, ie., 1, and we end up looking at Φn (ln) for large l. 4