For every positive integer $n\ge 3$, let $\phi_n$ be the set of all positive integers less than and coprime to $n$. Consider the polynomial: $$P_n(x)=\sum_{k\in\phi_n} {x^{k-1}}.$$ a. Prove that $P_n(x)=(x^{r_n}+1)Q_n(x)$ for some positive integer $r_n$ and polynomial $Q_n(x)\in\mathbb{Z}[x]$ (not necessary non-constant polynomial). b. Find all $n$ such that $P_n(x)$ is irreducible over $\mathbb{Z}[x]$.
Problem
Source: 2018 Vietnam Team Selection Test
Tags: polynomial, algebra
Tintarn
31.03.2018 16:47
a. First suppose that $n$ is odd. Then since for $k \in \phi_n$, also $n-k \in \phi_n$ and $(-1)^k+(-1)^{n-k}=0$, it is immediate that $P_n(-1)=0$ and hence we may choose $r=1$.
Now suppose that $4$ divides $n$. Via the same pairing as above and noting that $i^k+i^{n-k}=0$ for $k \in \phi_n$ we have $P_n(i)=0$ and hence we may choose $r=2$.
From now on suppose that $n \equiv 2 \mod 4$. Since $n \ge 3$, there is an odd prime $p$ dividing $n$. Let $r=2^k$ be the maximal power of $2$ dividing $p+1$ and let $s$ be the product of all primes dividing $n$ except for $2$ and $p$. We shall show that $x^r+1$ divides $P_n(x)$ or, equivalently, $xP_n(x)$. By Möbius Inversion,
\[xP_n(x)=(x^n-1)\sum_{d \mid n} \frac{\mu(d)}{x^d-1}=(x^n-1)\sum_{d \mid s} \mu(d) \left(\frac{1}{x^d-1}-\frac{1}{x^{2d}-1}-\frac{1}{x^{pd}-1}+\frac{1}{x^{2pd}-1}\right)\]Now since $4 \nmid n$, all the denominators are not divisible by $x^r+1$. Also $x^r+1$ is irreducible over the rationals so we may work with the quotients. So it suffices to prove that $x^r+1$ divides each summand and since $x^r+1$ divides $x^{rd}+1$, it suffices to prove that claim for $d=1$ i.e. we need to show that $x^r+1$ divides
\[\frac{1}{x-1}-\frac{1}{x^2-1}-\frac{1}{x^p-1}+\frac{1}{x^{2p}-1}\]But in the quotient field $\mathbb{Q}[x]/(x^r+1)$ we have $x^{p+1}=-1$ and hence
\[\frac{1}{x-1}-\frac{1}{x^2-1}-\frac{1}{x^p-1}+\frac{1}{x^{2p}-1}=\frac{x}{x^2-1}-\frac{x^p}{x^{2p}-1}=\frac{x}{x^2-1}-\frac{x^{p+2}}{x^{2p+2}-x^2}=\frac{x}{x^2-1}+\frac{x}{1-x^2}=0\]proving our claim.
b. So $Q_n$ must be constant and hence $P_n$ must be of the form $x^r+1$. In particular $\varphi(n)=P_n(1)=2$. But it is well-known and easy to see that this happens if and only if $n \in \{3,4,6\}$.
kahliipreyta
12.11.2018 16:04
OK. Can you explain clearly your ideal? We will discuss there
Tintarn
12.11.2018 16:29
kahliipreyta wrote: OK. Can you explain clearly your ideal? We will discuss there Fine. Could you ask a more precise question? Which is the first step you don't understand? What exactly is your problem there?
kahliipreyta
12.11.2018 16:44
Tintarn wrote:
By Möbius Inversion,
\[xP_n(x)=\sum_{d \mid n} \frac{\mu(d)}{x^d-1}=\sum_{d \mid s} \mu(d) \left(\frac{1}{x^d-1}-\frac{1}{x^{2d}-1}-\frac{1}{x^{pd}-1}+\frac{1}{x^{2pd}-1}\right)\]
Your chase
Tintarn
12.11.2018 16:54
kahliipreyta wrote: Your chase Sorry I seem to have missed a factor of $(x^n-1)$ there. I corrected it. Is it now clear for you? In any case, thanks for spotting that.
kahliipreyta
13.11.2018 19:11
Mobius Inversion Denote that $f(n) = \sum_{d|n} \mu(n/d) F(d) = \sum_{d|n} \mu(d) F(n/d) .$ can you explain for this, this is quite new for me
Tintarn
18.01.2021 21:55
kahliipreyta wrote: Mobius Inversion Denote that $f(n) = \sum_{d|n} \mu(n/d) F(d) = \sum_{d|n} \mu(d) F(n/d) .$ can you explain for this, this is quite new for me For me, Möbius inversion is the identity \[\sum_{d \mid n} \mu(d)=\begin{cases} 1 & n=1\\0 & n>1 \end{cases}\]which allows us to disentangle gcd conditions as follows: \begin{align*} xP_n(x)&=\sum_{(k;n)=1} x^k\\ &=\sum_{k=1}^{n-1} \sum_{d \mid n,k} \mu(d) x^k\\ &=\sum_{d \mid n} \mu(d) \sum_{1 \le k <n, d \mid k} x^k\\ &=\sum_{d \mid n} \mu(d) \sum_{k=1}^{n/d-1} x^{kd}\\ &=(x^n-1)\sum_{d \mid n} \mu(d) \cdot \frac{x^d}{x^d-1}\\ &=(x^n-1)\sum_{d \mid n} \frac{\mu(d)}{x^d-1} \end{align*}where in the last step we used that $n>1$ and hence $\sum_{d \mid n} \mu(d)=0$. (Basically in the third line already everything has happened, the rest is just a standard computation of a geometric sum and rearranging.)
naman12
02.12.2022 00:25
(a) We look for $r_n$ powers of $2$, which is clearly possible. Clearly if $n$ is odd, $-1$ is a root, and if $4\mid n$, $i$ a root. Thus, we focus on $n\equiv 2\pmod 4$. Note the identities (for $\gcd(a,b)=1$) \[P_{ab}(x)=P_b(x)\cdot\frac{x^{ab}-1}{x^b-1}-P_b(x^a)\]\[P_{bc^2}(x)=P_{bc}(x)\cdot\frac{x^{bc^2}-1}{x^{bc}-1}\]Thus we only have to look at $n=2p$ where $p$ is prime, as if $\omega$ is an $r_b$th root of unity, if we have $r_b\geq 2$, then $P_b(\omega)=P_{bc}(\omega)=P_{bc^2}(\omega)=0$. However, we see \[P_{2p}(x)=\sum_{k=0}^{p-1}x^{2k}-x^{p-1}=\frac{(x^{p-1}-1)(x^{p+1}+1)}{x^2-1}\]so if we let $r_n=2^{\nu_2(p+1)}$, we are done. (b) Clearly this means $\phi(n)\leq 2$ as $Q_n$ is constant. If $n>6$ is odd, $1,2,n-1$ are relatively prime. Otherwise, at least one of $n/2-1,n/2-2$ is odd, so is hence relatively prime to $n$, so $\phi(n)>2$. Thus $n\leq 6$, and $n=3,4,6$ follows.