If we need to show that a polynomial $p(x)$ is divisible by another polynomial $g(x)$ which can be broken or reduced into linear factors then it can be shown that each linear factor divides $p(x)$ and hence $g(x)$ divides $p(x)$.

But in case of irreducible polynomial $g(x)$ this method will not work. In that case is there any simple way to prove that $g(x)$ divides $p(x)$ without performing the long division of polynomials?

Please guide me.

  • $\begingroup$ Consider the map $f:R[x]\to R[x]/(g(x))$, and look at whether $f(p(x))=0$. $\endgroup$ Jan 10, 2020 at 4:22
  • $\begingroup$ A polynomial over what ring? $\endgroup$ Jan 10, 2020 at 4:34
  • $\begingroup$ a polynomial with real coefficients. $\endgroup$ Jan 10, 2020 at 4:39
  • $\begingroup$ If $g$ has special form then there may be optimizations, e.g. if $g$ is cyclotomic, i.e. $\,g\mid x^n-1\,$ for some $n$ then we can use the method of simpler multiples. $\endgroup$ Jan 10, 2020 at 18:22

2 Answers 2


Polynomial division has low computational cost compared to calculating the root of a polynomial, which is nearly impossible for high degree (in fact, general solution by radicals is impossible via Galois theory). But if you’re really not willing to use the easiest method, extend $\mathbb R$ to $\mathbb C$ so every polynomial can be splitted into linear factors.

Your polynomial will be divisible by the irreducible one if all the roots $\alpha_1, \ldots, \alpha_k$ are also roots and since it’s irreducible over $\mathbb R$, it has no multiple roots. So not only you’ll have to compute the roots of a polynomial which is extremely costly but also apply them in a higher-degree polynomial.

So, in synthesis: use polynomial long division.


The polynomial GCD is probably the best known general method to determine the largest factor of $g$ that divides $p$. The method is essentially Euclid's algorithm.

A significant space reduction is to work with coefficients modulo one or more relatively prime ideals (where the quotient of the ceofficient ring with the ideal is finite) and then reassemble the result using, for instance, the the Chinese Remainder Theorem. (There are some technical details here -- for instance avoid ideals where the leading coefficient of $g$ or $p$ vanishes. Rational reconstruction is an alternative to the CRT.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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