テトレーションのmod

巨大数,合同式

106

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

テトレーションにおけるmodを紹介します。

テトレーション

$a$ のテトレーション $b$ を $^{b} a$ と表記し、次のように定まる値を指す。
$^{1} a = a,^{b} a = a^{(^{b - 1} a)}$

$^{a} p (\mod n)$ の値が $a$ が変わったときどの様になるかを考えます。今回よく使う定理を明示します。

オイラーの定理

自然数 $n$ と、これと互いに素な自然数 $m$ について
$n^{ϕ (m)} \equiv 1 (\mod m)$

少し変形すると $k, l$ を自然数として、次のようになります。
$n^{k} \equiv n^{l} (\mod m) \Leftarrow k \equiv l (\mod ϕ (m))$

$p = 1$ のとき

何があっても自然数が上につくなら、 $1$ になります。

$p > 1$ のとき

例えば、素数について $p = 7$ のとき、 $\mod 5$ で考えると、
$^{1} p \equiv 2,^{2} p \equiv 3,^{3} p \equiv 3,^{4} p \equiv 3 \dots$
のようになります。　よって十分大きな所では、値が変わらないことが予想されます。
合成数についても
$p = 4$ , $n = 11$ のとき
$^{1} p \equiv 4,^{2} p \equiv 3,^{3} p \equiv 4,^{4} p \equiv 4, \dots (\mod n)$
$p = 6, n = 11$ のとき
$^{1} p \equiv 6,^{2} p \equiv 5,^{3} p \equiv 5,^{4} p \equiv 5, \dots (\mod n)$
やはり一定になりそうですね。
2以上の整数は $p = \prod_{i} p_{i}^{e_{i}}$ ( $p_{i}$ は素数, $e_{i}$ は1以上の自然数)とおけます。これと先ほどの計算方法から次の命題を示します。

$p$ が $p = \prod_{i} p_{i}^{e_{i}}$ ( $p_{i}$ は素数, $e_{i}$ は1以上の自然数)で表されるとき、任意の自然数 $n$ に対し、ある自然数 $N$ に対して、 $^{N} p \equiv^{N + 1} p \equiv^{N + 2} p \equiv \dots (\mod n)$ が成立する。

