Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.)
