Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given $f(x),g(x) \in \mathbb{Z}[x]$, two irreducible polynomials, is there a polynomial $h(x) \in \mathbb{Z}[x]$ coprime to $f(x)$ such that $f(x) + g(x)h(x)$ is reducible over $\mathbb{Z}[x]$ with factors not congruent to $1 \mod g(x)$?

If so, what is the best way to find one such $h(x) \in \mathbb{Z}[x]$?

Let degree of $f(x),g(x)$ be bounded by $n$ (with degree of $g(x)$ strictly less than degree of $f(x)$) and maximum size of coefficients of $f(x),g(x)$ be $2^{s}$. Is there a $(ns)^{c}$ or $(n2^{s})^{c}$ algorithm to find such an $h(x)$ (if such a polynomial exists) where $c \in \mathbb{N}$ is fixed?

In general, is there a way to define the probability that $f(x) + g(x)h(x)$ is reducible into factors not congruent to $1 \mod g(x)$? It is likely this probability asymptotically goes to zero in terms of $n$ and $s$. However how fast does it go to zero? Does it go to zero asymptotically as $\frac{1}{(ns)^{c_{1}}}$ or $\frac{1}{(n2^{s})^{c_{1}}}$ for some positive constant $c_{1}$?

share|improve this question
I suppose you do not want $h$ to be a multiple of $f$, then? In general, can you prove the existence a (non-trivial) $h$ that does the job? –  René Jun 28 '13 at 22:54
Thankyou corrected. –  Turbo Jun 28 '13 at 22:56
Good question! There should exist. I do not have a proof. May be I will change the question. –  Turbo Jun 28 '13 at 23:01

1 Answer 1

Let $h(x)=f(x)(f(x)+g(x))+1$, obviously coprime to $f(x)$. Then $$ f(x)+g(x)h(x) = (f(x)+g(x))(1+f(x)g(x)). $$

share|improve this answer
I think $h=1+fg+f$ if your displayed formula is to hold. –  Venkataramana Jun 29 '13 at 3:05
not exactly what I was thinking. However with polynomials there is always a sneaky way. –  Turbo Jun 29 '13 at 7:27

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.