帰納法を用いる。
$n = 1$ で成り立つことは明らか。
$k > 1$ として、 $n = k - 1$ まで全て成り立っていたとし、 $n = k$ の場合を示す。
(i) $k$ と $p$ が互いに素なとき
仮定よりある $N^{'}$ について、
$^{N^{'}} p \equiv^{N^{'} + 1} p \equiv^{N^{'} + 2} p \equiv \dots (\mod ϕ (k))$
よってオイラーの定理より、
$^{N^{'} + 1} p \equiv^{N^{'} + 2} p \equiv^{N^{'} + 3} p \equiv \dots (\mod k)$ が示された。
よって $N = N^{'} + 1$ などが与式を満たす。
(ii) $k$ と $p$ が互いに素でないとき、
$k = \prod_{i} p_{i}^{s_{i}} A$ ( $s_{i}$ は非負整数、 $A$ は $p$ と互いに素な自然数)　とおける。
命題を示すには中国剰余定理などから以下を満たす $N$ があればよい。
$\begin{array}{r} {\begin{cases} (\forall i) & ^{N} p \equiv^{N + 1} p \equiv^{N + 2} p \equiv \dots (\mod p_{i}^{s_{i}}) \\ ^{N} p \equiv^{N + 1} p \equiv^{N + 2} p \equiv \dots (\mod A) \end{cases} \end{array}$
前者は各 $i$ に対し、 $p_{i}^{s_{i}} \leq^{N} (p_{i}^{e_{i}})$ 　を満たす $N$ ならいつでも満たす。
後者について、
$A < N$ よりある $N^{'}$ で、
$^{N^{'}} p \equiv^{N^{'} + 1} p \equiv^{N^{'} + 2} p \equiv \dots (\mod A)$
となるものがあるから、 $N^{'} \leq N$ となる $N$ ならいつでも満たす。
よって $N \in {M | (\forall i) p_{i}^{s_{i}} \leq^{M} (p_{i}^{e_{i}}) \land N^{'} \leq M}$ を満たす $N$ について、
$^{N} p \equiv^{N + 1} p \equiv^{N + 2} p \equiv \dots (\mod k)$

どのくらいで一定になるのか

$n$ によって決まる、命題2に登場する $N$ の下限を $a_{n}$ で表すと、下のようになります。
$\begin{array}{r} {\begin{cases} a_{1} = 1 \\ a_{n} = a_{ϕ (n)} + 1 & (gcd (p, n) = 1) \\ a_{n} = max (max ({⌈ {slog}_{p_{i}^{e_{i}}} (p_{i}^{s_{i}}) ⌉}), a_{\frac{n}{\prod_{i} (p_{i}^{s_{i}})}}) & (gcd (p, n) > 1) \end{cases} \end{array}$
ただし、 ${slog}_{a} b$ は、 $^{x} a \geq b$ となる最小の $x$ を表します。ここで、この数列を $n$ 以下と評価したいと思います。もっと強い評価は他の人がやってくれると信じています。

上の式によって定義される ${a_{i}}$ は、任意の自然数 $n$ について、 $a_{n} \leq n$ とできる。

この命題から、以下のことが正しいと言えます。
$^{n} p \equiv^{n + 1} p \equiv^{n + 2} p \equiv \dots (\mod n)$

帰納法で示す。
$n = 1$ のとき、正しい。
$n = k$ まで正しいとして、 $n = k + 1$ のとき、
(i) $k + 1$ と $p$ が互いに素なとき、
$ϕ (n) < n$ より、
$a_{k + 1} = a_{ϕ (k + 1)} + 1 \leq ϕ (k + 1) + 1 \leq k + 1$
(ii) $k + 1$ と $p$ が互いに素でないとき
$p = \prod_{i} p_{i}^{e_{i}}$ とおく。各 $i$ に対し、
$\begin{array}{rcl} p_{i}^{s^{i}} & \leq & k + 1 \\ (k + 1) & < & ^{k + 1} p_{i} (∵ p_{i} > 1, p_{i}^{k + 1} \leq^{k + 1} p_{i}) \end{array}$
よって、
$\begin{array}{rcl} ⌈ {slog}_{p_{i}^{e_{i}}} (p_{i}^{s_{i}}) ⌉ & \leq & 1 + {slog}_{p_{i}} (k + 1) \\ \leq & k + 1 \end{array}$
また、 $\frac{k + 1}{\prod_{i} (p_{i}^{s_{i}})} < k + 1$ より、
$a_{\frac{k + 1}{\prod_{i} (p_{i}^{s_{i}})}} < k + 1$
よって、
$max (max ({⌈ {slog}_{p_{i}^{e_{i}}} (p_{i}^{s_{i}}) ⌉}), a_{\frac{n}{\prod_{i} (p_{i}^{s_{i}})}}) \leq n$
以上より、 $a_{n} \leq n$ .

他の巨大数への応用

まず、ペンテーションと呼ばれるものをみてみましょう。

ペンテーション

$a$ のペンテーション $b$ を $a ↑↑↑ b$ と表記し、次のように定まる値を指す。
$a ↑↑↑ 1 = a, a ↑↑↑ b =^{(a ↑↑↑ (b - 1))} a$

例えば、 $p ↑↑↑ 2 =^{p} p$ , $p ↑↑↑ 3 =^{(^{p} p)} p$ のようになります。よって命題3から次のことがわかります。

$n$ , $m$ , $p$ を自然数とし、とする。
$a$ を、 $n ↑↑↑ a \geq p$ となる最小の自然数とすれば、 $m > a$ に対し、
$n ↑↑↑ m \equiv^{p} n (\mod p)$

人類が知っている程度の数はかなり小さいことが多いので、 $a$ はそんなに大きく取る必要はありません。

$m \geq a + 1$ のとき $n ↑↑↑ (m - 1) \geq n ↑↑↑ a \geq p$ と命題3から、
$n ↑↑↑ m =^{n ↑↑↑ (m - 1)} n \equiv^{p} n (\mod p)$

テトレーション、ペンテーションは定義2で用いたような矢印表記によって表せます。

矢印表記

矢印表記 $a ↑^{n} b$ は次のように定まる。
$\begin{array}{r} \begin{array}{l} a ↑^{1} b & = & a^{b} \\ a ↑^{n} 1 & = & a^{1} \\ a ↑^{n + 1} (b + 1) & = & a ↑^{n} (a ↑^{n + 1} b) \end{array} \end{array}$

今まで考えていたテトレーションは $a ↑^{2} b$ , ペンテーションは $a ↑^{3} b$ に相当します。
また、三つ目の定義式から次のことが言えます。

$k$ , $n$ , $m$ , $p$ を自然数とし、 $n \geq 2$ , $k \geq 3$ ,とする。
$a$ を、 $n ↑↑↑ a \geq p$ となる最小の自然数とすれば、 $m > a$ に対し、
$n ↑^{k} m \equiv n ↑^{2} p =^{p} n (\mod p)$

$k$ に関する帰納法で示す。
$k = 3$ のときこれは命題4から明らか。
$k = l > 3$ として、 $3 \leq k \leq l - 1$ まで成り立っていたとすると、
$n \geq 2$ から、
$n ↑^{l} (m - 1) \geq n ↑^{1} (m - 1) \geq n ↑^{1} a > a$ より、
$n ↑^{l} m = n ↑^{l - 1} (n ↑^{l} (m - 1)) \equiv n ↑^{2} p (\mod p)$