Informally, the greatest common divisor (GCD) of two polynomials p(x) and q(x) is the "biggest" polynomial that divides evenly into both p(x) and q(x). When dealing with numbers, the definition is similar. If you have two whole numbers, the greatest common divisor of those numbers is simply the biggest whole number that you can divide into both of them while getting a remainder of zero. The greatest common divisor is also sometimes referred to as the greatest common factor or the highest common factor. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ...

Formal Definition

The greatest common divisor of two polynomials p(x) and q(x), not both zero, with coefficients from a field is the monic polynomial d(x) of highest degree such that d(x) is a common divisor of both p(x) and q(x). In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In mathematics, a monic can refer to monic morphism – a special kind of morphism in category theory, monic polynomial – a polynomial whose leading coefficient is one. ... In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ... The degree of a polynomial is the maximum of the degrees of all terms in the polynomial. ...

The definition is very specific and this is very important. For example, if both polynomials were zero, then any polynomial would divide them both. In this case, there would be no greatest common divisor. Thus, at least one of the polynomials must be nonzero.

Also, if there were no requirement for the GCD to be monic, there could be several different, even an infinite number of different, GCDs for any two polynomials. This results because any nonzero constant multiple (with constants from the field) of the monic common divisor of highest degree is still a common divisor of highest degree.

Finally, the definition states the coefficients must come from a field. If the coefficients could come from any ring, then factorization would not necessarily be unique. For example, in Z6,

(2x + 1)(3x + 1) = 6x² + 5x + 1 = 5x + 1

and

5(x + 5) = 5x + 25 = 5x + 1.

All of these details together ensure that there is a GCD and that the GCD is unique.

Properties

• As stated above, the GCD of two nonzero polynomials, with coefficients from a field, is unique.
• If c(x) is any common divisor of p(x) and q(x), then c(x) divides d(x). This is sometimes given in the definition instead of requiring d(x) to be the common divisor of highest degree. The two definitions are logically equivalent.
• The GCD of two polynomials, p(x) and q(x), can be written as a linear combination of p(x) and q(x). That is, there exist some polynomials, in the same field, r(x) and s(x), not necessarily unique, such that

d(x) = p(x)r(x) + q(x)s(x).

Methods for finding the GCD

There are several ways to find the greatest common divisor of two polynomials. Some of them include:

1. Factorization, in which one finds the factors of each expression, then selects the set of common factors held by all from within each set of factors.
2. The Euclidean Algorithm, which can be used to find the GCD of two polynomials in the same manner as for two numbers.
3. Swami Bharati Krishna Tirtha's Vedic mathematics contains a method, here called the Vedic method, which is mainly an application of the Lopana-Sthapana Sutra, the Sankalna-Vyavakalan process, and the Adyamadya rule. The sutra is a formula for the alternate destruction of the highest and lowest powers (by the addition or subtraction of multiples of the coefficients). ^[1]

In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. ... In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... Vedic mathematics is a system of mental calculation developed by Jagadguru Swami Sri Bharati Krishna Tirthaji Maharaja in the middle 20th century which he claimed he had based on sutras he had found in an appendix of Atharvaveda, an ancient text of the Indian teachings known as the Vedas. ...

Factoring

To find the GCD of two polynomials using factoring, simply factor the two polynomials completely. Then, take the product of all common factors. At this stage, we do not necessarily have a monic polynomial, so finally multiply this by a constant to make it a monic polynomial. This will be the GCD of the two polynomials as it includes all common divisors and is monic.

Example One

Find the GCD of x² + 7x + 6 and x² - 5x - 6.

x² + 7x + 6 = (x + 1)(x + 6)

x² - 5x - 6 = (x + 1)(x - 6)

Thus, their GCD = (x + 1).

Euclidean Algorithm

Finding the GCD by factoring is intuitively simple but requires knowing how to factor the polynomials, which can be difficult, especially if the polynomials have large degree. The Euclidean Algorithm is a fast method which works for any pair of polynomials. It makes repeated use of division with remainder, just as when the Euclidean Algorithm is applied to two numbers. When using the Euclidean Algorithm on two numbers, the size of the numbers decreases at each stage. With polynomials, the degree of the polynomials decreases at each stage. The last nonzero remainder, made monic if necessary, is the GCD of the two polynomials. In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ...

Example One

