整数のベキ乗の位数を計算する公式

 合同計算の復習も兼ねて、$7$ を法とする $3^4$ の位数を求めてみます。
 
\[3^4\equiv 4\quad (\mathrm{mod}\:7)\tag{1}\]
はすぐにわかるので、両辺を 2 乗して
 
\[(3^4)^2\equiv 16\quad (\mathrm{mod}\:7)\]
 $16\equiv 2\;(\mathrm{mod}\:7)$ なので
 
\[(3^4)^2\equiv 2\quad (\mathrm{mod}\:7)\tag{2}\]
 (1) と (2) を辺々掛けて
 
\[(3^4)^3\equiv 8\equiv 1\quad (\mathrm{mod}\:7)\]
となるので、$3^4$ は 3 乗して初めて $1$ と合同になることがわかります。よって $3^4$ の位数は
 
\[\mathrm{ord}_7(3^4)=3\]
となります。
 

整数のベキ乗の位数を計算する公式

 上の例では比較的簡単に位数を求めることができましたが、場合によってはなかなか $1$ と合同にならないこともあります。また、あまり大きな $a$ の位数は位数表にも載っていません。そこで $a$ の位数を用いて $a^k$ の位数を計算する公式を導いておきます。

[定理 E4] $p$ を素数とするとき
\[\mathrm{ord}_p(a^k)=\frac{\mathrm{ord}_p(a)}{(\mathrm{ord}_p(a),\:k)}=\frac{d}{(d,\:k)}\] ただし $d=\mathrm{ord}_p(a)$ とします。

[定理 E4 の証明] $e=\mathrm{ord}_p(a^k),\:\:f=(d,\:k)$ とすると
 
\[d=fd',\:\:k=fk'\]
のように書けて
 
\[(d',\:k')=1\]
となります。$e=\mathrm{ord}_p(a^k)$ より
 
\[a^{ke}\equiv 1\quad (\mathrm{mod}\:p)\]
が成り立つので
 
\[d\:|\:ke\quad\Longleftrightarrow\quad fd'\:|\:efk'\quad\Longleftrightarrow\quad d'\:|\:ek'\]
 $(d',\:k')=1$ より $d'\:|\:e$ となります。
 また、$d=fd',\:\:k=fk'$ より $dk'=kd'$ なので
 
\[(a^k)^{d'}=(a^d)^{k'}\equiv 1\quad (\mathrm{mod}\:p)\]
 $e=\mathrm{ord}_p(a^k)$ なので $e\:|\:d'$ となります。
 $d'\:|\:e$ かつ $e\:|\:d'$ なので、
 
\[e=d'=\frac{d}{f}=\frac{d}{(d,\:k)}=\frac{\mathrm{ord}_p(a)}{(\mathrm{ord}_p(a),\:k)}\]
が成立します。(証明終)

 位数表 などから $\mathrm{ord}_7(3)=6$ を既知として、冒頭で計算した $\mathrm{ord}_7(3^4)$ を定理 E4 を用いて計算してみると
 
\[\mathrm{ord}_7(3^4)=\frac{\mathrm{ord}_7(3)}{(\mathrm{ord}_7(3),\:4)}=\frac{6}{2}=3\]
となります。 ≫ p-1 の約数に等しい位数 ≫ 初等整数論入門講座

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

コメントをどうぞ

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

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