Does it ask for $\gcd(Q(x), 1+ax+x^2R(x))=P_n(x)$?

mestavk wrote: Let define $P_{n}(x)=x^{n-1}+x^{n-2}+x^{n-3}+...+x+1$ for every positive integer $n$. Prove that for every positive integer $a$ one can find a positive integer $n$ and polynomials $R(x)$ and $Q(x)$ with integer coefficients such that \[P_{n}(x)=(1+ax+x^{2}R(x),Q(x)).\] I think problem should be: Let define $P_{n}(x)=x^{n-1}+x^{n-2}+x^{n-3}+...+x+1$ for every positive integer $n$. Prove that for every positive integer $a$ one can find a positive integer $n$ and polynomials $R(x)$ and $Q(x)$ with integer coefficients such that \[P_{n}(x)=(1+ax+x^{2}R(x))Q(x).\] My answer is: Let $n$ be the product of first $k$ primes. For $k=2$, we have $n=6$. $P_6(x)(x-1) = x^6 - 1 = (x-1)\underbrace{(x+1)(x^2+x+1)}_{\text{There should be } \dots + 2x +1}\underbrace{(x^2-x+1)}_{Q(x)}$ So we get for $a=2$, there exists polynomials $R(x)$ and $Q(x)$. One observation is to get $ax$, we may $\underbrace{(\dots + x + 1)\dots (\dots + x + 1)}_{a \text{ times }}$ For $k=3$, we have $n= 2\cdot 3 \cdot 5 = 30$. $P_{30}(x)(x-1) = x^{30} - 1$. We have $x^{2} - 1 | x^{30} - 1$, $x^{6} - 1 | x^{30} - 1$, and $x^{10} - 1 | x^{30} - 1$. So $x-1$, $x+1$, $x^{3}-1$, $x^{3}+1$, $x^{5}-1$, $x^{5}+1$ also divide $x^{30}-1$. So $x^2+x+1$ and $x^4+x^3+x^2+x+1$ divides $x^{30}-1$. If their $\gcd$ is $1$, we will have \[x^{30}-1 = P(x)\underbrace{(x+1)(x^2+x+1)(x^4+x^3+x^2+x+1)}_{\dots + 3x +1}\] Lemma: \[\gcd(x^m-1, x^n-1) = x^{\gcd(m,n)}-1.\] Proof: $d=(m,n) \Rightarrow x^d-1|x^m-1$ and $x^d-1|x^n-1$. $(x^m-1,x^n-1)=t \Rightarrow x^d-1 | t \Rightarrow x^d-1\leq t$. There exist positive integers $r,s$ such that $mr - ns = d$, or equivalently $mr = d + ns$. We have $t | x^{mr}-1$ and $t | x^{ns}-1 \Rightarrow t|x^d(x^{ns}-1) \Rightarrow t | x^{d+ns}-x^d \Rightarrow t|x^{mr}-x^d$. Subtracting the two $t | x^{mr} - 1 - x^{mr} + x^d \Rightarrow t | x^d - 1 \Rightarrow t\leq x^d - 1$. So $(x^m-1, x^n-1) = t = x^d - 1 = x^{(m,n)} - 1$.$\blacksquare$ According to above lemma, for distinct primes $p$ and $q$, \[\gcd(x^p-1, x^q-1) = x-1.\] So for $k=a$, we have $n$ with product of the first $a$ primes. For any prime $p|n$, we have $x^p-1|x^n-1$. So $(1+x+\dots + x^{p-1})|x^n-1$. There is at least $a$ of them. Since all are relatively prime, the product exactly $a$ of them also divides $x^n-1$. \[x^n-1 = (x-1) \underbrace{\dots}_{Q(x)}(1+ax + \underbrace{\dots}_{x^2R(x)})\blacksquare\]

