Greatest Common Divisors

The greatest common divisor (GCD) of two polynomials is the highest-degree polynomial that divides both without leaving a remainder. If $P\left(x\right)$ and $Q\left(x\right)$ share factors, computing the GCD reveals them. Otherwise the result is simply $1$. This concept generalizes the integer GCD to the polynomial ring.

Input Format

Specify each polynomial by listing coefficients from highest degree to constant term. For example, $P\left(x\right)=x^2-1$ should be written as "1,0,-1". The Euclidean algorithm divides the higher-degree polynomial by the lower one, replacing it with the remainder, and repeats until no remainder remains. The last nonzero remainder is the GCD.

Normalization

After each step we scale the polynomial so the leading coefficient becomes $1$. This keeps numbers manageable and mirrors the conventional monic GCD used in algebra.

Example

Suppose $P\left(x\right)=x^2-1$ and $Q\left(x\right)=x^3-x$. Factoring shows $P$ divides $Q$, so the GCD is $x^2-1$. Enter "1,0,-1" and "1,0,-1,0" to confirm.