テトレーションのmod
テトレーションにおけるmodを紹介します。
$a$のテトレーション$b$を$^ba$と表記し、次のように定まる値を指す。
$$^1a=a, ^ba = a^{(^{b-1}a)}$$
$^ap\;\pmod n$ の値が$a$が変わったときどの様になるかを考えます。今回よく使う定理を明示します。
自然数$n$と、これと互いに素な自然数$m$について
$$n^{\phi(m)}\equiv 1 \pmod m$$
少し変形すると$k,l$を自然数として、次のようになります。
$$n^k\equiv n^l \pmod m \Leftarrow k\equiv l \pmod {\phi(m)}$$
$p=1$ のとき
何があっても自然数が上につくなら、$1$ になります。
$p>1$のとき
例えば、素数について$ p=7$のとき、$ \mod 5 $で考えると、
$$^1p\equiv 2, ^2p\equiv 3, ^3p\equiv 3, ^4p\equiv 3 \cdots$$
のようになります。 よって十分大きな所では、値が変わらないことが予想されます。
合成数についても
$p=4$, $n=11$のとき
$$^1p\equiv4,{}^2p\equiv3,{}^3p\equiv4, {}^4p\equiv4,\cdots \pmod n$$
$p=6,\;n=11$のとき
$$^1p\equiv6,{}^2p\equiv5,{}^3p\equiv5, {}^4p\equiv5,\cdots \pmod 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$に対して、${}^Np\equiv {}^{N+1}p\equiv {}^{N+2}p\equiv \cdots \pmod {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 \cdots \pmod {\phi(k)}$
よってオイラーの定理より、
${}^{N'+1}p\equiv {}^{N'+2}p\equiv {}^{N'+3}p\equiv \cdots \pmod k$ が示された。
よって$N=N'+1$ などが与式を満たす。
(ii) $k$と$p$が互いに素でないとき、
$k=\prod_ip_i^{s_i} A$ ($s_i$は非負整数、$A$は$p$と互いに素な自然数) とおける。
命題を示すには中国剰余定理などから以下を満たす$N$があればよい。
$\begin{eqnarray}
\left\{
\begin{array}{l}
(\forall i) & {}^Np\equiv {}^{N+1}p\equiv {}^{N+2}p\equiv \cdots \pmod {p_i^{s_i}} \\
&{}^Np\equiv {}^{N+1}p\equiv {}^{N+2}p\equiv \cdots \pmod A
\end{array}
\right.
\end{eqnarray}$
前者は各$i$に対し、$p_i^{s_i} \le {}^N(p_i^{e_i})$ を満たす$N$ ならいつでも満たす。
後者について、
$A< N$よりある$N'$で、
$${}^{N'}p\equiv {}^{N'+1}p\equiv {}^{N'+2}p\equiv \cdots \pmod A $$
となるものがあるから、$N' \leq N$ となる$N$ならいつでも満たす。
よって$N \in \{M | (\forall i)p_i^{s_i} \le {}^M(p_i^{e_i})\land N' \leq M\}$ を満たす$N$について、
$${}^Np\equiv {}^{N+1}p\equiv {}^{N+2}p\equiv \cdots \pmod k$$
どのくらいで一定になるのか
$n$によって決まる、命題2に登場する$N$の下限を$a_n$で表すと、下のようになります。
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
a_1 = 1 \\
a_n = a_{\phi(n)}+1 & (\gcd(p,n)=1 ) \\
a_n = \max(\max(\{\lceil\slog_{p_i^{e_i}}(p_i^{s_i})\rceil\}), a_{\frac{n}{\prod_i(p_i^{s_i})}}) & (\gcd(p,n)>1)
\end{array}
\right.
\end{eqnarray}
$$
ただし、$\slog_ab$は、$^xa\geq b$となる最小の$x$を表します。ここで、この数列を$n$以下と評価したいと思います。もっと強い評価は他の人がやってくれると信じています。
上の式によって定義される$\{a_i\}$は、任意の自然数$n$について、$a_n\leq n$とできる。
この命題から、以下のことが正しいと言えます。
$${}^np\equiv{}^{n+1}p\equiv{}^{n+2}p\equiv\cdots \pmod n$$
帰納法で示す。
$n=1$ のとき、正しい。
$n=k$ まで正しいとして、$n=k+1$ のとき、
(i)$k+1$ と$p$ が互いに素なとき、
$\phi(n)< n$ より、
$$a_{k+1}=a_{\phi(k+1)}+1\leq \phi(k+1)+1\leq k+1$$
(ii)$k+1$と$p$ が互いに素でないとき
$p=\prod_ip_i^{e_i}$ とおく。各$i$に対し、
\begin{eqnarray}
p_i^{s^i} &\leq& k+1 \\
(k+1) &\lt & {}^{k+1}p_i \;\;\;(\because p_i>1, p_i^{k+1}\leq{}^{k+1}p_i)\\
\end{eqnarray}
よって、
\begin{eqnarray}
\lceil\slog_{p_i^{e_i}}(p_i^{s_i})\rceil
&\leq& 1+\slog_{p_i}(k+1) \\
&\leq& k+1
\end{eqnarray}
また、$\frac{k+1}{\prod_i(p_i^{s_i})}\lt k+1$ より、
$$a_{\frac{k+1}{\prod_i(p_i^{s_i})}}< k+1$$
よって、
$$\max(\max(\{\lceil\slog_{p_i^{e_i}}(p_i^{s_i})\rceil\}), a_{\frac{n}{\prod_i(p_i^{s_i})}})\leq n$$
以上より、$a_n\leq n$.
他の巨大数への応用
まず、ペンテーションと呼ばれるものをみてみましょう。
$a$のペンテーション$b$を$a\pentation b$と表記し、次のように定まる値を指す。
$$a\pentation 1=a, a\pentation b = {}^{(a\pentation (b-1))}a$$
例えば、$p\pentation2={}^pp$, $p\pentation3={}^{({}^pp)}p$のようになります。よって命題3から次のことがわかります。
$n$, $m$, $p$ を自然数とし、 とする。
$a$を、$n\pentation a\geq p$となる最小の自然数とすれば、$m\gt a$に対し、
$$n\pentation m \equiv {}^pn \pmod p$$
人類が知っている程度の数はかなり小さいことが多いので、$a$はそんなに大きく取る必要はありません。
$m\geq a+1$ のとき$n\pentation (m-1)\geq n\pentation a\geq p$と命題3から、
$n\pentation m={}^{n\pentation (m-1)}n\equiv {}^pn \pmod p$
テトレーション、ペンテーションは定義2で用いたような矢印表記によって表せます。
矢印表記$a\uparrow^nb$は次のように定まる。
$\begin{eqnarray}
\begin{array}{l}
a\uparrow^1b&=&a^b \\
a\uparrow^n1&=&a^1 \\
a\uparrow^{n+1}(b+1)&=&a\uparrow^{n}(a\uparrow^{n+1}b)
\end{array}
\end{eqnarray}$
今まで考えていたテトレーションは$a\uparrow^2b$, ペンテーションは$a\uparrow^3b$に相当します。
また、三つ目の定義式から次のことが言えます。
$k$, $n$, $m$, $p$ を自然数とし、$n\geq2$, $k\geq3$,とする。
$a$を、$n\pentation a\geq p$となる最小の自然数とすれば、$m\gt a$に対し、
$$n\uparrow^k m \equiv n\uparrow^2p={}^pn \pmod p$$
$k$に関する帰納法で示す。
$k=3$のときこれは命題4から明らか。
$k=l>3$として、$3\leq k\leq l-1$ まで成り立っていたとすると、
$n\geq2$から、
$n\uparrow^l(m-1)\geq n\uparrow^1 (m-1)\geq n\uparrow^1 a\gt a$より、
$$n\uparrow^lm=n\uparrow^{l-1}(n\uparrow^l(m-1))\equiv n\uparrow^2p \pmod p$$
まとめ
テトレーションをmodすると、$^ba$ の$b$の部分が大きくなりまくると変化しなくなることがわかりました。
参考文献
この記事を高評価した人
投稿者
