The question is that $e^{2\pi i/6r}$ is a root of the polynomial $X^{2r}-X^{r}+1 \in \mathbb Q[X]$ , we want to prove that $X^{2r}-X^{r}+1$ is irreducible if and only if $r$ is of the form $2^{a}3^{b}(a,b\geq 0)$, and the following question $X^{2r}+X^{r}+1$ is irreducible if and only if $r$ is of the form a power of $3$.
The irreduciblity of $X^{2r}-X^{r}+1$
-
1Cool, this is a very useful link. – 2012-12-27
3 Answers
Note that
$X^{2r}-X^r+1=\frac{X^{3r}+1}{X^r+1}=\frac{X^{6r}-1}{(X^r+1)(X^{3r}-1)}$
$\Rightarrow$
Assume by contradiction that $r$ has a prime factor $p \geq 5$. Let $r=pq$. Then $e^{\frac{2 \pi i }{6q}}$ is a root of $X^{6r}-1$ but not of $(X^r+1)(X^{3r}-1)$.
This shows that the minimal polynomial of $e^{\frac{2 \pi i }{6q}}$ divides $X^{2r}-X^r+1$. Since the degree of the minimal polynomial is $\phi(6q) \neq 2r$, it follows that the minimal polynomial of $e^{\frac{2 \pi i }{6q}}$ is a proper divisor of $X^{2r}-X^r+1$.
$\Leftarrow$
If $r=2^a3^b$. It should be easy to prove from
$X^{2r}-X^r+1=\frac{X^{6r}-1}{(X^r+1)(X^{3r}-1)}$ that $X^{2r}-X^r+1$ is a cyclotomic polynomial. Note that
$\phi(6r)=2^a\cdot 3^b \cdot 2=2r=6r-r-3r=\deg(X^{6r}-1)-\deg(X^r+1))-\deg(X^{3r}-1)$
The second part should follow by the same idea, using
$X^{2r}+X^r+1=\frac{X^{3r}-1}{X^r-1}$
-
0Thanks so much for such detailed answer, I appreciate that. :) – 2012-12-27
In general, the degree of the minimal polynomial for $e^{\frac{2\pi i}n}$ is $\phi(n)$. So if $x^{2r}-x^r+1$ is irreducible, then $2r=\phi(6r)$. Write $r=2^a3^bD$ with $(6,D)=1$. Then $2r = \phi(6r)=\phi(2^{a+1})\phi(3^{b+1})\phi(D)=2^a(2-1)3^b(3-1)\phi(D) = 2r\frac{\phi(D)}D$
So $\phi(D)=D$, so $D=1$.
For the second case, $e^{\frac{2\pi i}{3r}}$ is a root, so for $x^{2r}+x^r+1$ to be irreducible, $2r=\phi(3r)$. Write $r=3^aD$ with $(D,3)=1$.
Then $2r = \phi(3r)=\phi(3^{a+1}D)=(3-1)3^a\phi(D) = 2r\frac{\phi(D)}D$, and again $D=1$.
-
0yes , I can use that, we have learnt the Euler's function and learnt cyclotomic polinomial – 2012-12-27
This solution requires familiarity with Cyclotomic polynomials, specfically their irreducibility. I will factor $x^{2r}-x^{r}+1$ completely.
As N.S. observed, $x^{2r}-x^{r}+1 = \frac{x^{3r}+1}{x^r+1}=\frac{x^{6r}-1}{x^{3r}-1}\frac{x^r-1}{x^{2r}-1}$ Remember that $\prod_{d|n} \phi_d(x) = x^n-1$, thus: $x^{2r}-x^{r}+1 = \frac{\prod_{d|6r} \phi_d(x)}{\prod_{d|3r} \phi_d(x)}\frac{\prod_{d|r} \phi_d(x)}{\prod_{d|2r} \phi_d(x)}$ Most of the terms cancel - $\frac{\prod_{d|6r} \phi_d(x)}{\prod_{d|3r} \phi_d(x)} = \prod_{d|6r, d\nmid 3r} \phi_{d}$ $\frac{\prod_{d|r} \phi_d(x)}{\prod_{d|2r} \phi_d(x)} = \frac{1}{\prod_{d|2r, d\nmid r} \phi_{d}}$
So $x^{2r}-x^{r}+1 = \prod_{d|6r,d\nmid 3r,(d|r \text{ or } d\nmid 2r)} \phi_{d}(x)$
When $r=3^a 2^b$, the unique positive integer satisfying the three conditions $d|6r,d\nmid 3r,(d|r \text{ or } d\nmid 2r)$ is $d=6r$ itself - the condition $d|6r,d\nmid 3r$ requires that $d$ is divisible by the maximal power of $2$ dividing $6r$, so $d=2^{b+1}3^{k \le a+1}$. $d$ can't divide $r$, so it must not divide $2d$, provided $k\ge a+1$, i.e. $k=a+1$. Thus $x^{2r}-x^r+1 = \phi_{6r}(x)$.
When $r$ is not a product of a power of 2 and a power of 3, $d=6r$ appears in the product, but also any $\frac{6r}{q}$ where $q$ divides $r$ but $(q,2)=(q,3)=1$: $x^{2r}-x^{r}+1 = \prod_{d=6r/q,q|r,(q,6)=1} \phi_{d}(x)$
(this formula is always valid.) If we write $r=2^{a}3^{b}r', (r',6)=1$, we find that the number of factors in the factorization of the polynomials equals the number of divisors of $r'$.
EDIT: In general, by using $\phi_{n} (x) = \prod_{d|n} (x^d - 1)^{ \mu (n/d) }$, one can show: $\phi_{n}(x^m) = \prod_{d|m,(d,n)=1} \phi_{nm/d}(x) $ So $\phi_{n}(x^m)$ is irreducible iff $p|m \implies p |n$, in which case $\phi_{n}(x^m) = \phi_{nm}(x)$.
To prove the last statement (without using my identity), notice that $\phi_{n}(x^m)$ must be divisible by $\phi_{nm}(x)$, and by comparing degrees as in the other solutions, to have equality we must have $m\phi(n)=\phi(nm)$, i.e. $nm \prod_{p|n}(1-\frac{1}{p}) = nm\prod_{p|nm}(1-\frac{1}{p})$, or $\prod_{p|nm, p \nmid n} (1-\frac{1}{p}) = 1$, which is equivalent to $p|m \implies p|n$.
-
0@user53800 - In general, I proved $\phi_n(x^m) = \prod_{d|m, (d,n)=1} \phi_{nm/d}(x)$, using the explicit formula for $\phi_n$ (the one that uses the Mobius functions). Thus, $\phi_n(x^m)$ is irreducible iff each prime dividing $m$ also divides $n$, in which case $\phi_n(x^m)=\phi_{nm}(x)$. – 2012-12-31