$p$ を法とする互いに合同でない集合
今回も $a^k$ を $7$ で割ったときの余りを並べてみます。
今回は $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)\]
が成り立つということです。これを一般的に述べたのが次の定理です。
$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) の解の個数 ≫ 初等整数論入門講座