Proof
If
is a multiple of
, then we can write
-

with another polynomial
. Inserting
yields
-

In general, there exists, due to
fact,
a representation
-

where either
or the degree of
is
, so in both cases
is a constant. Inserting
yields
-

So if
holds, then the remainder must be
,
and this means
.