An, almost similar alternative; showing, how to make $a\mapsto a+1$ jump; which also shows why the construction of the previous solution (through the product of primes) really works. Let us first, illustrate the idea, that will be used throughout the proof. Suppose that, we have proven the result, for $a\in\mathbb{N}$. Let, $n$, $Q$, and $R$ be the corresponding quantities. We have, $$ x^n -1 = (x-1)(1+ax+x^2Q(x))R(x). $$Now, just for the purposes of illustration, again, suppose that, $3\nmid n$. We will give a way to jump from $a$ to $a+1$. Our idea is to look at $x^{3n}-1$. Clearly, both, $x^{n}-1 \mid x^{3n}-1$; and, $x^2+x+1 \mid x^{3n}-1$. What is more important, is that, ${\rm gcd}(x^n-1,x^2+x+1)=1$, and therefore, $x^{3n}-1$ is divisible by $(x^n-1)(x^2+x+1)$. Hence, $$ x^{3n}-1 = P_{3n}(x)(x-1)=(x-1)(1+ax+x^2Q(x))(x^2+x+1)\underbrace{R(x)\Theta(x)}_{\triangleq \tilde{R}(x)}. $$Thus, we have, $$ P_{3n}(x) = (1+(a+1)x+\underbrace{(1+a)x^2+ax^3+x^2Q(x)(x^2+x+1)}_{\triangleq x^2\tilde{Q}(x)})\tilde{R}(x), $$and therefore, $$ P_{3n}(x) = (1+(a+1)x+x^2\tilde{Q}(x))\tilde{R}(x). $$This idea is illustrative enough. So, we will now, proceed as follows. Suppose that, $a$ is generated by $n$. Now, take a prime $p$ such that $p\nmid n$, and look at, $x^{pn}-1$. Clearly, both, $x^n-1$ and $x^{p-1}+x^{p-2}+\cdots+1$ divides this polynomial. Next, we present a lemma, to establish coprimeness. Lemma: If, $p$ is a prime number, such that $p \nmid n$. Then, $$ {\rm gcd}(x^n-1,P_{p}(x))=1. $$Proof: Let, $n=qp +r$, with, $1\leq r\leq p-1$. We have, $x^p \equiv 1 \pmod{P_{p}(x)}$, and therefore, $$ x^n - 1 \equiv x^r -1 \pmod{P_p(x)}\implies x^n-1 = A(x)P_p(x)+x^r-1. $$Now, if these factors have a gcd, then, this factor must divide both $x^r-1$, and $x^{p-1}+\cdot+1$. We now, state, the irreducibility criterion for $P_p(x)$, as a separate lemma, which will, clinch the result. Lemma: For any prime number $p$, the $p^{th}$ cyclotomic polynomial, $$ x^{p-1}+x^{p-2}+\cdots+1, $$is irreducible. Proof: Note that, $P_p(x) = \frac{x^p-1}{x-1}$. Letting, $x=y+1$, this turns out to be, $$ P_p(x) = \frac{(y+1)^p-1}{y}=\sum_{i=1}^p \binom{p}{i}y^{p-1}. $$Now, using, Eisenstein's criterion, and the fact that, $p\mid \binom{p}{i}$, for every $i=1,2,\dots,p-1$, we arrive at the result. Coming back to the problem, if $a$ is obtained through $n$, then, after letting $p$ to be a prime, $p\nmid n$, we get, \begin{align*} P_{pn}(x)(x-1) &= x^{pn}-1 \\ &=(x^n-1)(x^{p-1}+\cdots+1)\Theta(x)\\ &=(x-1)(1+ax+x^2Q(x))(1+x+x^2\tilde{Q}(x))R(x)\Theta(x)\\ &=(x-1)(1+(a+1)x+x^2\hat{Q}(x))\tilde{R}(x), \end{align*}implying that, $$ P_{pn}(x)=1+(a+1)x+x^2\hat{Q}(x))\tilde{R}(x), $$where, $\tilde{R}(x)=R(x)\Theta(x)$, $\tilde{Q}(x)=1+x+\cdots+x^{p-3}$, and $\hat{Q}$ is obtained through some algebra, and merging. For $n=3$, we directly obtain $a=1$, which constitutes the baseline of the induction, and we are done.

An alternate construction: given $a$, let $2,3,\dots,p$ be the first $a$ primes. Then taking $n=2\cdot 3\cdots p$ and $Q=\tfrac{P}{\Phi_2\cdot \Phi_3\cdots \Phi_p}$ does the trick. (Where $\Phi_n(x)$ is the $n^\text{th}$ cyclotomic polynomial.)

Let's prove this by induction over $a$. For $a=1$, we have $(1+x+x^2\cdot 0)\cdot 1=x+1$. For $a=2$, we have $(1+2x+x^2(2+x))(x^2-x+1)=(1+x+x^2)(x+1)(x^2-x+1)=(1+x+x^2)(x^3+1)=x^5+x^4+x^3+x^2+x+1$. Suppose that for a positive integer $a-1$ ,where $a\ge 3$, such polynomials exist. Let $P_m(x)=[1+(a-1)x+x^2V(x)]U(x)$. Since $a-1\ge 2$, we can find that $m\ge 2$. We will prove that one can find a positive integer $n$ and polynomials $R(x)$ and $Q(x)$ such that $P_n(x)= [1+ax+x^2R(x)]Q(x).$ Let $R(x)=a+ax+ax^2+\cdots +ax^{m-3}+(a-1)x^{m-2}+(x^{m-1}+x^{m-2}+\cdots +1)V(x).$ We have $$1+ax+x^2R(x)=1+ax+ax^2+ax^3+\cdots +ax^{m-1}+(a-1)x^m+x^2V(x)(x^{m-1}+x^{m-2}+\cdots +1)=$$$$(1+x+\cdots+x^{m-1})+(a-1)x(1+x+\cdots+x^{m-1})+x^2V(x)(x^{m-1}+x^{m-2}+\cdots +1)=$$$$(x^{m-1}+x^{m-2}+\cdots +1)[1+(a-1)x+x^2V(x)]$$We know that $1+x+x^2+\cdots +x^{m-1}+x^m|1+x^m+x^{2m}+\cdots +x^{m^2-m}+x^{m^2}$. Hence, there exist a polynomial $A(x)$ with integer coefficients such that $1+x^m+x^{2m}+\cdots +x^{m^2-m}+x^{m^2}=(1+x+x^2+\cdots +x^{m-1}+x^m)A(x).$ Let $Q(x)=U(x)\cdot A(x)$. Then, $$[1+ax+x^2R(x)]Q(x)=(x^{m-1}+x^{m-2}+\cdots +1)[1+(a-1)x+x^2V(x)]U(x)\cdot A(x)=$$$$(x^{m-1}+x^{m-2}+\cdots +1)(x^m+x^{m-1}+\cdots+1)A(x)=(1+x+\cdots x^{m-2}+x^{m-1})(1+x^m+x^{2m}+\cdots +x^{m^2-m}+x^{m^2})=$$$$1+x+\cdots x^{m-1}+x^m+x^{m+1}+\cdots +x^{m^2+m-1}=P_{m^2+m-1}(x)$$, done.