Polynomial long division and the Euclidean algorithm

Divides two polynomials with remainder, and finds their greatest common divisor via the polynomial Euclidean algorithm – exactly the integer Euclidean algorithm with polynomial division in place of integer division.

from mathematicskit.abstract_algebra import Polynomial, poly_divmod, poly_gcd, poly_mul

Divide x^3 - 1 by x - 1

p = Polynomial([-1, 0, 0, 1])  # x^3 - 1
q = Polynomial([-1, 1])  # x - 1
quotient, remainder = poly_divmod(p, q)
print(f"(x^3 - 1) / (x - 1) = quotient {quotient.coeffs}, remainder {remainder.coeffs}")
print(f"check: quotient * (x-1) + remainder = {(poly_mul(quotient, q) + remainder).coeffs}")

(x^3 - 1) / (x - 1) = quotient [Fraction(1, 1), Fraction(1, 1), Fraction(1, 1)], remainder [Fraction(0, 1)]
check: quotient * (x-1) + remainder = [Fraction(-1, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1)]

GCD of x^4 - 1 and x^6 - 1

a = Polynomial([-1, 0, 0, 0, 1])  # x^4 - 1
b = Polynomial([-1, 0, 0, 0, 0, 0, 1])  # x^6 - 1
g = poly_gcd(a, b)
print(f"\ngcd(x^4 - 1, x^6 - 1) has degree {g.degree}, coefficients {g.coeffs}")

gcd(x^4 - 1, x^6 - 1) has degree 2, coefficients [Fraction(-1, 1), Fraction(0, 1), Fraction(1, 1)]