# Is there a simple way to prove that a polynomial is divisible by other irreducible polynomial?

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?

• Consider the map $f:R[x]\to R[x]/(g(x))$, and look at whether $f(p(x))=0$. – Don Thousand Jan 10 at 4:22
• A polynomial over what ring? – Lucas Henrique Jan 10 at 4:34
• a polynomial with real coefficients. – Sameer nilkhan Jan 10 at 4:39
• 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. – Bill Dubuque Jan 10 at 18:22

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