整数論の問題

方針 位数は $\phi (23)$ の約数です。そこで、$\phi (23)$ の約数を小さい順に調べていきます。

手順 1: 調べる候補を絞る

$23$ は素数なので $\phi (23)=22$ です。$\gcd (2,23)=1$ ですから、フェルマーの小定理より
$$2^{22}\equiv 1(\mathrm{mod}23)$$
が成り立ちます。

「$a^k\equiv 1⟺{\mathrm{ord}}_{23}(a)\mid k$」という性質を $k=22$ に使うと、${\mathrm{ord}}_{23}(2)$ は $22$ の約数です。したがって、候補は
$$1,2,11,22$$
の 4 つだけです。

手順 2: 候補を小さい順に確かめる

- $2^1=2\not\equiv 1$
- $2^2=4\not\equiv 1$
- $2^{11}$ は次のように計算します。
$$2^5=32\equiv 9,2^{10}=(2^5{)}^2\equiv 9^2=81=3\cdot 23+12\equiv 12,$$
$$2^{11}=2^{10}\cdot 2\equiv 12\cdot 2=24\equiv 1(\mathrm{mod}23).$$

結論 $2^k\equiv 1$ となる最小の候補は $k=11$ です。よって
$${\mathrm{ord}}_{23}(2)=11$$
です。

位数は $\phi (23)=22$ の約数であるから、候補は $1,2,11,22$ である。
$2^1=2\not\equiv 1$、$2^2=4\not\equiv 1$ である。
$2^{11}$ を計算する。$2^5=32\equiv 9$、$2^{10}\equiv 81=69+12\equiv 12$、$2^{11}\equiv 24\equiv 1(\mathrm{mod}23)$。
よって $2^{11}\equiv 1$ である。
約数 $1,2$ では $1$ にならないので、最小の $k$ は $11$ である。
検算: $2^{11}=2048=23\cdot 89+1$ （$23\cdot 89=2047$）なので $2^{11}\equiv 1$ が確かめられる。