Suppose you have a monic polynomial (the leading coefficient is $1$) and you know that the polynomial has integer roots. We will consider two approaches to authoring such algorithms.

Algorithm A: Factoring a quadratic polynomial with integer roots

Given the polynomial $x^2 - x - 12$, then if this equals $(x - m)(x - n)$, the product of the roots must be $mn = -12$ and the sum of the roots $-(m + n) = -1$. Now, if the roots are integers, we note that the prime decomposition of $12$ is $12 = 2^2 \cdot 3$.

Thus, we need only consider all possible pairs of roots, one of which must be negative:

Possible roots $(s, t)$	$-(s + t)$
$ 1, -12$	$11$
$-1, 12$	$-11$
$ 2, -6$	$4$
$-2, 6$	$-4$
$ 3, -4$	$1$
$-3, 4$	$-1$

Thus, the roots are $-3$ and $4$, and $x^2 - x - 12 = (x + 3)(x - 4)$.

Describe this algorithm to find both roots of quadratic polynomial with integer coefficients.

Algorithm B: Factoring a polynomial with negative integer roots

Suppose a polynomial has all roots being negative integers. In this case, the product of the negated roots must be the constant coefficient and the negated sum of the roots must be the constant coefficient. With this, it may be much simpler to factor the polynomial:

$-1, -1, -6$

$-1, -2, -3$

Such situations are very common in engineering, as you will see in second year when you study differential equations and stability in systems.

Algorithm C: Factoring a polynomial with integer roots

If the roots may be positive or negative integers, it requires much more significant work, as there are now many more roots to consider. Suppose, for example, that the constant coefficient was $-6$. In this case, if all the roots are integers, we must somehow enumerate and the following possibilities:

$(x + 1)(x + 1)(x - 6)$
$(x + 1)(x - 1)(x + 6)$
$(x - 1)(x - 1)(x - 6)$
$(x + 1)(x + 2)(x - 3)$
$(x + 1)(x - 2)(x + 3)$
$(x - 1)(x + 2)(x + 3)$
$(x - 1)(x - 2)(x - 3)$

This may become tedious, and it will become more tedious as the number of prime factors of the constant coefficient increases. Thus, an alternative is to consider all divisors of the constant coefficient, and then perform polynomial division, trying to divide the polynomial by the given monomial $x - n$ and see if there is a zero remainder. If there is, we have found a root and we try again.

Describe this algorithm formally.