p を法として互いに合同でない整数のベキ乗

$p$ を法とする互いに合同でない集合

 今回も $a^k$ を $7$ で割ったときの余りを並べてみます。

 Excel 整数論 mod7位数表a5

 今回は $a^0$ から $a^{11}$ まで載せています。
 たとえば $a=5$ の列に着目すると、$7$ で割ったときの余りは

$5^0$ $5^1$ $5^2$ $5^3$ $5^4$ $5^5$ $5^6$ $5^7$ $5^8$ $5^9$ $5^{10}$ $5^{11}$
1 5 4 6 2 3 1 5 4 6 2 3

のように周期 $\mathrm{ord}_7(5)=6$ で並んでいます。つまり
 
\[5^0,\;5^1,\;5^2,\;5^3,\;5^4,\;5^5\]
は互いに合同ではなく、もし
 
\[5^m\equiv 5^n\quad (\mathrm{mod}\:7)\]
が成り立つのであれば、その周期から
 
\[m\equiv n\quad (\mathrm{mod}\:6)\]
が成り立ちます。たとえば
 
\[5^3\equiv 5^9\quad (\mathrm{mod}\:7)\]
が成り立っているので、
 
\[3\equiv 9\quad (\mathrm{mod}\:6)\]
が成り立つということです。これを一般的に述べたのが次の定理です。

[定理 E2]
 $p$ を素数、$a$ を正整数とします。$(a,\;p)=1$ のとき、$e=\mathrm{ord}_p(a)$ とおくと
\[a^0,\;a^1,\;a^2,\;\cdots,\;a^{e-1}\]は互いに合同ではなく、
\[a^m\equiv a^n\; (\mathrm{mod}\:p)\quad\Longleftrightarrow\quad m\equiv n\: (\mathrm{mod}\:e)\]

[定理 E2 の証明]
 $a^0,\;a^1,\;a^2,\;\cdots,\;a^{e-1}$ のなかに互いに合同な要素があったとして、それを
 
\[a^s\equiv a^t\;(\mathrm{mod}\:p)\quad (0\leq s\lt t\lt e)\]
とおくと、
 
\[a^{t-s}\equiv 1\;(\mathrm{mod}\:p)\quad (0\lt t-s\lt e)\]
となり、これは $e$ の最小性に反します。よって
 
\[a^0,\;a^1,\;a^2,\;\cdots,\;a^{e-1}\]
は互いに合同ではないことが示されました。また
 
\[m=e\,q_1+r_1\quad (0\leq r_1\lt e)\]
とおくと、$a^e\equiv 1\;(\mathrm{mod}\:p)$ より
 
\[a^m=a^{e\,q_1+r_1}=(a^e)^{q_1}a^{r_1}\equiv a^{r_1}\;(\mathrm{mod}\:p)\]
となります。同様に
 
\[n=e\,q_2+r_2\quad (0\leq r_2\lt e)\]
とおくと、$a^n\equiv a^{r_2}\;(\mathrm{mod}\:p)$ なので
 
\[a^m\equiv a^n\;(\mathrm{mod}\:p)\]
が成り立つときは
 
\[a^{r_1}\equiv a^{r_2}\;(\mathrm{mod}\:p)\]
も成り立つことになります。$r_1,\;r_2$ は
 
\[0\leq r_1\lt e,\quad 0\leq r_2\lt e\]
 すなわち、ともに位数 $e$ より小さい数なので、$a^{r_1}$ と $a^{r_2}$ が合同になるのは $r_1=r_2$ のときだけです。つまり $m$ と $n$ は $e$ で割ると余りが同じなので
 
\[m\equiv n\quad (\mathrm{mod}\:e)\]
が成り立ちます。(証明終) ≫ x k ≡ 1 (mod p) の解の個数 ≫ 初等整数論入門講座

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

コメントをどうぞ

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