p-1 の約数に等しい位数は必ず存在します

p-1 の約数に等しい位数は必ず存在します

 いつものように素数 $\mathrm{mod}\:7$ のベキ乗表です。

 Excel 数論 mod7の表で位数を調べる

 $7-1=6$ の約数は $1,\;2,\;3,\;6$ ですが、表を見ると、それぞれの約数に等しい位数が存在していることがわかります。すなわち法 $7$ において、最小べき指数で $1$ と合同になる $a$ を分類してみると

$\mathrm{ord}_p(a)=1$  $a=1\;$   ($\varphi(1)=1$ 個)
$\mathrm{ord}_p(a)=2$  $a=6\;$   ($\varphi(2)=1$ 個)
$\mathrm{ord}_p(a)=3$  $a=2,\;4$  ($\varphi(3)=2$ 個)
$\mathrm{ord}_p(a)=6$  $a=3,\;5$  ($\varphi(6)=2$ 個)

のようになります。また個数については、オイラー関数で $\varphi(d)$ 個のように表されていますが、これは偶然ではないことが以下の定理によって示されます。

[定理 E5] 素数 $p$ を法として、$p-1$ の任意の正の約数 $d$ に等しい位数をもつ整数 $a$、すなわち
\[\mathrm{ord}_p(a)=d\]を満たす整数 $a$ は必ず存在し、
\[1,\;2,\;\cdots,\;p-1\]のなかに $\varphi(d)$ 個あります。

[定理 E5 の証明] 位数 $d$ である数 $a$ が存在すると仮定します。
 
\[\mathrm{ord}_p(a)=d\]
 すなわち $a$ のべきをつくっていくと
 
\[\{\:a^0,\;a^1,\;a^2,\;\cdots,\;a^k,\;\cdots,\;a^{d-1},\;a^d\:\}\]
となって $a^d$ のときに初めて $1$ と合同になります。ところが
 
\[\{\:a^0,\;a^1,\;a^2,\;\cdots,\;a^k,\;\cdots,\;a^{d-1}\:\}\tag{1}\]
もすべて $d$ 乗すると
 
\[(a^k)^d=(a^d)^k\equiv 1\quad (\mathrm{mod}\:p)\]
となるので、これらは位数 $d$ の候補です ($d$ が 1 と合同になる最小のべき指数とは限りません)。もちろん仮定によって $a$ の位数は $d$ ですが、他にもあるかもしれないということです。また (1) は 定理 E2 より法 $p$ に関して互いに合同ではありません。さらに (1) は合同方程式
 
\[x^d\equiv 1\quad (\mathrm{mod}\:p)\]
の根となっています。この合同方程式の 解の個数は d 個を超えない ので、(1) 以外に $d$ 乗して $1$ と合同になる数はありません。(1) の各要素の位数は 定理 E4 より、
 
\[\mathrm{ord}_p(a^k)=\frac{\mathrm{ord}_p(a)}{(\mathrm{ord}_p(a),\:k)}=\frac{d}{(d,\:k)}\]
なので、位数が $d$ となるのは
 
\[(d,\:k)=1\]
を満たす $k$ に対応する $a^k$ だけです。
 
\[(d,\:1),\;(d,\:2),\:\cdots,\:(d,\,d-1)\]
の中から $1$ となるものだけを抜き出すので、その個数はオイラーの関数を用いて $\varphi (d)$ で表されます。ここまでの議論で
 
\[\mathrm{ord}_p(a)=d\]
を満たす $a$ があると仮定してきましたが、もしかすると存在しないかもしれません。そこで $p$ を法として位数 $d$ である数の個数を $\psi(d)$ とすると、

$\psi(d)=\varphi(d)$ または $\psi(d)=0$

のどちらかです。これは $p-1$ の約数を $d_1,\;d_2,\;d_3,\;\cdots$ とすれば、たとえば
 
\[\begin{align*}&\psi(d_1)=\varphi(d_2)\\[6pt]
&\psi(d_2)=0\\[6pt]
&\psi(d_3)=\varphi(d_3)\\[6pt]
&\cdots\cdots\cdots\cdots\cdots\end{align*}\]
のように、約数によって、その約数に等しい位数があったりなかったりするかもしれないということです。しかし $\mathrm{ord}_p(a)\:|\:p-1$(こちらの記事を参照してください)より、$1$ から $p-1$ までの数はそれぞれが $p-1$ の約数のうちいずれかを位数とするので、
 
\[\sum_{d|p-1}\psi(d)=p-1\]
が成り立っているはずです。またオイラーの関数についても
 
\[\sum_{d|p-1}\varphi(d)=p-1\]
が成り立ちます。もしある $d$ について $\psi(d)=0$ であれば
 
\[\sum_{d|p-1}\psi(d)\lt\sum_{d|p-1}\varphi(d)\]
となってしまうので不合理です。よって任意の正の約数 $d$ に等しい位数をもつ整数 $a$ は必ず存在し、その個数は $\varphi(d)$ です。(証明終)

 ≫ 素数の原始根 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください