---
title: "PolynomialGCD"
language: "en"
type: "Symbol"
summary: "PolynomialGCD[poly1, poly2, ...] gives the greatest common divisor of the polynomials polyi. PolynomialGCD[poly1, poly2, ..., Modulus -> p] evaluates the GCD modulo the prime p."
keywords: 
- common roots
- GCD of polynomials
- greatest common divisor of polynomials
- HCF
- highest common factor
- polynomial GCD
- polynomial greatest common divisor
- Zippel's algorithm
- finduni
- gcd
canonical_url: "https://reference.wolfram.com/language/ref/PolynomialGCD.html"
source: "Wolfram Language Documentation"
related_guides: 
  - 
    title: "Polynomial Division"
    link: "https://reference.wolfram.com/language/guide/PolynomialDivision.en.md"
  - 
    title: "Theorem Proving"
    link: "https://reference.wolfram.com/language/guide/TheoremProving.en.md"
  - 
    title: "Polynomial Algebra"
    link: "https://reference.wolfram.com/language/guide/PolynomialAlgebra.en.md"
  - 
    title: "Finite Fields"
    link: "https://reference.wolfram.com/language/guide/FiniteFields.en.md"
related_functions: 
  - 
    title: "PolynomialLCM"
    link: "https://reference.wolfram.com/language/ref/PolynomialLCM.en.md"
  - 
    title: "PolynomialQuotient"
    link: "https://reference.wolfram.com/language/ref/PolynomialQuotient.en.md"
  - 
    title: "GCD"
    link: "https://reference.wolfram.com/language/ref/GCD.en.md"
  - 
    title: "Cancel"
    link: "https://reference.wolfram.com/language/ref/Cancel.en.md"
  - 
    title: "Together"
    link: "https://reference.wolfram.com/language/ref/Together.en.md"
  - 
    title: "PolynomialExtendedGCD"
    link: "https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.en.md"
  - 
    title: "PolynomialMod"
    link: "https://reference.wolfram.com/language/ref/PolynomialMod.en.md"
  - 
    title: "PolynomialReduce"
    link: "https://reference.wolfram.com/language/ref/PolynomialReduce.en.md"
  - 
    title: "PolynomialRemainder"
    link: "https://reference.wolfram.com/language/ref/PolynomialRemainder.en.md"
  - 
    title: "FiniteField"
    link: "https://reference.wolfram.com/language/ref/FiniteField.en.md"
related_tutorials: 
  - 
    title: "Algebraic Operations on Polynomials"
    link: "https://reference.wolfram.com/language/tutorial/AlgebraicManipulation.en.md#13694"
  - 
    title: "Polynomials Modulo Primes"
    link: "https://reference.wolfram.com/language/tutorial/AlgebraicManipulation.en.md#6923"
---
# PolynomialGCD

PolynomialGCD[poly1, poly2, …] gives the greatest common divisor of the polynomials polyi. 

PolynomialGCD[poly1, poly2, …, Modulus -> p] evaluates the GCD modulo the prime p.

## Details and Options

* In ``PolynomialGCD[poly1, poly2, …]``, all symbolic parameters are treated as variables.

* ``PolynomialGCD[poly1, poly2, …]`` will by default treat algebraic numbers that appear in the ``polyi`` as independent variables.

* ``PolynomialGCD`` takes the following options:

|            |       |                                                                  |
| ---------- | ----- | ---------------------------------------------------------------- |
| Extension  | None  | generators for the algebraic number field to be used             |
| Modulus    | 0     | modulus to assume for integers                                   |
| Trig       | False | whether to do trigonometric as well as algebraic transformations |

* ``PolynomialGCD[poly1, poly2, …, Extension -> Automatic]`` extends the coefficient field to include algebraic numbers that appear in the ``polyi``.

---

## Examples (21)

### Basic Examples (3)

Compute the greatest common divisor of polynomials:

```wl
In[1]:= PolynomialGCD[(1 + x) ^ 2(2 + x)(4 + x), (1 + x)(2 + x)(3 + x)]

Out[1]= (1 + x) (2 + x)
```

---

Compute the GCD of multivariate polynomials:

```wl
In[1]:= PolynomialGCD[(x + y) ^ 2(y + z), (x + y)(y + z) ^ 3]

Out[1]= (x + y) (y + z)
```

---

Show that polynomials are relatively prime:

```wl
In[1]:= PolynomialGCD[x ^ 2 + 4x + 4, x ^ 2 + 2x + 1]

Out[1]= 1
```

### Scope (10)

#### Basic Uses (4)

The GCD of univariate polynomials:

```wl
In[1]:= PolynomialGCD[x ^ 4 - 4, x ^ 4 + 4 x ^ 2 + 4]

Out[1]= 2 + x^2
```

---

The GCD of multivariate polynomials:

```wl
In[1]:= PolynomialGCD[x ^ 2 + 2 x y + y ^ 2, x ^ 3 + y ^ 3]

Out[1]= x + y
```

---

The GCD of more than two polynomials:

```wl
In[1]:= PolynomialGCD[x ^ 2 - 1, x ^ 3 - 1, x ^ 4 - 1, x ^ 5 - 1, x ^ 6 - 1, x ^ 7 - 1]

Out[1]= -1 + x
```

---

The GCD of polynomials with complex coefficients:

```wl
In[1]:= PolynomialGCD[x ^ 2 + 1, x ^ 3 + 3I x ^ 2 - 3x - I]

Out[1]= I + x
```

#### Advanced Uses (6)

With ``Extension -> Automatic``, ``PolynomialGCD`` detects algebraically dependent coefficients:

```wl
In[1]:= PolynomialGCD[x ^ 2 - 3, x - Sqrt[3], Extension -> Automatic]

Out[1]= Sqrt[3] - x
```

---

Compute the GCD of polynomials over the integers modulo $3$ :

```wl
In[1]:= PolynomialGCD[(x ^ 2 - 1) ^ 2, x ^ 3 - 1, Modulus -> 3]

Out[1]= (2 + x)^2
```

---

Compute the GCD of polynomials over a finite field:

```wl
In[1]:= ℱ = FiniteField[17, 3];

In[2]:= PolynomialGCD[ℱ[1]x ^ 2 + ℱ[246]x + ℱ[4436], ℱ[3]x ^ 2 + ℱ[1771]]

Out[2]= [image]
```

---

With ``Trig -> True``, ``PolynomialGCD`` recognizes dependencies between trigonometric functions:

```wl
In[1]:= PolynomialGCD[Sin[2x], 1 - Cos[x] ^ 2, Trig -> True]

Out[1]= Sin[x]
```

---

The GCD of rational functions:

```wl
In[1]:= PolynomialGCD[(x - 1)(x - 2) / ((x - 3)(x - 4)), (x - 1)(x - 5) / ((x - 3)(x - 6))]

Out[1]= (-1 + x/(-6 + x) (-4 + x) (-3 + x))
```

---

Compute the GCD of two polynomials of degree $20000$ :

```wl
In[1]:=
rpoly[n_] := RandomInteger[{-2 ^ 10, 2 ^ 10}, {n + 1}].x ^ Range[0, n]
SeedRandom[1234];
p = rpoly[10000]; q = rpoly[10000]; r = rpoly[10000];
pp = Expand[p r]; qq = Expand[q r];

In[2]:= (d = PolynomialGCD[pp, qq]);//AbsoluteTiming

Out[2]= {0.185276, Null}

In[3]:= Exponent[d, x]

Out[3]= 10000
```

### Options (3)

#### Extension (1)

By default, algebraic numbers are treated as independent variables:

```wl
In[1]:= PolynomialGCD[x ^ 2 - 2, x - Sqrt[2]]

Out[1]= 1
```

With ``Extension -> Automatic``, ``PolynomialGCD`` detects algebraically dependent coefficients:

```wl
In[2]:= PolynomialGCD[x ^ 2 - 2, x - Sqrt[2], Extension -> Automatic]

Out[2]= Sqrt[2] - x
```

#### Modulus (1)

Compute the GCD over the integers modulo 2:

```wl
In[1]:= PolynomialGCD[(x + 1) ^ 3, x ^ 3 + x, Modulus -> 2]

Out[1]= (1 + x)^2
```

#### Trig (1)

By default, ``PolynomialGCD`` treats trigonometric functions as independent variables:

```wl
In[1]:= PolynomialGCD[Sin[2x], 1 - Cos[x] ^ 2]

Out[1]= 1
```

With ``Trig -> True``, ``PolynomialGCD`` recognizes dependencies between trigonometric functions:

```wl
In[2]:= PolynomialGCD[Sin[2x], 1 - Cos[x] ^ 2, Trig -> True]

Out[2]= Sin[x]
```

### Applications (2)

Find common roots of univariate polynomials:

```wl
In[1]:=
f = x ^ 7 - 2x ^ 5 - x ^ 4 + 5x ^ 3 + 4x ^ 2 - 12x + 5;
g = x ^ 7 - 9x ^ 5 + x ^ 4 + 17x ^ 3 - 7x ^ 2 - 6x + 3;
d = PolynomialGCD[f, g]

Out[1]= 1 - 2 x + x^3

In[2]:= x /. Solve[d == 0, x]

Out[2]= {1, (1/2) (-1 - Sqrt[5]), (1/2) (-1 + Sqrt[5])}

In[3]:= Intersection[x /. Solve[f == 0, x], x /. Solve[g == 0, x]]

Out[3]= {1, (1/2) (-1 - Sqrt[5]), (1/2) (-1 + Sqrt[5])}
```

---

Find multiple roots of univariate polynomials:

