Modular Mathematics, Unique Factorization of Polynomials

Unique Factorization of Polynomials

If p is prime, the polynomials in Zp[x] are subject to synthetic division. In other words, the smaller polynomial (by degree) can be divided into the larger, giving a quotient and remainder. Use modular division to divide the lead coefficients. This gives q, a number between 1 and p-1 that acts as the lead coefficient for the quotient. Multiply q by the divisor, shift, and subtract, similar to long division. Repeat this process until the degree of the dividend is less than the degree of the divisor. This is the remainder. Let's illustrate with x3+2x2+3x+4 divided by 5x+6 mod 7. 

 x3 + 2x2 + 3x + 4
                         1/5 = 3
-x3 - 4x2
      5x2 + 3x + 4
                         5/5 = 1
    - 5x2 - 6x
            4x + 4
                         4/5 = 5
          - 4x - 2
                 2

Quotient: 3x2+x+5, remainder 2

For efficiency, you might want to normalize the denominator, 5×(x+4) in the above example. Divide by x+4 first, and then by 5. There is no need for modular division at each step, since the dividend starts with 1. This can save time when the modulus has hundreds of digits, and the polynomials have thousands of terms.

since division is well defined, and the remainder is always smaller than the divisor, the gcd algorithm works for polynomials mod p. We may not be able to factor two large polynomials, but we can tell if they have any factors in common.

The gcd algorithm implies unique factorization, using the same proof as the integers.

This reasoning holds for the polynomials over any field, not just Zp. Polynomials over the rationals, the reals, or the complex numbers all exhibit unique factorization.

Next suppose f(x) is an integer polynomial taken from Z[x], having two different prime polynomial factorizations. Let s be the largest coefficient in any of the prime polynomials. Let k prime polynomials combine to form f. Let d be one more than the degree of the largest prime polynomial. As we multiply the prime polynomials together, we will never encounter a number larger than (ds)k. Select a prime p that is larger than this. Reduce everything mod p. All the coefficients are unchanged, since p is larger than all of them. In fact all the calculations proceed as before, since the numbers never exceed p. Now f factors two ways in Zp[x], which is impossible. Therefore the integer polynomials factor uniquely.

Note that the monomial x-r is prime in the integer or modular polynomials. Such a monomial is a factor of the polynomial f(x) iff r is a root, i.e. a solution, of f(x). If x-r is a factor, substitute to obtain r-r, or 0, as a factor, hence f(r) is 0. Conversely, let f(r) = 0 and write f = g×(x-r) + h, where g is the quotient polynomial and h is the remainder. When x = r, f(r) is 0, and x-r is also 0, so h is 0. Thus x-r divides f.

A polynomial of degree n cannot have more than n roots. That would imply more than n factors, which contradicts unique factorization.

As a corollary, there are at most n different nth roots of c. If there were more, then xn-c would have more than n roots, which is impossible, at least within the context of Zp. When working mod 7,1 2 and 4 are cube roots of 1, and there can be no others. Three is the limit.

The equation x2+1 = 0 has 6 roots in the quaternions. What goes wrong when multiplication is not commutative?

Given two polynomials q(x) and r(x), we can compute the left gcd g(x), so that sg = q and tg = r. Any other polynomial h(x) that left divides q and r also left divides g. However, the right gcd could be a completely different polynomial. There is not a well defined, two-sided gcd.

The proof that p divides ab implies p divides a or p divides b requires a traditional gcd, and without that, the proof of unique factorization cannot continue. Thus (x+i)×(x-i) = (x+j)×(x-j) = x2+1.

Without unique factorization, an equation like x2+1 could have lots of roots.