Latest revision as of 05:11, 23 September 2011

Problem

Show that $ Phi_n(x) $ is reducible if $ n $ is not prime.

Think I might be stumped on this problem. I was thinking to show that Eisenstein fails when n isn't prime, but I'm not sure how to do that. ---

something by using the counter...?

I'm working on it, will update in a little while...

--Nick Rupley 23:21, 8 April 2009 (UTC)

Eisenstein's Criterion gives sufficient conditions for a polynomial to be irreduible over $ \scriptstyle\mathbb{Q} $, but not necessary conditions. That is, you can't use the inverse of Eisenstein's Criterion to show that a polynomial is reducible.

Now, onto cyclotomic polynomials. I'm pretty sure Uli has a typo in the homework question, because $ \scriptstyle\Phi_n(x) $ is irreducible over $ \scriptstyle\mathbb{Q} $ for all $ \scriptstyle n\in\mathbb{N} $. For any positive integer $ \scriptstyle n $, the $ \scriptstyle n $-th cyclotomic polynomial $ \scriptstyle\Phi_n(x) $ is defined as:

$ \scriptstyle\Phi_n(x)\ =\ \prod_\zeta(x-\zeta) $, where $ \scriptstyle\zeta $ ranges through the primitive $ \scriptstyle n $-th roots of unity.

I could go into detail, but it is much better explained here: Cyclotomic Polynomials

For reference, here are some of the first $ \scriptstyle n $-th cyclotomic polynomials:

$ \scriptstyle\Phi_1(x)\ =\ x-1 $

$ \scriptstyle\Phi_2(x)\ =\ x+1 $

$ \scriptstyle\Phi_3(x)\ =\ x^2+x+1 $

$ \scriptstyle\Phi_4(x)\ =\ x^2+1 $

$ \scriptstyle\Phi_5(x)\ =\ x^4+x^3+x^2+x+1 $

$ \scriptstyle\Phi_6(x)\ =\ x^2-x+1 $