Find the GCD of x² + 7x + 6 and x² - 5x - 6.

x² + 7x + 6 = (x² - 5x - 6)(1) + (x + 1)(12)

x^2 - 5x - 6 = (x + 1)(x - 6) + 0

Since x + 1 is the last nonzero remainder, the GCD of these polynomials is x + 1.

Algebraic proof of the Vedic method for finding the GCD

Let P and Q be two expressions. Let H be their GCD. Let A and B be the quotients (after dividing by the GCD). Therefore, P/H = A and Q/H = B and also P = HA and Q = HB. Therefore P±Q = H(A±B) and MP±NQ = H(MA±NB) Therefore, the GCD of P and Q is also the GCD of P±Q, 2P±Q, P±2Q, and MP±NQ. So, when we select our M and N so that the highest and lowest powers are removed, then the GCD appears and shows itself! ^[2]

Examples

Example one: the Vedic Method

Find the GCD of x²+7x+6 and x²-5x-6. To eliminate the x-squared terms, just subtract the expressions. To eliminate the constant terms, simply add the two expressions. Then, pull out any common factors to reveal the GCD.

 x2+7x+6 x2+7x+6 Subtract: -(x2-5x-6) Add: + (x2-5x-6) 12x+12 = 12(x+1) 2x2+2x = 2x(x+1) Thus, their GCD = (x+1). 

Example two: Vedic method

 E1 = x3 –3x2 - 4x +12 E2 = x3 – 7x2 +16x -12 Minus -(x3 –7x2 +16x –12) Add +(x3 – 3x2 - 4x +12) 4x2 –20x +24 2x3 -10x2 +12x Remove common factors: 4(x2–5x +6) 2x(x2-5x+6) Their GCD = (x2-5x+6) 

Example three: factorization

Find the GCD of the two expressions after factorization:

 E1 = x4 + x3 –5x2 -3x +2 = (x+1)(x-2)(x2+2x-1) and E2 = x4 -3x3 + x2 +3x -2 = (x+1)(x-2)(x-1)2 Seeing the shared factors are the binomials (x+1)(x-2) we have them as the GCD. 

Example three: Vedic method

Find the GCD of two expressions by elimination and retention of the highest and the lowest powers.

 E1 = x4 + x3 –5x2 -3x +2 E1 = x4 + x3 –5x2 -3x +2 and E2 = x4 -3x3 + x2 +3x -2 E2 = x4 -3x3 + x2 +3x -2 The sum: 2x4 –2x3 –4x2 Their difference: 4x3 –6x2 –6x +4 Pull out the common factors: (2x2)(x2 –x -2) (2)(2x3 –3x2 –3x +2) Restore a factor of (2x) for a second elimination. Multiply by (2x)(x2 –x -2) = 2x3 –2x2 –4x Subtract second result from first result: 2x3 –3x2 –3x + 2 Minus -(2x3 –2x2 –4x ) – x2 +x + 2 Since the expressions have positive x2 terms remove the factor of -1: Their GCD = (x2 -x -2) 

Example four: Vedic method

 Find the GCD of two expressions. E1 = 6x4 – 7x3 – 5x2 + 14x +7 E2 = 3x3 – 5x2 +7 To eliminate the 4th power: E1 + (-2x)(E2). Subtract: E1 - E2 to eliminate the constant terms. 6x4 – 7x3 –5x2 +14x +7 6x4 – 7x3 –5x2 +14x +7 (-2x)(3x3–5x2+7)= add +(6x4 +10x3 –14x) Minus -(3x3 –5x2 +7) 3x3 –5x2 +7 6x4 –10x3 +14x Take out the common factor: (2x)(3x3 -5x2 +7) The GCD = (3x3 –5x2 +7) 

See also

• Euclidean algorithm
• Greatest common divisor
• List of polynomial topics
• Synthetic division

In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... This is a list of polynomial topics, by Wikipedia page. ... In mathematics, Ruffinis rule allows the rapid division of any polynomial by a binomial of the form x − r. ...

References

• Vedic Mathematics: Sixteen Simple Mathematical Formulae from the Vedas, by Swami Sankaracarya (1884-1960), Motilal Banarsidass Indological Publishers and Booksellers, Varnasi, India, 1965; reprinted in Delhi, India, 1975, 1978. 367 pages.