Polynomial GCD (or HCF)

This tool calculates two Polynomial GCD (Greatest Common Divisor) also called HCF (Highest Common Factor). Polynomials considered here are over the rational numbers.

How to use this calculator?

Variable Input a single-letter that is the polynomial variable. Examples :
polynomial = 4x+1 , then input variable = 'x'
polynomial = 9t + 5 , then input variable ='t'
Polynomial Are accepted :
  • The Polynomial variable
  • Polynomial coefficients : must be rational numbers e.g. integer numbers (-4) or fractions (1/4) or decimals (3.6).
  • Operators : + - * / ^ (the last is the power operator so x^2 = `x^2`)
  • Parentheses : an example of use is (x^2+1)(x-5)
Examples Polynomial = x^2-4x+1 (variable = 'x')
Polynomial = (x^2-1)(x-5)-3 (variable = 'x')
Polynomial = x^3-4/3*x^2+1 (variable = 'x')
Polynomial = 0.23*t^2-1/5*t+1/2 (variable = 't')

2 Polynomials GCD Example

To find the GCD (greatest common divisor) of the polynomials
`A(x) = x^5 - 2x^4 + x^2 - x - 2`
`B(x) = x^3 - x^2 - x - 2`
We will use the Euclidean algorithm for polynomials which is to do successive divisions of polynomials until we get a zero remainder. The GCD will be the last non-zero remainder.

We proceed as follows:

Step 1: Division of A(x) by B(x)
We divide A(x) by B(x) and note the quotient Q1(x) and the remainder R1(x).
A(x) : B(x) = Q1(x) with a remainder R1(x).
`Q1(x) = x^2 - x`
`R1(x) = 2x^2 - 3x - 2`

Calculator : Division of A(x) by B(x)

Step 2: division of the divisor by the remainder (from the previous step) i.e., B(x) by R1(x)
Now we divide B(x) by the previous remainder R1(x) and note the new quotient Q2(x) and the new remainder R2(x).
B(x) : R1(x) = Q2(x) with a remainder R2(x).
`Q2(x) = 1/2x + 1/4`
`R2(x) = 3/4x - 3/2`

Calculator : Division pf B(x) by R1(x)

Step 3: division of the divisor by the remainder (from the previous step) i.e., R1(x) by R2(x)
Now we divide R1(x) by the previous remainder R2(x) and note the new quotient Q3(x) and the new remainder R3(x).
R1(x) : R2(x) = Q3(x) with a remainder R3(x).
`Q3(x) = 8/3x + 4/3`
`R3(x) = 0`

Calculator : Division of R1(x) by R2(x)

The gcd is equal to the last non-zero remainder, which is,

The GCD (greatest common divisor) of A(x) and B(x) is given by the last non-zero remainder obtained in the Euclidean algorithm for polynomials, which in this case is `3/4x - 3/2`.

We can multiply this remainder by a real number, also called a scalar, to eliminate the fractions and simplify the expression. This operation is valid because the GCD is defined only up to a scalar factor.

In our case, by multiplying by `4/3`, we obtain `4/3 * (3/4x - 3/2)`, which simplifies to `x - 2`. Thus, the GCD can be expressed in a simplified form without fractions.

`\text{GCD}(A,B) = x - 2`

See also

Polynomial calculators
Math Calculators