MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Obviously this doesn't work for linear $f$. – Siksek Feb 6 '13 at 8:12
It's amazing how difficult it is to find reducible polynomials... – Lior Bary-Soroker Feb 6 '13 at 9:23
You can drop the condition that $p(a)$ etc. not equal 1, unless you also disallow them equalling $-1$ (and it's irrelevant in the finite field case anyway). The requirement that the factors all have degree at least 1 is, I think, sufficient to make the problem interesting. – Barry Cipra Feb 6 '13 at 21:51
Roughly speaking, how general is the class of polynomials $p\cdot q+r\cdot s$, where $p\ q\ r\ s$ are non-constant polynomials? – Włodzimierz Holsztyński May 12 '13 at 21:14
Let me state it more cartefully: how general is the class of polynomials $f := p\cdot q+r\cdot s$, where $p\ q\ r\ s$ are non-constant polynomials such that $\deg(f)\ =\ \max(\deg(p\cdot q)\ \ \deg(r\cdot s))$ ? – Włodzimierz Holsztyński May 12 '13 at 21:18
up vote 4 down vote accepted

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).

share|cite|improve this answer
Nice answer! As for where the problem came from, if you look at its history of edits, you'll see it slowly accreted hypotheses. I recommended not requiring $p(a)\neq 1$ etc. (and the attendant requirement that $f(a)$ be composite), thinking it was sufficient to require all the degrees to be positive, but I see from your answer that it does add something of interest. – Barry Cipra Feb 7 '13 at 1:20

Am I missing something?* If $f(x) = x^n + \cdots$ is a monic polynomial of degree $n$, one can let $r(x)=2x^{n-1}-2a^{n-1}+f(a)$ and $s(x)=x-a+1$, so that $r(a)s(a)=f(a)\cdot1=f(a)$, and then $p(x)=1$ and $q(x)=2f(x)-r(x)s(x)$ (which has lower degree than $f$), obtaining $p(a)q(a)=2f(a)-r(a)s(a)=f(a)$ also.

*(Added later): This answer was posted for a previous version of the problem, which now disallows factors from taking the value 1 at $x=a$.

share|cite|improve this answer
I was thinking something else where $s(a) \ne 1$ – Turbo Feb 6 '13 at 19:24
may be I should add it as condition. – Turbo Feb 6 '13 at 19:24
@unknown, maybe you want to require that all four factors have degree at least 1. – Barry Cipra Feb 6 '13 at 19:33

Not sure if u want the additional constraints $p(x), q(x),r(x),s(x)\neq -f(x)$, the following choices would work every time for any value of $a$:

$ p(x)=-f(x)$, $q(x)=x-a-1$, $r(x)=-f(x)$, $s(x)=-x+a-1. $

share|cite|improve this answer
your offer didn't satisfy the assumptions deg(p) < deg(f) nor deg(r) < deg(p). – Włodzimierz Holsztyński Feb 6 '13 at 9:00
I wonder if this answer was down-voted because someone thought that adas had not read the question carefully. In fact, the early versions of the question did not include any assumptions on the degrees of $p$, $q$, etc. – Barry Cipra Feb 6 '13 at 22:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.