```wl
In[1]:=
f = x ^ 9 - 7x ^ 8 + 19x ^ 7 - 27x ^ 6 + 35x ^ 5 - 77x ^ 4 + 145x ^ 3 - 157x ^ 2 + 88x - 20;
d = PolynomialGCD[f, D[f, x]]

Out[1]= -2 + 5 x - 4 x^2 + x^3

In[2]:= x /. Solve[d == 0, x]

Out[2]= {1, 1, 2}

In[3]:= N[x /. Solve[f == 0, x]]

Out[3]= {1., 1., 1., 2., 2., -1.06876 - 1.26889 I, -1.06876 + 1.26889 I, 1.06876 - 0.821224 I, 1.06876 + 0.821224 I}
```

### Properties & Relations (3)

The GCD of polynomials divides the polynomials; use ``PolynomialMod`` to prove it:

```wl
In[1]:=
f = x ^ 7 - 2x ^ 5 - x ^ 4 + 5x ^ 3 + 4x ^ 2 - 12x + 5;
g = x ^ 7 - 9x ^ 5 + x ^ 4 + 17x ^ 3 - 7x ^ 2 - 6x + 3;
d = PolynomialGCD[f, g]

Out[1]= 1 - 2 x + x^3

In[2]:= PolynomialMod[{f, g}, d]

Out[2]= {0, 0}
```

``Cancel`` divides the numerator and the denominator of a rational function by their GCD :

```wl
In[3]:= Cancel[f / g]

Out[3]= (5 - 2 x + x^4/3 - 7 x^2 + x^4)
```

``PolynomialLCM`` finds the least common multiple of polynomials:

```wl
In[4]:= PolynomialLCM[f, g]

Out[4]= (5 - 2 x + x^4) (3 - 6 x - 7 x^2 + 17 x^3 + x^4 - 9 x^5 + x^7)

In[5]:= % - (f g) / d //Together

Out[5]= 0
```

---

``Resultant`` of two polynomials is zero if and only if their GCD has a nonzero degree:

```wl
In[1]:= Resultant[x ^ 2 - 4, x ^ 2 + 4x + 4, x]

Out[1]= 0

In[2]:= PolynomialGCD[x ^ 2 - 4, x ^ 2 + 4x + 4]

Out[2]= 2 + x

In[3]:= Resultant[3 x + 9, 6x ^ 3 - 3x + 12, x]

Out[3]= -3807

In[4]:= PolynomialGCD[3 x + 9, 6x ^ 3 - 3x + 12]

Out[4]= 3
```

---

``Discriminant`` of a polynomial ``f`` is zero if and only if the degree of ``GCD(f, f')`` is nonzero:

```wl
In[1]:=
f = x ^ 3 - 3x + 2;
g = x ^ 3 - 2x + 1;

In[2]:= Discriminant[f, x]

Out[2]= 0

In[3]:= PolynomialGCD[f, D[f, x]]

Out[3]= -1 + x

In[4]:= Discriminant[g, x]

Out[4]= 5

In[5]:= PolynomialGCD[g, D[g, x], x]

Out[5]= 1
```

``Discriminant`` of a polynomial ``f`` is zero if and only if the polynomial has multiple roots:

```wl
In[6]:= x /. Solve[f == 0, x]

Out[6]= {-2, 1, 1}

In[7]:= x /. Solve[g == 0, x]

Out[7]= {1, (1/2) (-1 - Sqrt[5]), (1/2) (-1 + Sqrt[5])}
```

## See Also

* [`PolynomialLCM`](https://reference.wolfram.com/language/ref/PolynomialLCM.en.md)
* [`PolynomialQuotient`](https://reference.wolfram.com/language/ref/PolynomialQuotient.en.md)
* [`GCD`](https://reference.wolfram.com/language/ref/GCD.en.md)
* [`Cancel`](https://reference.wolfram.com/language/ref/Cancel.en.md)
* [`Together`](https://reference.wolfram.com/language/ref/Together.en.md)
* [`PolynomialExtendedGCD`](https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.en.md)
* [`PolynomialMod`](https://reference.wolfram.com/language/ref/PolynomialMod.en.md)
* [`PolynomialReduce`](https://reference.wolfram.com/language/ref/PolynomialReduce.en.md)
* [`PolynomialRemainder`](https://reference.wolfram.com/language/ref/PolynomialRemainder.en.md)
* [`FiniteField`](https://reference.wolfram.com/language/ref/FiniteField.en.md)

## Tech Notes

* [Algebraic Operations on Polynomials](https://reference.wolfram.com/language/tutorial/AlgebraicManipulation.en.md#13694)
* [Polynomials Modulo Primes](https://reference.wolfram.com/language/tutorial/AlgebraicManipulation.en.md#6923)

## Related Guides

* [Polynomial Division](https://reference.wolfram.com/language/guide/PolynomialDivision.en.md)
* [Theorem Proving](https://reference.wolfram.com/language/guide/TheoremProving.en.md)
* [Polynomial Algebra](https://reference.wolfram.com/language/guide/PolynomialAlgebra.en.md)
* [Finite Fields](https://reference.wolfram.com/language/guide/FiniteFields.en.md)

## History

* Introduced in 1991 (2.0) \| Updated in 1996 (3.0) ▪ [2022 (13.2)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn132.en.md) ▪ [2023 (13.3)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn133.en.md)