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
31.03.2018 16:47
12.11.2018 16:04
OK. Can you explain clearly your ideal? We will discuss there
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?
12.11.2018 16:44
Tintarn wrote:
Your chase
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.
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
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.)
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.