2014/11/10

位数の性質と原始根の応用

分野: 整数問題  レベル: 数学オリンピック

位数の性質:$\mathrm{mod}\:p$ における $a$ の位数を $n$ とする。
$a^m\equiv 1\:\mathrm{mod}\:p$ を満たすなら $m$ は $n$ の倍数である。

位数や原始根の話題は高校範囲を逸脱しますが,整数論の様々な定理の証明に役立ちます。上記の性質は特によく使うものです。

位数の定義と原始根

この記事を読み進めるために必要な前提知識の確認です。

  • $a^n\equiv 1\:\mathrm{mod}\:p$ となる最小の正の整数 $n$ を法 $p$ における $a$ の位数と呼びます。
  • 素数 $p$ に対して位数が $p-1$ であるような元 $r$ のことを $p$ の原始根と呼びます。素数 $p$ には原始根 $r$ が必ず存在します。
  • 素数 $p$ に対する原始根を $r$ とすると,$r,\:r^2,\cdots,\:r^{p-1}$ を $p$ で割った余りは全て異なり $1$ から $p-1$ までを一巡します。

初見の方はこれだけではよく分からないと思うので,原始根の定義と具体例(高校生向け)も参照してください。

位数の性質

冒頭の性質を証明します!丸暗記してもよいくらい重要な証明方法です。

方針:$a$ の位数が $n$ なので,位数の定義より以下の二つを使うことになります。
条件1:$a,\:a^2,\cdots,\:a^{n-1}$ は $p$ で割った余りが $1$ ではない。
条件2:$a^n$ は $p$ で割った余りが $1$ である。
そして,$m$ が $n$ の倍数であることを証明するのが目標なので,$m$ を $n$ で割った余りを考えてそれが $0$ と一致することを証明します(倍数であることを証明するときによく使う手法)。

証明

$m$ を $n$ で割った商を $Q$,余りを $R$ とおく。
$1\equiv a^m=a^{nQ+R}=(a^{n})^Qa^R\equiv 1^Qa^R=a^R\:\mathrm{mod}\:p$
途中で条件2を用いた。これより $a^R\equiv 1\:\mathrm{mod}\:p$
ここで,$R$ は余りなので $0\leq R< n$ だが,もし $R\neq 0$ と仮定すると,上式は条件1に矛盾する。よって $R=0$ となり題意は示された。

原始根の応用

位数の性質と原始根の応用例としてウィルソンの定理をエレガントに証明します。

任意の素数 $p$ に対して$(p-1)!\equiv -1\:\mathrm{mod}\:p$ を示すのが目標です。 $p=2$ のときは確かに正しいので $p$ が奇素数の場合を証明します。

証明

素数 $p$ の原始根 $r$ をとってくる。つまり,$r$ の位数は $p-1$ である。すると,$r,\:r^2,\cdots,\:r^{p-1}$ を $p$ で割った余りは全て異なり $1$ から $p-1$ までを一巡するので,
$r\cdot r^2\cdots r^{p-1}\equiv 1\cdot 2\cdots p-1\:\mathrm{mod}\:p$
よって,$r^m\equiv (p-1)!\:\mathrm{mod}\:p\:$(※)となる。ただし,$m=1+2+\cdots + (p-1)=\frac{p(p-1)}{2}$

一方,フェルマーの小定理より,$r^{2m}=r^{p(p-1)}\equiv 1\:\mathrm{mod}\:p$ なので,
$(r^m-1)(r^m+1)$ は $p$ の倍数。

もし,$r^m\equiv 1\:\mathrm{mod}\:p$ と仮定すると,位数の性質より $m$ は $p-1$ の倍数である。よって,$\dfrac{m}{p-1}=\dfrac{p}{2}$ は整数でなければならないが、これは $p$ が奇数であることに矛盾。

よって,$r^m\equiv -1\:\mathrm{mod}\:p$ である。(※)と合わせてウィルソンの定理が証明された。

そういえば明日はポッキーの日ですね。
分野: 整数問題  レベル: 数学オリンピック