For example, let's look at $ \scriptstyle\Phi_4(x) $. What are the primitive 4-th roots of unity? By inspection it's obvious that they are $ \scriptstyle i $ and $ \scriptstyle -i $, since $ \scriptstyle i^4\ =\ (-i)^4\ =\ 1 $. We could also reach this answer by looking at the more general set of 4-th roots of unity (not necessarily primitive) $ \scriptstyle\zeta_k\ \equiv\ e^{2\pi ik/4},\ k\equiv\{1,2,3,4\} $ and then only take the roots for which $ \scriptstyle k $ and 4 are relatively prime. Then, $ \scriptstyle k\equiv \{1,3\} $, and $ \scriptstyle\zeta_k\ \equiv\ \{e^{\pi i/2}, e^{3\pi i/2}\}\ =\ \{i, -i\} $ ( Euler's Formula helps out here). To check, we can expand the factors:

$ \scriptstyle(x-i)(x+i)\ =\ x^2-ix+ix-i^2\ =\ x^2+1\ =\ \Phi_4(x)\ \checkmark $

The cyclotomic polynomials are actually irreducible over $ \scriptstyle\mathbb{Q} $ for all positive integers. Here is a proof of that statement.

So, I'm going to assume that instead of $ \scriptstyle\Phi_n $, Uli meant the polynomial $ \scriptstyle\frac{x^n-1}{x-1} $. Obviously $ \scriptstyle1 $ is a root of $ \scriptstyle x^n-1 $ and thus $ \scriptstyle x-1 $ divides $ \scriptstyle x^n-1 $, so there are no problems there. Indeed for any prime $ \scriptstyle n $, $ \scriptstyle\frac{x^n-1}{x-1}\ =\ x^{n-1}+x^{n-2}+\ldots+x+1\ =\ \Phi_n(x) $, and is irreducible over $ \scriptstyle\mathbb{Q} $ (this is proved in the book on pp308-309). So, what happens when $ \scriptstyle n $ is composite?

If $ \scriptstyle n $ is composite, then there exists an integer $ \scriptstyle a\geq2 $ such that $ \scriptstyle a\mid n $. Consider the primitive $ \scriptstyle a $-th root of unity $ \scriptstyle\zeta_a $. We know that $ \scriptstyle\zeta_a^a\ =\ 1 $, from the definition of a primitive root of unity. Now consider the $ \scriptstyle a $-th cyclotomic polynomial $ \scriptstyle\Phi_a(x) $. Since $ \scriptstyle\zeta_a $ is a primitive $ \scriptstyle a $-th root of unity, $ \scriptstyle\Phi_a(x) $ must therefore be a minimal, irreducible polynomial of $ \scriptstyle\zeta_a $. This is important. Return here to see why it must be minimal for $ \scriptstyle\zeta_a $ over $ \scriptstyle\mathbb{Q} $.

Now, remember that $ \scriptstyle a\mid n $. This implies that for some positive integer $ \scriptstyle b $, $ \scriptstyle n\ =\ ab $.

$ \scriptstyle\Rightarrow\ \zeta_a^n\ =\ \zeta_a^{ab}\ =\ (\zeta_a^a)^b\ =\ 1^b\ =\ 1 $. This means that $ \scriptstyle\zeta_a $ is actually an $ \scriptstyle n $-th root of unity as well! What does this mean? Recall that a number $ \scriptstyle r $ is an $ \scriptstyle n $-th root of unity if $ \scriptstyle r^n\ =\ 1 $. But that is equivalent to saying that $ \scriptstyle r $ is a zero of the polynomial $ \scriptstyle x^n-1 $. So, since $ \scriptstyle\Phi_a(x) $ is the minimal polynomial over the primitive $ \scriptstyle a $-th root of unity $ \scriptstyle\zeta_a $, $ \scriptstyle\Phi_a(x) $ must therefore divide $ \scriptstyle x^n-1 $.

Now return to the polynomial $ \scriptstyle\frac{x^n-1}{x-1} $. We know that if $ \scriptstyle n $ is composite, there exists a divisor $ \scriptstyle a\geq2 $ such that $ \scriptstyle a\mid n $. We now also know that this implies that $ \scriptstyle\Phi_a(x)\textstyle\mid\scriptstyle\frac{x^n-1}{x-1} $.

It follows that $ \scriptstyle\frac{x^n-1}{x-1} $ can be expressed as a product $ \scriptstyle\Phi_a(x)\cdot g(x) $ for some $ \scriptstyle g(x) $. It therefore must be reducible over $ \scriptstyle\mathbb{Q} $. $ \scriptstyle\Box $

For futher clarification, look at $ \scriptstyle f(x)\ =\ \frac{x^6-1}{x-1} $ for an example. We know that $ \scriptstyle2\mid6 $, so $ \scriptstyle\Phi_2(x)\ =\ x+1 $ must divide $ \scriptstyle\frac{x^6-1}{x-1}\ =\ x^5+x^4+x^3+x^2+x+1 $. By long division:

    $ \scriptstyle x^4\ \ \ +x^2\ \ \ \ \ +1 $

$ \scriptstyle x+1)\overline{x^5+x^4+x^3+x^2+x+1} $

  $ \scriptstyle-\underline{x^5+x^4} $
      $ \scriptstyle0\ +x^3+x^2 $
       $ \scriptstyle-\ \underline{x^3+x^2} $
            $ \scriptstyle0\ +x+1 $
             $ \scriptstyle-\ \underline{x+1} $
                 $ \scriptstyle0 $

So, $ \scriptstyle\frac{x^6-1}{x-1}\ =\ \Phi_2(x)\cdot(x^4+x^2+1) $, and is clearly reducible over $ \scriptstyle\mathbb{Q} $. $ \scriptstyle\checkmark $

(By the way, Chapter 33 in the book will help a lot too if you're still confused; it focuses completely on cyclotomic field extensions.)

--Nick Rupley 01:58, 9 April 2009 (UTC)