ある数列の発散について

今回は以下のような問題を解いてみたいと思います。必要な知識は合同式だけですので、
高校生でも十分に理解できる内容です。



## 問題

```math:

正の整数 m と x に対し m^x の各桁の和を
F_m(x) と表すことにする。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

```
```math:

このときmが10の冪でなければ、xが増大するにしたがいF_m(x)は発散することを証明せよ。

```

例えば m = 3 とすると

```math:
F_3(1)=3,~~F_3(2)=9,~~F_3(3)=2+7=9,~~F_3(4)=8+1=9,~~F_3(5)=2+4+3=9, \cdots
```

というような値となります。


因みに、この関数をPythonで書くと以下の様になります。



```python:
m, x = map(int, input().split())
r = m**x
#print(r)

s = 0
while r >= 10:
    x = r % 10  #1桁目
    #print(x)
    s = s + x
    #print(s)
    r = ((r-x)//10)

#print(r)
s = s + r
print(s)
```



#### オイラーの定理
この問題を解くにあたって鍵となるのは、オイラーの定理と言われる次の定理です。

```math:
aとnが互いに素な整数であるとき、次が成り立つ。\\
```
```math:
　　　　　    a^{\varphi(n)} \equiv 1 \pmod n \\
```
```math:
ここで\varphi(n)~は~n~以下の~n~と互いに素な正の整数の個数を表す。
```
この定理は、n が素数の時は次の有名なフェルマーの小定理となります。

```math:
pが素数で、a~が~p~と互いに素な正の整数であるとき、次が成り立つ。\\
```
```math:
　　　　　a^{p-1} \equiv 1 \pmod p \\
```


## 証明
４つの場合に分けて考えていきます。
#### Case 1　整数mが5でも2でも割り切れないとき
```math:
F_m(x)が発散しないならば任意の整数~x~に対しF_m(x) \leq F_m(x_0) を満たすx_0 \in {\mathbb N}が存在する。
```
```math:
m^{x_0}の桁数を~l~とすると~10^l>m^{x_0}~である。またオイラーの定理より
```

```math:
　m^{\varphi(10^l)} \equiv 1 \pmod {10^l}\\
```
```math:
したがって
```
```math:
m^{\varphi(10^l)+x_0} \equiv m^{x_0} \pmod {10^l}\\
```
```math:
m^{\varphi(10^l)+x_0}は下~l~桁が~m^{x_0}~と等しく最上位の数が~0~でないことから~F_m(\varphi(10^l)+x_0)>F_m(x_0)~となるが、これは~x_0の定義に反する。よってF_m(x)は発散する。


```


#### Case 2　整数mが5の倍数で、かつ2の倍数ではないとき

[補題]

```math:
lを任意の自然数として、関数g_l:{\mathbb N} \rightarrow {\mathbb　N} を次のように定める。\\
```
```math:
g_l(x)=\{5^{l \varphi (10^x)}を十進法表示したときの下x桁の和 \}\\
```
```math:
このときg_l(x)は発散する。
```
[補題の証明]

```math:

g_l(x)が発散しないならば任意の整数~x~に対しg_l(x) \leq g_l(x_1) を満たすx_1 \in {\mathbb N}が存在する。
```
```math:
また\varphi(10^n)=4 \cdot 10^{n-1}であるから任意の自然数k~に対し
5^{l \varphi (10^{x_1+k})}-5^{l \varphi (10^{x_1})}
=5^{l \cdot 4 \cdot 10^{x_1-1}} (5^{l \cdot 4 \cdot 10^{x_1+k-1}-{l \cdot 4 \cdot 10 ^{x_1 -1}}}-1)\\

=5^{l \cdot 4 \cdot 10^{x_1-1}} (5^{l \cdot 4 \cdot 10^{x_1-1}(10^k-1)}-1)\cdots(1)\\

```
```math:
さらに\varphi(2^n)=2^{n-1}で、5^lと2^nは互いに
素な整数だからオイラーの定理より
(5^l)^{\varphi(2^n)} \equiv 5^{l 2^{n-1}} \equiv 1 \pmod {2^n}\\

```
```math:
従って
5^{l \cdot 4 \cdot 10^{x_1-1}(10^k-1)}-1 \equiv (5^{l \cdot 2^{x_1-1}})^{ 4 \cdot 5^{x_1-1}(10^k-1)}-1 \equiv 0 \pmod {2^{x_1}}\cdots(2)

```
```math:
一方10^{x_1-1} \geq x_1 より
5^{l \cdot 4 \cdot 10^{x_1-1}} \equiv 0 \pmod {5^{x_1}} \cdots(3)\\
```
```math:
(1)(2)(3)より

5^{l{\varphi(10^{x_1+k})}} - 5^{l \varphi(10^{x_1})} \equiv 0 \pmod {10^{x_1}}\\
```
```math:
すなわち5^{l{\varphi(10^{x_1+k})}}の下x_1桁は全て5^{l \varphi(10^{x_1})}に等しい。\\
```
```math:
g_l(x_1)の最大性から5^{l{\varphi(10^{x_1+k})}}の下x_1+1桁目からx_1+k桁目は全て0である。\\
```
```math:
よって5^{l{\varphi(10^{x_1})}}  \equiv A \pmod {10^{x_1}}~~~~(1 \leq A \leq 10^{x_1}-1)とおくと
5^{l{\varphi(10^{x_1+k})}} - A \equiv 0 \pmod {10^{x_1+k}}\\

```
```math:
従って
5^{l{\varphi(10^{x_1+k})}} - A \equiv 0 \pmod {5^{x_1+k}}\\
```
```math:
一方\varphi(10^{x_1+k})=4 \cdot 10^{x_1+k-1}>x_1+kより5^{l{\varphi(10^{x_1+k})}} \equiv 0 \pmod {5^{x_1+k}}\\
```
```math:
よって
A \equiv 0 \pmod {5^{x_1+k}}\\
```
```math:
しかしこれはk~が十分大きいとき成り立たない。よってg_l(x)は発散する。


```

