5

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

418
0
$$$$

多項式の割り算

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

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

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

整数係数多項式$f(x)$,$g(x)$(ただし、$g(x) \neq 0$)があり、$g(x)$は最高次の項の係数が$1$である。このとき、
$$ f(x)=g(x)q(x)+r(x) \qquad \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+2x+3$、余りは$4$となる。余りは$f(1)$となる。

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

命題2

命題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)$である。

命題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) \pmod m$であるとは、$f(x)-g(x)$の各項の係数が$m$の倍数であることとする。

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

命題4

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

命題5

$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$に対し、$(p-1)! \equiv -1 \pmod p$である。

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

この定理を示します。

定理6

$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$である。

おわりに

今回は合同世界での因数定理を利用してウィルソンの定理の定理を示しました。ウィルソンの定理の証明はこれだけではないので、興味のある方は、自分で考えてみたり、色々調べて見て下さい!

最後に、ウィルソンの定理が整数が素数であることの必要十分条件を与えている、ということを紹介しましょう。

$n>1$となる整数$n$において、$(n-1)! \equiv -1 \pmod n$であることと、$n$が素数であることは同値である。

最後までお読みいただきありがとうございました!

投稿日:2020117

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

魚鱈
魚鱈
8
1587
好きなキャラはカロン(Nintendo®の)

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中