Polynomial Division and Factorization

Polynomial division algorithms including long division, exact division, and factorization capabilities such as square-free factorization, resultant, and discriminant computation.

📐

Mathematical Definition

Polynomial Long Division: For polynomials $f(x), g(x)$ with $\deg(g) \leq \deg(f)$ :

f(x) = g(x) \cdot q(x) + r(x)

where $q(x)$ is the quotient and $r(x)$ is the remainder with $\deg(r) < \deg(g)$ .

Resultant: The resultant $\text{Res}(f, g)$ of polynomials $f, g$ of degrees $m, n$ is:

\text{Res}(f, g) = a_n^m \cdot b_m^n \cdot \prod_{i,j} (\alpha_i - \beta_j)

where $\alpha_i, \beta_j$ are roots of $f, g$ respectively. Properties: - $\text{Res}(f, g) = 0 \iff f$ and $g$ share a common root - Computed as determinant of Sylvester matrix

Discriminant: For polynomial $f(x)$ of degree $n$ with leading coefficient $a_n$ :

\text{disc}(f) = \frac{(-1)^{n(n-1)/2}}{a_n} \cdot \text{Res}(f, f')

Properties: - $\text{disc}(f) = 0 \iff f$ has a repeated root - For quadratic $ax^2 + bx + c$ : $\text{disc} = b^2 - 4ac$

Code Examples

Polynomial Long Division

Compute quotient and remainder using standard division algorithm

use mathhook_core::core::polynomial::algorithms::polynomial_long_division;
use mathhook_core::{expr, symbol};

let x = symbol!(x);

// Divide (x^2 - 1) by (x - 1)
let dividend = expr!((x ^ 2) - 1);
let divisor = expr!(x - 1);

let (quotient, remainder) = polynomial_long_division(&dividend, &divisor, &x).unwrap();

// quotient = x + 1
// remainder = 0
// Verify: dividend = divisor * quotient + remainder

Exact Division

Division that errors if remainder is non-zero

use mathhook_core::core::polynomial::algorithms::exact_division;
use mathhook_core::{expr, symbol};

let x = symbol!(x);

// x^2 / x = x (exact)
let dividend = expr!(x ^ 2);
let divisor = expr!(x);

match exact_division(&dividend, &divisor, &x) {
    Ok(quotient) => println!("Exact quotient: {}", quotient),
    Err(e) => println!("Division not exact: {:?}", e),
}

Trait-Based Division

Use PolynomialArithmetic trait for ergonomic API

use mathhook_core::core::polynomial::PolynomialArithmetic;
use mathhook_core::{expr, symbol};

let x = symbol!(x);

let f = expr!((x ^ 3) - 1);
let g = expr!(x - 1);

// Returns (quotient, remainder)
let (q, r) = f.poly_div(&g, &x).unwrap();
// q = x^2 + x + 1
// r = 0

Polynomial Resultant

Test for common roots using resultant

use mathhook_core::core::polynomial::algorithms::polynomial_resultant;
use mathhook_core::{expr, symbol};

let x = symbol!(x);

// p1 = x - 1
let p1 = expr!(x - 1);
// p2 = x - 2
let p2 = expr!(x - 2);

let res = polynomial_resultant(&p1, &p2, &x).unwrap();
// Resultant is non-zero (distinct roots)

Polynomial Discriminant

Detect repeated roots using discriminant

use mathhook_core::core::polynomial::algorithms::polynomial_discriminant;
use mathhook_core::{expr, symbol};

let x = symbol!(x);

// (x - 1)^2 = x^2 - 2x + 1 (repeated root at 1)
let poly = expr!((x ^ 2) - (2 * x) + 1);

let disc = polynomial_discriminant(&poly, &x).unwrap();
// Discriminant = 0 (repeated root)

🔗 Related Topics

Browse All Topics

Explore the full documentation library