Basic functions: Rational functions
Greatest common divisor and least common multiple of polynomials
Discussing division with remainder for polynomials and long division of polynomials, we have already pointed out the analogy with these operations for integers. This raises the question whether this also holds for the greatest common divisor of polynomials by analogy with gcd of integers. The answer is yes and even Euclid's algorithm for computing the gcd has its equivalent algorithm for polynomials!
A polynomial \(d(x)\) is a divisor of the polynomial \(p(x)\) if there exists a polynomial \(q(x)\) such that \(p(x)=q(x)\cdot d(x)\).
In other words, if \(d(x)\) a divisor of the polynomial \(p(x)\), then \(p(x)\) is a multiple of \(d(x)\).
Greatest common divisor
For polynomials \(p(x)\) and \(q(x)\) we call a polynomial that is both a divisor of \(p(x)\) and \(g(x)\) a common divisor of \(q(x)\) and \(p(x)\).
If \(p(x)\) and \(q(x)\) are both unequal to the zero polynomial, then a common divisor with the highet degree is called a greatest common divisor.
The greatest common divisor is unique up to a nonzero scalar. If you make the leading coefficient equal to \(1\) by scalar multiplication, that is, make it a monic polynomial, them the greatest common divisor of polynomials is unique and is denoted by gcd.
Two polynomials are said to be relativcely prime if they have only \(1\) as a common divisor, i.e., if their gcd is equal to \(1\).
Example
From \[x^3-1=(x^2+x+1)(x-1)\] follows that \[\textbf{gcd}(2x^3-2, x^2+x+1)=x-1\] and \[x^3-1\text{ is a multiple of }x-1\]
The polynomials \(x^2-1\) and \(x^2-4\) relatively prime because their factorised forms have no factor in common.
Least cCommon multiple For polynomials \(p(x)\) and \(q(x)\) we call the monic polynomial with the least degree that is a multiple of both polynomials the least common multiple which we denote as \(\textbf{lcm}\bigl(p(x),q(x)\bigr)\).
Calculation rules for gcd and lcm Let \(a\) and \(b\) ne polynomials in one variable,
- \(\mathrm{gcd}(a,b)= \mathrm{gcd}(b,a)\).
- \(\text{gcd}(a,0)=\frac{a}{c}\) where \(c\) is the head coefficient of \(c\)
- If \(c\) is a common divisor of \(a\) and \(b\) then \(\mathrm{gcd}(a,b)= c\times \mathrm{gcd}\left(\frac{a}{c},\frac{b}{c}\right)\).
- If \(a=q\times b+r\), i.e, if division of \(a\) by \(b\) give the remainder\(r\), then \(\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)\).
- If \(d\) is a common divisor of \(a\) and \(b\) with leading coefficient equal to \(1\), then \(\gcd(a,b) = d\cdot\gcd\left(\frac{a}{d},\frac{b}{d}\right)\).
- \(\mathrm{gcd}(a,b)\cdot\mathrm{kcv}(a,b)=a\cdot b\).
The Euclidean algorithm Let \(a\) and \(b\) two be polynomials in one variable with \(\text{degree}(a)\ge \text{degree(b)}\) (if the ordering relation is not satisfied, just swap the two polynomials). The gcd of \(a\) and \(b\) can now be calculated as follows:
- Calculate the remainder \(r\) of \(a\) when dividing by \(b\).
- Replace \(a\) with \(b\) and \(b\) with \(r\).
- Repeat the previous steps until \(b\) equals \(0\).
- The last value of \(a\) is equal to \(\mathrm{gcd}(a,b)\).
Note: You can enter intermediate results in the answer field in the form of \(\mathrm{gcd}(\Box,\Box)\) and gradually work through the algorithm towards the final answer.
The Euclidean algorithm goes as follows: \[\begin{aligned}
\mathrm{gcd}(x^5+x^4-7\,x^3-5\,x^2,x^4-2\,x^3-2\,x^2) &= \mathrm{gcd}(x^4-2\,x^3-2\,x^2,x^3+x^2) \\[0.1cm]
{\small\blue{\text{because } x^5+x^4-7\,x^3-5\,x^2}}&{\small\blue{\,=(x+3)\cdot (x^4-2\,x^3-2\,x^2)+x^3+x^2}}\\[0.5cm]
&= \mathrm{gcd}(x^3+x^2,x^2) \\[0.1cm]
{\small\blue{\text{because } x^4-2\,x^3-2\,x^2}}&{\small\blue{\,=(x-3)\cdot (x^3+x^2)+x^2}}\\[0.5cm]
&= \mathrm{gcd}(x^2,0) \\[0.1cm]
{\small\blue{\text{because } x^3+x^2}}&{\small\blue{\,=(x+1)\cdot x^2+0}}\\[0.5cm]
&= x^2\end{aligned}\]
