合同世界での因数定理とウィルソンの定理

命題1より
$$ f(x)=(x-a)q(x)+r(x) \qquad \deg r(x) < \deg (x-a) $$を満たす多項式$q(x)$,$r(x)$が存在する。$\deg r(x) < \deg (x-a)$と$\deg (x-a) = 1$より、$\deg r(x) = 0$となり、$r(x)$が定数であることが分かる。$f(x)=(x-a)q(x)+r(x)$に$a$を代入すると、
$$ f(a) = r(a) $$となり、$r(x)$が定数であることから、
$$ r(x) = f(a) $$がいえる。よって、$f(x)$を$x-a$で割った余りは$f(a)$である。

$f(x)$が$x-a$で割り切れるとき、ある整数係数多項式$g(x)$があって、
$$ f(x)=g(x)(x-a) $$となる。$x$に$a$を代入すると$f(a)=0$が得られる。

逆に、$f(a)=0$とすると、命題2より、$f(x)$を$x-a$で割ったときの余りは$0$になる。よって、$f(x)$は$x-a$で割り切れる。

$f(x) \equiv g(x) \pmod m$より、$f(x)-g(x)$の各項の係数が$m$の倍数である。従って、$f(a)-g(a)$は$m$の倍数である。よって、$f(a) \equiv g(a) \pmod m$である。

$f(x) \equiv (x-a)g(x) \pmod m$なる整数係数多項式$g(x)$が存在するとする。このとき、両辺に$a$を代入すると、$f(a) \equiv 0 \pmod m$となる。

逆に、$f(a) \equiv 0 \pmod m$とする。命題2より
$$f(x) = (x-a)g(x)+f(a)$$なる整数係数多項式$g(x)$がある。$f(a) \equiv 0 \pmod m$より、
$$f(x) \equiv (x-a)g(x) \pmod m$$が分かる。

$p=2$のときは容易なので、$p$は奇数であるとする。
$f(x)=x^{p-1}-1$とおく。フェルマーの小定理より、$1^{p-1}-1\equiv 2^{p-1}-1 \equiv \cdots \equiv (p-1)^{p-1} \equiv 0 \pmod p$であるから、$f(1) \equiv f(2) \equiv \cdots \equiv f(p-1) \equiv 0 \pmod p$である。$f(1) \equiv 0 \pmod p$と命題5より、
$$ f(x) \equiv (x-1)g_1(x) \pmod p $$となる整数係数多項式$g_1(x)$が存在する。これに$2,3,\ldots,p-1$を代入すると、$g_1(2) \equiv g_1(3) \equiv \cdots \equiv g_1(p-1) \equiv 0 \pmod p$が分かる。$g_1(2) \equiv 0 \pmod p$と命題5より、
$$ g_1(x) \equiv (x-2)g_2(x) \pmod p $$となる整数係数多項式$g_2(x)$が存在する。この操作を繰り返すことで、
$$ f(x) \equiv (x-1)(x-2)\cdots(x-(p-1))g_{p-1}(x) \pmod p $$となる整数係数多項式$g_{p-1}(x)$の存在が分かる。左辺は$p-1$次のモニックなので、$g_{p-1}(x) \equiv 1 \pmod p$である。従って、
$$ x^{p-1}-1 \equiv (x-1)(x-2)\cdots(x-(p-1)) \pmod p $$である。$0$を代入すると、
$$ -1 \equiv (-1)(-2)\cdots(-(p-1)) \pmod p $$ $$ -1 \equiv (-1)^{p-1} \times 1 \times 2 \times \cdots \times (p-1) \pmod p $$ $$ (-1)^p \equiv 1 \times 2 \times \cdots \times (p-1) \pmod p $$ $$ (p-1)! \equiv (-1)^p \pmod p $$ $p$が奇数なので、$(p-1)! \equiv -1 \pmod p$である。