https://tsujimotter.hatenablog.com/entry/20th-power-and-automorphic-number

早速ですが、前回書いた記事の続きです。
前回は「 $2^{100}$ の下２桁はいくつか」という問題を考えました。
tsujimotter.hatenablog.com

この問題は「 $\bmod{100}$ における $2^{100}$ 」を計算すればよく、さまざまなアプローチにより

$2^{100} \equiv 76 \pmod{100}$

と計算できるのでした。

ところで、この $76$ という数は自己同型数でもあるのでした。

自己同型数（Automorphic number）とは、ある $k$ が存在して

$x^2 \equiv x \pmod{10^k}$

が成り立つ $x$ のことです。

要するに、二乗した数と元の数の下 $k$ 桁が一致する数（二乗して元に戻ってしまう数）というわけですね。

$k = 2$ のとき $\bmod{100}$ の場合、自己同型数は $0, \; 1, \; 25, \; 76$ の4つだけであることが知られています。

そんなわけで $2^{100}$ が自己同型数であることがわかったわけですがこれは偶然なのかを考えたいと思います。これが今日のテーマです。

ところで、前回は $2^{100}$ を考えましたが、考えてみると20乗の段階で

$2^{20} \equiv 76 \pmod{100}$

なのでした。よって以降は $2^{20} \bmod{100}$ が自己同型数であるのはなぜかという点について考えたいと思います。

他の基数ではどうか？

さて、基数 $2$ が恣意的に選ばれていますので、 $3^{20}$ や他の基数も試してみたくなります。

$3^{20}$ は

$3^{20} = 34867844{\bf 01}$

となり、下2桁は 01 です。この $1$ という数も自己同型数なのでした。これは気になりますね。

一般的にはどうでしょうか。 $a = 0, 1, 2, \ldots, 99$ に対して、 $a^{20}\bmod{100}$ を計算してみます。結果は次のとおりです。

なんということでしょう！　自己同型数 $0, \; 1, \; 25, \; 76$ しか出てきません！　

$a$ が10の倍数のときは $0$ になるのは明らかです。
また、 $a$ が $100$ と互いに素の場合も、オイラーの定理やカーマイケルの定理によって $1$ になることが分かります。

問題は、互いに素ではない場合に必ず $25$ や $76$ になるという点です。これは何か裏があるに違いありません。

もう一つ気になるのは、すべての行で同じ数の並びになっている点です。

これは二項定理によって理解できます。 $a = 10k + b$ とすると

$\begin{align} a^{20} &= (10k + b)^{20} \\ &= (10k)^{20} + \binom{20}{1}(10k)^{19}b^{1} + \cdots + \binom{20}{18}(10k)^2b^{18} + \binom{20}{19}(10k)^1 b^{19} + b^{20} \end{align}$

となります。

ここで $(10k)^{20}$ の項から $\binom{20}{18}(10k)^2b^{18}$ の項までは明らかに $100$ の倍数なので、 $\bmod{100}$ で消えます。

また、 $\binom{20}{19}(10k)^1 b^{19}$ の項についても

$\binom{20}{19}(10k)^1 b^{19} = 200kn^{19} \equiv 0 \pmod{100}$

となり、 $\bmod{100}$ で消えます。

よって、 $\bmod{100}$ では最後の項だけが残り

$a^{20} \equiv b^{20} \pmod{100}$

となるわけですね。

以上で証明はできたわけですが、この件はあまり本題と関係がありません。

$a^{20}\bmod{100}$ のあまりは4通り

実は、今回の謎を解く手がかりは昔のブログ記事にありました。

tsujimotter.hatenablog.com
（こちらの記事は青山学院大学西山研究室の中川貴仁さんの卒業論文をきっかけに書いた記事でした。）

上の記事で示したことは、次の定理に集約されます：

定理

$m$ を任意の2以上の整数とし、 $r$ を $m$ の相異なる素因数の個数とする。すなわち

$m = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$

のとき、 $a^{\varphi(m)} \pmod{m}$ （あるいは、 $a^{\lambda(m)} \pmod{m}$ ）の値は $2^r$ 通りの数をとる

$\varphi(m)$ はオイラーのトーシェント関数で、 $\lambda(m)$ はカーマイケルの定理に登場する数論的関数です。

今回のケースに当てはめて考えると、 $m = 100 = 4 \times 25$ より次のように計算されます：

$\varphi(100) = \varphi(4) \cdot \varphi(25) = 2 \cdot 20 = 40$
$\lambda(100) = \operatorname{LCM}( \lambda(4), \; \lambda(25) ) = \operatorname{LCM}( 2, \; 20 ) = 20$

したがって、上の記事の定理を適用すると

$a^{40}\pmod{100}$ あるいは $a^{20}\pmod{100}$

の値は $4$ 通りの数をとることになります。
（このことは、今回の状況でも確かに成り立っていますね。）

問題は、その4通りの数が自己同型数になっているかどうかです。

上記の定理の証明を思い出す

実は、4通りの数が自己同型数になることは示せるのですが、そのためには上記の定理の証明を思い出す必要があります。

ここでは $m = 10^k = 2^k \cdot 5^k$ として、証明の概要を振り返りたいと思います。

証明のキモは中国剰余定理であり、

$\mathbb{Z}/10^k \mathbb{Z} \; \simeq \; \mathbb{Z}/2^k \mathbb{Z} \times \mathbb{Z}/5^k \mathbb{Z}$

なる環同型が重要です。この環同型を通して、 $a^{\varphi(m)}$ や $a^{\lambda(m)}$ を $\bmod{2^k}, \; \bmod{5^k}$ に送ったときに、どのような値になるのかを考えます。

以下簡単のため、 $f(m) = \varphi(m)$ または $f(m) = \lambda(m)$ としておきます。

$a$ が $2$ で割り切れる/割り切れない、 $a$ が $5$ で割り切れる/割り切れない、で4通りの場合わけが発生します。結論としては次が成り立ちます：

$a^{f(m)} \equiv \begin{cases} 0 \pmod{2^k} & (a\;\text{が2で割り切れる}) \\ 1 \pmod{2^k} & (a\;\text{が2で割り切れない}) \end{cases}$

$a^{f(m)} \equiv \begin{cases} 0 \pmod{5^k} & (a\;\text{が5で割り切れる}) \\ 1 \pmod{5^k} & (a\;\text{が5で割り切れない}) \end{cases}$

（この部分の計算は上に挙げた記事をご覧ください。）

よって、 $a^{f(m)}$ を $\mathbb{Z}/2^k \mathbb{Z} \times \mathbb{Z}/5^k \mathbb{Z}$ に送ったときの値としては

$(\overline{0}, \; \overline{0}), \;\; (\overline{0}, \; \overline{1}), \;\; (\overline{1}, \; \overline{0}), \;\; (\overline{1}, \; \overline{1})$

のいずれかの値をとります。

よって、環の同型により、この値を $\mathbb{Z}/10^k \mathbb{Z}$ に戻してきても、取りうる値は4通りというわけです。

これは自己同型数そのものではないか

さて、以上の証明の中で登場した $\mathbb{Z}/2^k \mathbb{Z} \times \mathbb{Z}/5^k \mathbb{Z}$ の中での取りうる値

$x = (\overline{0}, \; \overline{0}), \;\; (\overline{0}, \; \overline{1}), \;\; (\overline{1}, \; \overline{0}), \;\; (\overline{1}, \; \overline{1})$