# Divisibilty Among Polynomials

In the previous post, I demonstrated the beginnings of “divisibility theory”.  Here are some more formal ideas to support the example shown there.

First, it is necessary to establish some definitions.

Let _x_ be the representation of a vector called x.  For a variable c specified as a constant (or a literal constant, e.g. 0), let _c_ = [c, c, c, …, c] or _0_ = [0, 0, 0, …, 0].  Let the context supply the size of such a vector, such as “a polynomial p in k variables” followed by a reference to “p(_x_)” would imply that _x_ is of size k.

“Divisible under n” – the reasons for this term will become more clear with examples; an integer polynomial p in k variables (where k > 1) may be said to be “divisible under n” for a given integer n > 1 if and only if the only point where p(_x_) == 0 (mod n) is exactly when _x_ == _0_ (mod n).

(1) For every n such that n is prime or square-free, there exists a polynomial p in k variables such that p is divisible under n.

(2) For a given n, if a polynomial p exists such that there is exactly one solution p(_x_) == 0 (mod n) but _x_ != _0_ (mod n), then a polynomial q exists which is divisible under n.  It can be shown that q is a linear transform of p along each variable represented in _x_.

(3) For a given n, if a polynomial p exists such that there is exactly one solution p(_x_) == u (mod n), then p(_x_) – u (mod n) is a polynomial satisfying (2).