Thanks for the reason why x^2 + 7=0 mod 8 can have 4 solutions. I didn't know that.

]]>This can be proved using the equivalent of the division algorithm for polynomials over a field.

A simple proof of this using induction on the degree of

can be found on p.28 of D.J.H. Garling,Note that this applies to polynomials over a field only. This wont work with rings in general, e.g.

and in . However, if is an integral domain, we can apply the division algorithm to polynomials over its field of fractions .Let

be a polynomial of degree in . Let be a root of Considering as a polynomial in , we can write where and . Then .Thus

. If is another root of distinct from , write where and . Then as .Thus

. Continuing this way, we find that if are all the distinct roots of , then we have for some . It follows that cannot have more than roots in since has degree and so cannot be factorized into more than linear factors in . And since a root of polynomial in is also a root of a polynomial in (Gausss lemma), our proof is complete.If

is not an integral domain, it may be possible for an th-degree polynomial in to have more than roots. For instance, as a polynomial over , the quadratic polynomial actually has 4 roots, namely 1, 3, 5, 7. Thats because is not an integral domain and so we cannot construct its field of fractions.]]>