3
高校数学解説
文献あり

テトレーションのmod

106
0

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

テトレーション

aのテトレーションbbaと表記し、次のように定まる値を指す。
1a=a,ba=a(b1a)

ap(modn) の値がaが変わったときどの様になるかを考えます。今回よく使う定理を明示します。

オイラーの定理

自然数nと、これと互いに素な自然数mについて
nϕ(m)1(modm)

少し変形するとk,lを自然数として、次のようになります。
nknl(modm)kl(modϕ(m))

p=1 のとき

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

p>1のとき

例えば、素数についてp=7のとき、mod5で考えると、
1p2,2p3,3p3,4p3
のようになります。 よって十分大きな所では、値が変わらないことが予想されます。
合成数についても
p=4, n=11のとき
1p4,2p3,3p4,4p4, (modn)
p=6,n=11のとき
1p6,2p5,3p5,4p5, (modn)
やはり一定になりそうですね。
2以上の整数はp=ipiei(piは素数, eiは1以上の自然数)とおけます。これと先ほどの計算方法から次の命題を示します。

pp=ipiei(piは素数, eiは1以上の自然数)で表されるとき、任意の自然数n に対し、ある自然数Nに対して、NpN+1pN+2p(modn) が成立する。

帰納法を用いる。
n=1で成り立つことは明らか。
k>1として、n=k1まで全て成り立っていたとし、n=kの場合を示す。
(i) kpが互いに素なとき
仮定よりあるN について、
NpN+1pN+2p(modϕ(k))
よってオイラーの定理より、
N+1pN+2pN+3p(modk) が示された。
よってN=N+1 などが与式を満たす。
(ii) kpが互いに素でないとき、
k=ipisiA (siは非負整数、Apと互いに素な自然数) とおける。
命題を示すには中国剰余定理などから以下を満たすNがあればよい。
{(i)NpN+1pN+2p(modpisi)NpN+1pN+2p(modA)
前者は各iに対し、pisiN(piei) を満たすN ならいつでも満たす。
後者について、
A<NよりあるNで、
NpN+1pN+2p(modA)
となるものがあるから、NN となるNならいつでも満たす。
よってN{M|(i)pisiM(piei)NM} を満たすNについて、
NpN+1pN+2p(modk)

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

nによって決まる、命題2に登場するNの下限をanで表すと、下のようになります。
{a1=1an=aϕ(n)+1(gcd(p,n)=1)an=max(max({slogpiei(pisi)}),ani(pisi))(gcd(p,n)>1)
ただし、slogabは、xabとなる最小のxを表します。ここで、この数列をn以下と評価したいと思います。もっと強い評価は他の人がやってくれると信じています。

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

この命題から、以下のことが正しいと言えます。
npn+1pn+2p(modn)

帰納法で示す。
n=1 のとき、正しい。
n=k まで正しいとして、n=k+1 のとき、
(i)k+1p が互いに素なとき、
ϕ(n)<n より、
ak+1=aϕ(k+1)+1ϕ(k+1)+1k+1
(ii)k+1p が互いに素でないとき
p=ipiei とおく。各iに対し、
pisik+1(k+1)<k+1pi(pi>1,pik+1k+1pi)
よって、
slogpiei(pisi)1+slogpi(k+1)k+1
また、k+1i(pisi)<k+1 より、
ak+1i(pisi)<k+1
よって、
max(max({slogpiei(pisi)}),ani(pisi))n
以上より、ann.

他の巨大数への応用

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

ペンテーション

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

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

n, m, p を自然数とし、 とする。
aを、n↑↑↑apとなる最小の自然数とすれば、m>aに対し、
n↑↑↑mpn(modp)

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

ma+1 のときn↑↑↑(m1)n↑↑↑apと命題3から、
n↑↑↑m=n↑↑↑(m1)npn(modp)

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

矢印表記

矢印表記anbは次のように定まる。
a1b=aban1=a1an+1(b+1)=an(an+1b)

今まで考えていたテトレーションはa2b, ペンテーションはa3bに相当します。
また、三つ目の定義式から次のことが言えます。

k, n, m, p を自然数とし、n2, k3,とする。
aを、n↑↑↑apとなる最小の自然数とすれば、m>aに対し、
nkmn2p=pn(modp)

kに関する帰納法で示す。
k=3のときこれは命題4から明らか。
k=l>3として、3kl1 まで成り立っていたとすると、
n2から、
nl(m1)n1(m1)n1a>aより、
nlm=nl1(nl(m1))n2p(modp)

まとめ

テトレーションをmodすると、babの部分が大きくなりまくると変化しなくなることがわかりました。

参考文献

投稿日:20231215
更新日:20231215
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

ふつ
ふつ
3
106

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. p=1 のとき
  2. p>1のとき
  3. どのくらいで一定になるのか
  4. 他の巨大数への応用
  5. まとめ
  6. 参考文献