[Case 2の証明]

```math:
m=5^{l'}p~~(p~は10と互いに素な整数）とおくと、任意の自然数~y~に対し
オイラーの定理より
p^{\varphi(10^y)} \equiv 1 \pmod {10^y} であるから
m^{\varphi(10^y)} = p^{\varphi(10^y)}5^{l'\varphi(10^y)} \equiv  5^{l'\varphi(10^y)} \pmod {10^y}\\
```
```math:
補題より5^{l'\varphi(10^y)}の下~y~桁の和はいくらでも大きな数をとりうるので、F_m(x)は発散する。
```


#### Case 3　整数mが2の倍数で、かつ5の倍数ではないとき

[補題Ⅱ]

```math:
aを任意の自然数として、関数h_a:{\mathbb N} \rightarrow {\mathbb　N} を次のように定める。\\
```
```math:
h_a(x)=\{2^{a \varphi (10^x)}を十進法表示したときの下x桁の和 \}~~(x \in {\mathbb N} )\\
```
```math:
このときh_a(x)は発散する。
```
[補題Ⅱの証明]

```math:

h_a(x)が発散しないならば任意の整数~x~に対しh_a(x) \leq h_a(x_2) を満たすx_2 \in {\mathbb N}が存在する。

任意の自然数~b~に対し
2^{a \varphi (10^{x_2+b})}-2^{a \varphi (10^{x_2})}\\
=2^{a \cdot 4 \cdot 10^{x_2-1}} (2^{a \cdot 4 \cdot 10^{x_2-1}(10^b-1)}-1)   \equiv 0 \pmod {10^{x_2}}\\
```

```math:
よって
2^{a{\varphi(10^{x_2})}}  \equiv B \pmod {10^{x_2}}~~~~(1 \leq B \leq 10^{x_2}-1)とおくと\\
2^{a{\varphi(10^{x_2+b})}} - B \equiv 0 \pmod {10^{x_2+b}}\\
```
```math:
従って
2^{a{\varphi(10^{x_2+b})}} - B \equiv 0 \pmod {2^{x_2+b}}\\
よって
B \equiv 0 \pmod {2^{x_2+b}}\\
```
```math:
しかしこれは~b~が十分大きいとき成り立たない。よってh_a(x)は発散する。


```







[Case 3の証明]

```math:
m=2^{l''}q~~(q~は10と互いに素な整数）とおくと、任意の自然数z~に対し
オイラーの定理よりq^{\varphi(10^z)} \equiv 1 \pmod {10^z} であるから
m^{\varphi(10^z)} = q^{\varphi(10^z)}2^{l''\varphi(10^z)} \equiv  2^{l''\varphi(10^z)} \pmod {10^z}\\
```
```math:
補題Ⅱより2^{l''\varphi(10^z)}の下z~桁の和はいくらでも大きな数をとりうるので、F_m(x)は発散する。

```


#### Case 4　整数mが10の倍数のとき
```math:
m=10^cd~~~~~~(c,d \in {\mathbb N}, \frac{d}{10} \notin {\mathbb N})\\
とおけば
```
```math:
(m^xの各桁の和)=(d^xの各桁の和）
```
```math:であり、
{\rm Case 1 ～3}よりd^xの各桁の和は発散するので
F_m(x)は発散する。
```

証明終。