べきの塔の剰余

$2^{2^{2^{\cdot^{\cdot}}}}$ のようなべきの塔を、オイラーの定理で指数の法を $φ$ に順に下げて計算し、 $A (4, 3) = 2^{2^{65536}} - 3$ を $1000$ で割った余りのような値を求められる

前提

アッカーマン関数の値（大学院数学計算理論・ラムダ計算）
剰余類環の単元群とオイラー関数（大学数学代数学）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
互いに素な法への分解（数学A 整数の性質）

この技能までの道筋（34 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
等差数列・等比数列の一般項（数学B 数列）
数学的帰納法と一般項の推定（数学B 数列）
原始再帰的定義と関数の値（大学院数学計算理論・ラムダ計算）
アッカーマン関数の値（大学院数学計算理論・ラムダ計算）
約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
有限アーベル群の構造と部分群の個数（大学数学代数学）
剰余類環の単元群とオイラー関数（大学数学代数学）
n 進法（数学A 整数の性質）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
互いに素な法への分解（数学A 整数の性質）

説明

$2^{2^{2^{2^{2^{2}}}}}$ のように指数が何段も積み重なった数（べきの塔）は、桁数すら書き下せないほど巨大ですが、ある数 $n$ で割った余りなら手で求められます。鍵は、底と互いに素な法 $m$ では指数を $φ (m)$ で割った余りに置きかえてよいことです。指数そのものもまたべきの塔なので、法を $n \to φ (\cdot) \to φ (φ (\cdot)) \to \dots$ と順に下げながら計算します。 $A (4, 3) = 2^{2^{65536}} - 3$ のようなアッカーマン関数の値の下数桁を求めるときなどに使います。

なぜそうしてよいのか

法 $m$ と底 $a$ が互いに素なら、 $a$ の余りは単元群 $(Z / m Z)^{\times}$ の元です。この群の位数は $φ (m)$ で、元の位数は群の位数を割り切るので $a^{φ (m)} \equiv 1 (mod m)$ （オイラーの定理）が成り立ちます。すると $e = q φ (m) + r$ （ $0 \leq r < φ (m)$ ）と書けば $a^{e} = (a^{φ (m)})^{q} a^{r} \equiv a^{r} (mod m)$ となり、 $a^{e} mod m$ は指数 $e$ を $φ (m)$ で割った余り $r$ だけで決まります。つまり巨大な指数 $e$ は「 $e mod φ (m)$ 」さえわかればよく、その $e$ がまたべきの塔なら、同じ考えを法 $φ (m)$ で繰り返せばよいのです。 $m \geq 2$ なら $φ (m) < m$ なので法はどんどん小さくなり、数段で $1$ や $2$ に達して計算が止まります（法 $1$ ではどんな数も余り $0$ ）。

底と法が互いに素でないとき（底 $2$ と法 $1000$ など）はオイラーの定理をそのまま使えません。そこで法を $n = 2^{k} m$ （ $m$ は奇数）と互いに素な数の積に分けます。 $2^{k}$ の部分では、 $2^{e} = 2^{k} \cdot 2^{e - k}$ と書けるので、指数が $e \geq k$ のときに限り $2^{e} \equiv 0 (mod 2^{k})$ です。 $e < k$ なら $2^{e} < 2^{k}$ でこれ自身が余りになり、 $0$ にはなりません。たとえば $2^{2} = 4$ は法 $8 = 2^{3}$ では指数 $2 < 3$ なので余り $4$ のままです。したがって「 $e \geq k$ か」はどの段でも毎回確かめます。確かめるのは難しくありません。 $2$ だけの塔は段数を $1$ 増やすごとに $x \mapsto 2^{x}$ を施すので、 $2, 2^{2} = 4, 2^{4} = 16, 2^{16} = 65536, \dots$ と増えていき、 $3$ 段以上の塔なら指数は $16$ 以上、 $4$ 段以上なら $65536$ 以上です。手計算で扱う法の $k$ （ $1000 = 2^{3} \cdot 125$ なら $k = 3$ ）はこれらよりずっと小さいので、塔がその高さを超えていることを示せば条件が確かめられます。 $m$ の部分は $g cd (2, m) = 1$ なので上の指数の置きかえが使えます。最後に中国剰余定理で 2 つの余りを 1 つにまとめます（底が奇素数 $p$ で $n$ が $p$ を含むときも、同様に $p^{k}$ の部分を分けて $e \geq k$ を確かめます）。

手順

塔を上から読み、上の小さな段はそのまま計算しておく（例: $2^{2^{2}} = 2^{4} = 16$ ）。塔は右上から結合する: $a^{b^{c}} = a^{(b^{c})}$
法 $n$ を、底と共通の素因数をもつ部分 $p^{k}$ と、底と互いに素な部分 $m$ に分ける: $n = p^{k} m$
$p^{k}$ の部分: 指数 $e$ が $e \geq k$ を満たすことを具体的な値の下限（例: 指数が $2^{16} = 65536$ 以上）で確かめてから $p^{e} \equiv 0 (mod p^{k})$ とする。 $e < k$ なら $p^{e}$ がそのまま余り
$m$ の部分: 指数 $e$ を $φ (m)$ で割った余り $r$ を求める。 $e$ 自身がべきの塔なら、法 $φ (m)$ に対してこの手順全体を（法が小さくなるまで）繰り返す
$a^{r} mod m$ を繰り返し二乗法などで計算する: $a^{e} \equiv a^{r} (mod m)$
中国剰余定理で $p^{k}$ と $m$ の余りをまとめ、 $n$ で割った余りを得る

