cyclotomic polynomials « Bedtime mathematics

a result concerning cyclotomic polynomials

April 24, 2011 mymbl 1 comment

In this post we record a useful result concerning cyclotomic polynomials. This will help us prove what is claimed in this post.

Theorem: For distinct positive integers ${i,j}$ the GCD of the values of cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ , is ${p}$ only if ${j = i \cdot p^k}$ for some integer ${k \ge 1}$ . On the other hand, if ${j = i \cdot p^k}$ for some ${k \ge 1}$ , ${(\Phi_i(y) , \Phi_j(y)) = p \text{ or } 1}$ .

Proof: ( ${\Leftarrow}$ ) We show that ${j = i \cdot p^k}$ for some ${k \ge 1}$ if ${p | (\Phi_j(y), \Phi_i(y))}$ . We will start by proving that the gcd ${g=(i,j)=i}$ . Then show that $j/i$ is a prime power. Let ${g = (i,j)}$ and assume to the contrary that ${g < i}$ . The cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ divide ${\frac{(y^j-1)}{(y^g-1)}}$ and ${\frac{(y^i-1)}{(y^g-1)}}$ resp. But, ${\frac{(y^i-1)}{(y^g-1)}}$ and ${\frac{(y^j-1)}{(y^g-1)}}$ are relatively prime (easy exercise), and so their divisors ${\Phi_i(y)}$ and ${\Phi_j(y)}$ are also relatively prime. This shows that if for ${1 \le i < j}$ , the values of cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ have a factor in common then ${\text{gcd}(i,j) = i}$ .

Now suppose ${j= m \cdot i}$ and that, a prime ${p}$ , divides the values of cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ . But ${\Phi_j(y)}$ divides

$\displaystyle \frac{ (y^j-1)}{(y^i-1)}=1+y^i+ \ldots + y^{i(m-1)},$

and so ${p}$ also divides it. Going modulo ${p}$ , we see that ${(y^j-1)/(y^i-1) \mod p=m}$ . This proves that ${m}$ is a multiple of ${p}$ . Next we show that ${m}$ is a power of ${p}$ .

Let ${p^h}$ be the largest power of ${p}$ dividing ${i}$ and ${p^k}$ be the largest power of ${p}$ that divides ${j = i\cdot m}$ . Now using Thm 1.1 of \cite{YVES}, we have,

$\displaystyle \Phi_{i}(y) | \Phi_{i/p^h}(y^{p^h}) \text{ and } \Phi_{im} (y) | \Phi_{im/p^k} (y^{p^k})$

Now, ${\Phi_{i/p^h}(y^{p^h}) \mod p = \Phi_{i/p^h} (y)}$ and ${\Phi_{im/p^k} (y^{p^k}) \mod p = \Phi_{im/p^k} (y)}$ . Since ${p | \Phi_i(y)}$ and ${p | \Phi_j(y)}$ , ${p}$ divides both ${ \Phi_{im/p^k}(y)}$ and ${ \Phi_{i/p^h}(y)}$ . From the arguments in the first paragraph of this proof, this is possible only if ${im/p^k = i/p^h}$ or ${m = p^{k-h}}$ . Hence ${j = i p^{k-h}}$ .

( ${\Rightarrow}$ ) Let ${j = i \cdot p^k}$ ( ${k>0}$ ). From the proof in the “only if” direction ${p}$ is the only prime that can possibly divide ${ (\Phi_i(y), \Phi_j(y))}$ . To show that

$\displaystyle {(\Phi_i(y),\Phi_j(y) = p \text{ or } 1}$

it will be enough to show that

$\displaystyle {p | (\Phi_i(y) , \Phi_j(y)) } \Rightarrow {p^2 {\not |} \Phi_j(y)}$

First suppose ${p^k \neq 2}$ . Since ${p | \Phi_i(y)}$ , we must have, ${p | (y^i-1)}$ and so we may write ${y^i \mod p^2= 1 + ap \mod p^2}$ , for some ${a \in \{0,\ldots, p-1\}}$ . Also, as ${\Phi_j(y) | (y^{i p^k} -1 ) / (y^i-1)}$ , it is enough to show that ${p^2 {\not |} (y^{i p^k} -1 ) / (y^i-1)}$ to show that ${p^2 {\not |} \Phi_j(y)}$ . Consider,

$\displaystyle (y^{i p^k} -1 ) / (y^i-1) \mod p^2 = 1 + y^i + \ldots + y^{(p^k-1)i} \mod p^2$

$\displaystyle = p + ap + 2 ap + 3 ap + \ldots + (p^k-1) ap \mod p^2$

$\displaystyle = p + ap ( p^k ( p^k-1)/2 ) \mod p^2 = p \mod p^2$

Thus ${p^2 {\not |} (y^{i p^k} - 1) / (y^i-1)}$ . If ${j = 2i}$ with ${p=2}$ , and ${i}$ is an even number then ${\Phi_j(y) | (y^{2i}-1) / (y^i-1) = 1 + y^i \mod 4 \neq 0}$ . If ${i}$ is odd then,