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

608

多項式の割り算

整数同士の和、差、積は整数となりますが、商、つまり割り算に関しては
$2 \nabla \cdot 3 = \frac{2}{3}$ というように整数の世界から飛び出してしまいます。しかし、
$11 \nabla \cdot 4 = 2 \dots 3$ というように、余りという概念を考えることが出来ました。これを、
$11 \equiv 3 (\mod 4)$ と書きます。これは、 $11$ と $3$ は $4$ で割った余りが等しいことを意味し、このような式を合同式といいます。

同様に、多項式同士の和、差、積は多項式になり、商に関しては多項式の世界から飛び出してしまいますが、多項式にも余りという概念が存在します。

多項式における除法の原理

整数係数多項式 $f (x)$ , $g (x)$ (ただし、 $g (x) \neq 0$ )があり、 $g (x)$ は最高次の項の係数が $1$ である。このとき、
$f (x) = g (x) q (x) + r (x) \deg r (x) < \deg g (x)$ を満たす整数係数多項式 $q (x)$ , $r (x)$ がただ一つ存在する。

命題1における $q (x)$ , $r (x)$ を、 $f (x)$ を $g (x)$ で割った時の商、余りと呼びます。
多項式 $f (x)$ に対し、 $\deg f (x)$ は $f (x)$ の次数を表します。つまり $f (x)$ は $\deg f (x)$ 次の多項式です。
最高次の項の係数が $1$ である多項式をモニックと呼びます。ここでは、 $g (x)$ はモニックです。
整数係数多項式で無い多項式(実数係数多項式など)についても同様な定理が成り立ちます(実数係数多項式の場合は $g (x)$ がモニックである必要はない)。

(命題1の証明は、ここでは省略します。)

因数定理

以下の定理が成り立ちます。

剰余の定理

$a$ を任意の整数とする。整数係数多項式 $f (x)$ を多項式 $x - a$ で割った余りは $f (a)$ である。

$f (x) = x^{3} + x^{2} + x + 1$ を $x - 1$ で割ると、商は $x^{2} + 2 x + 3$ 、余りは $4$ となる。余りは $f (1)$ となる。

このように、剰余の定理を用いることで、簡単に余りを求めることができます。
では、この命題を証明しましょう。証明に命題1を用います。

命題2

命題1より
$f (x) = (x - a) q (x) + r (x) \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)$ である。

命題2より次の命題が導かれます。

因数定理

$a$ を整数とする。整数係数多項式 $f (x)$ が $x - a$ で割り切れることと、 $f (a) = 0$ であることは同値である。

命題3

$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) = x^{3} + x^{2} + x + 1$ とする。 $f (- 1) = 0$ より、 $f (x)$ は $x + 1$ で割り切れる。
実際、 $f (x) = (x^{2} + 1) (x + 1)$ である。

合同世界での因数定理

多項式同士の合同式を以下の通りに定義します。

多項式の合同

整数係数多項式 $f (x)$ , $g (x)$ と正の整数 $m$ に対し、 $f (x) \equiv g (x) (\mod m)$ であるとは、 $f (x) - g (x)$ の各項の係数が $m$ の倍数であることとする。

整数係数多項式 $f (x)$ , $g (x)$ と正の整数 $m$ に対し、 $f (x) \equiv g (x) (\mod m)$ であるとき、任意の整数 $a$ に対し、 $f (a) \equiv g (a) (\mod m)$ である。

命題4

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

実は、合同式の世界における因数定理というものが成り立ちます。

合同世界での因数定理

$f (x)$ を整数係数多項式、 $m$ を正の整数とし、 $a$ を整数とする。このとき、 $f (x) \equiv (x - a) g (x) (\mod m)$ なる整数係数多項式 $g (x)$ が存在することと、 $f (a) \equiv 0 (\mod m)$ であることは同値である。

命題5

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

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

この命題を用いて、ウィルソンの定理を証明することができます。

ウィルソンの定理

ウィルソンの定理とは以下のような定理のことです。

ウィルソンの定理

素数 $p$ に対し、 $(p - 1)! \equiv - 1 (\mod p)$ である。

$p = 2$ のとき、 $(p - 1)! = 1 \equiv - 1 (\mod 2)$
$p = 3$ のとき、 $(p - 1)! = 2 \equiv - 1 (\mod 3)$
$p = 5$ のとき、 $(p - 1)! = 24 \equiv - 1 (\mod 5)$
$p = 7$ のとき、 $(p - 1)! = 720 \equiv - 1 (\mod 7)$

この定理を示します。

定理6

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