例題

$T = 2^{2^{2^{2^{2^{2}}}}}$ （ $2$ が $6$ 個並んだべきの塔）を $100$ で割った余りを求めよ。

例題の解答

【手順 1】上の段から計算すると $2^{2} = 4$ , $2^{4} = 16$ , $2^{16} = 65536$ なので $T = 2^{E}$ , $E = 2^{65536}$ である。

【手順 2】 $100 = 4 \times 25 = 2^{2} \times 25$ と分ける（ $g cd (2, 25) = 1$ ）。

【手順 3】法 $4 = 2^{2}$ （ $k = 2$ ）: 指数 $E = 2^{65536} \geq 65536 \geq 2$ を確かめたので $T = 2^{E} \equiv 0 (mod 4)$ 。

【手順 4】法 $25$ : $φ (25) = 20$ なので $E mod 20$ が必要。 $E = 2^{65536}$ について、法 $20 = 2^{2} \times 5$ で同じ手順を繰り返す。
- 法 $4$ （手順 3）: 指数 $65536 \geq 2$ なので $E = 2^{65536} \equiv 0 (mod 4)$ 。
- 法 $5$ （手順 4・5）: $φ (5) = 4$ なので指数 $65536 = 2^{16}$ を $4$ で割った余りが必要。 $16 \geq 2$ より $2^{16} \equiv 0 (mod 4)$ 。よって $2^{4} = 16 \equiv 1 (mod 5)$ を使って $E = 2^{65536} \equiv 2^{0} = 1 (mod 5)$ 。
- （手順 6） $E \equiv 0 (mod 4)$ , $E \equiv 1 (mod 5)$ を満たす $0 \leq E < 20$ の値は $0, 4, 8, 12, 16$ のうち $5$ で割って $1$ 余る $16$ 。よって $E \equiv 16 (mod 20)$ 。

【手順 5】 $T = 2^{E} \equiv 2^{16} (mod 25)$ 。 $2^{10} = 1024 \equiv - 1$ , $2^{6} = 64 \equiv 14$ より $2^{16} \equiv - 14 \equiv 11 (mod 25)$ 。

【手順 6】 $T \equiv 0 (mod 4)$ , $T \equiv 11 (mod 25)$ 。 $11, 36, 61, 86$ のうち $4$ の倍数は $36$ 。よって $T \equiv 36 (mod 100)$ 。

答え: $36$

よくある誤り

底と法が互いに素でないのにオイラーの定理を使い、 $2^{e} mod 1000$ を $e mod φ (1000) = 400$ だけで決めてしまう誤り。実際 $2^{400}$ は偶数なので $2^{400} \neq \equiv 1 (mod 1000)$ 。正しくは $1000 = 8 \times 125$ と分け、法 $8$ では $e \geq 3$ を確かめて $0$ 、法 $125$ では $e mod φ (125) = 100$ を使う。
指数を法 $m$ そのもので割ってしまう誤り（例: $2^{e} mod 25$ を $e mod 25$ で計算する）。正しくは指数は $φ (m)$ で割る: $2^{e} \equiv 2^{e mod 20} (mod 25)$ 。
塔を下から結合してしまう誤り（例: $2^{2^{3}} = (2^{2})^{3} = 64$ とする）。正しくは $2^{2^{3}} = 2^{(2^{3})} = 2^{8} = 256$ 。
$2^{k}$ の部分で指数の大きさを確かめずに $0$ とする誤り（例: $2^{2} = 4$ を法 $8$ で $0$ とする）。 $2^{e} \equiv 0 (mod 2^{k})$ は $e \geq k$ のときだけ成り立ち、 $4 = 2^{2}$ は $2 < 3$ なので法 $8$ で余り $4$ である。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
型なしラムダ計算で、 $0$ 以上の整数 $n$ のチャーチ数を
$n = λ f . λ x . n 個 f (f (\dots (f x) \dots))$
と定める。関数適用は左結合とし、 $M N P$ は $(M N) P$ を表す。
ラムダ項 $777$ は $β$ 簡約によって、あるチャーチ数 $N$ を正規形にもつ。この $N$ を $100$ で割った余りを求めよ。

この技能を使う問題

難易度 4（大学院入試の難問レベル）
$N = {0, 1, 2, \dots}$ （ $0$ を含む）とし、関数 $A : N \times N \to N$ （アッカーマン・ペーター関数）を次の再帰で定める。すべての $m, n \in N$ に対して
$A (0, n) = n + 1, A (m + 1, 0) = A (m, 1), A (m + 1, n + 1) = A (m, A (m + 1, n)) .$
このとき、 $A (4, 3)$ を $1000$ で割った余りを求めよ。