Let $f(x)$ be an irreducible polynomial in $\mathbb{Z}[x]$ or $\mathbb{F}\_{q}[x]$ with $deg(f(x)) \ge 2$ (assume constant coefficient is $1$).


Let $a \in \mathbb{Z}$ or $\mathbb{F}\_{q}$. Let $f(a)$ be composite if $a \in \mathbb{Z}$.


Let $char(\mathbb{F}\_{q}) \ne 2$.


Is it always possible to find polynomials $p(x),q(x),r(x)$ and $s(x) \in \mathbb{Z}[x]$   such that:
$$2f(x) = p(x)q(x) + r(x)s(x),$$
$$1 \le deg(p(x)) < deg(f(x)),\qquad 1 \le deg(q(x)) < deg(f(x)),$$
$$ 1 \le deg(r(x)) < deg(f(x)),\qquad 1 \le deg(s(x)) < deg(f(x)),$$
and
$$p(a)q(a)=r(a)s(a)=f(a),\quad p(a) \ne \pm 1,\ q(a) \ne \pm 1,\ r(a) \ne \pm 1,\ s(a) \ne \pm 1?$$


If such a decomposition is found, is it unique?



Decomposing irreducible polynomials with a prescribed condition - Existence
The problem as stated is unsolvable in the case of $\mathbb{Z}$ coefficients with $f(a)$ a prime power. **Proof:** Let $a=0$, let $f(0) = p^n$ and let the coefficient of $x$ in $f$ not be divisible by $p$. Then $p(0)$, $q(0)$, $r(0)$ and $r(0)$ are all of the form $\pm p^k$, and the hypotheses forbid that $k=0$. So all of the constant terms of $p(x)$, $q(x)$, $r(x)$ and $s(x)$ are divisible by $p$. But then the linear term of $f(x) = (p(x)q(x)+r(x)s(x))/2$ is divisible by $p$ as well, a contradiction. $\square$ 




---


Here is a solution for $\mathbb{Z}$ coefficients, assuming that $f(a)$ is not a prime power. 
Adapting it for coefficients in a finite field should be easy, since there are fewer things to worry about. 


Without loss of generality, let $a=0$. Since $f(0)$ is not a prime power, we can factor it as factor $f(0)$ as $p\_0 \cdot r\_0$ with $GCD(p\_0,r\_0)=1$. Find $c$ and $d$ such that $c p\_0 -d r\_0=1$, note for future reference that this implies $GCD(c,d)=1$. We will take $p(x) = dx+p\_0$ and $r(x) = cx+r\_0$, and slowly construct $q(x)$ and $s(x)$.


**Step 1** Making $2 f(x) = p(x) q\_0(x) + r(x) s\_0(x)$.


We just need to show that $2 f(x)$ is in the ideal generated by $p(x)$ and $r(x)$. But $c p(x) - d r(x) = c (dx+p\_0) - d (cx+r\_0) = c p\_0 - d r\_0 = 1$, so this ideal is the whole ring and every polynomial is in it. Explicitly, $2 f(x) = (2 c f(x)) p(x) - (2 d f(x)) r(x)$. $\square$


**Step 2** Making $2 f(x) = p(x) q\_1(x) + r(x) s\_1(x)$ with $\deg q\_1$ and $\deg s\_1 \leq \deg f -1$. 


Suppose that we have found polynomial $Q(x)$ and $S(x)$ with $2 f(x) = p(x) Q(x) + r(x) S(x)$ and $\deg Q$ or $\deg R \geq \deg f$. We will show that we can replace them by polynomials $Q'(x)$ and $S'(x)$ of lower degree, still obeying the equation $2 f(x) = p(x) Q'(x) + r(x) S'(x)$.


Since we are supposing that at least one of $p(x) Q(x)$ and $r(x) S(x)$ has degree larger than the sum $p(x) Q(x) + r(x) S(x)$, we see that the leading terms must cancel. Let the leading terms of $Q$ and $S$ be $Q\_m x^m + \cdots$ and $S\_m x^m + \cdots$. So $d Q\_m + c S\_m=0$. Using our above observation that $GCD(c,d)=1$, we see that $Q\_m = c F$ and $S\_m = -d F$ for some integer $F$. Replace $Q(x)$ and $S(x)$ by $Q(x) - F r(x) x^{m-1}$ and $S(x) + F p(x) x^{m-1}$. $\square$.


**Step 3** Achieving $2 f(x) = p(x) q(x) + r(x) s(x)$ with $p(0) q(0) = r(0) s(0)$, and $\deg q$, $\deg s \leq \deg f-1$.


At this point in the proof we already have $2 f(x) = p(x) q\_1(x) + r(x) s\_1(x)$ with $q\_1$ and $s\_1$ of sufficiently low degree; we just must change their values at $0$ without making their degree larger. 


Comparing constant terms, 
$$2 f(0) = 2 p\_0 r\_0 = p\_0 q\_1(0) + r\_0 s\_1(0).$$
Using $GCD(p\_0, r\_0) = 1$, we see that $r\_0 | q\_1(0)$ and $p\_0 | s\_1(0)$. Let $q\_1(0) = r\_0 (1-G)$ and $s\_1(0) = p\_0 (1+G)$ for some integer $G$. Then replace $q\_1(x)$ and $s\_1(x)$ by $q\_1(x) + G r(x)$ and $s\_1(x) - G p(x)$. Since $\deg p = \deg r =1 \leq \deg f-1$, this replacement can't make the degrees of $q$ and $s$ larger than $\deg f-1$. $\square$.




---


Where did this problem come from? It would make a nice Putnam problem (not now, of course).


