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

問題


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


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

例えば m = 3 とすると

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で書くと以下の様になります。

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)

オイラーの定理

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

aとnが互いに素な整数であるとき、次が成り立つ。\\

　　　　　    a^{\varphi(n)} \equiv 1 \pmod n \\

ここで\varphi(n)~は~n~以下の~n~と互いに素な正の整数の個数を表す。

この定理は、n が素数の時は次の有名なフェルマーの小定理となります。

pが素数で、a~が~p~と互いに素な正の整数であるとき、次が成り立つ。\\

　　　　　a^{p-1} \equiv 1 \pmod p \\

証明

４つの場合に分けて考えていきます。

Case 1　整数mが5でも2でも割り切れないとき

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

m^{x_0}の桁数を~l~とすると~10^l>m^{x_0}~である。またオイラーの定理より

　m^{\varphi(10^l)} \equiv 1 \pmod {10^l}\\

したがって

m^{\varphi(10^l)+x_0} \equiv m^{x_0} \pmod {10^l}\\

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の倍数ではないとき

[補題]

lを任意の自然数として、関数g_l:{\mathbb N} \rightarrow {\mathbb　N} を次のように定める。\\

g_l(x)=\{5^{l \varphi (10^x)}を十進法表示したときの下x桁の和 \}\\

このときg_l(x)は発散する。

[補題の証明]


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

また\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)\\

さらに\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}\\

従って
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)

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

(1)(2)(3)より

5^{l{\varphi(10^{x_1+k})}} - 5^{l \varphi(10^{x_1})} \equiv 0 \pmod {10^{x_1}}\\

すなわち5^{l{\varphi(10^{x_1+k})}}の下x_1桁は全て5^{l \varphi(10^{x_1})}に等しい。\\

g_l(x_1)の最大性から5^{l{\varphi(10^{x_1+k})}}の下x_1+1桁目からx_1+k桁目は全て0である。\\

よって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}}\\

従って
5^{l{\varphi(10^{x_1+k})}} - A \equiv 0 \pmod {5^{x_1+k}}\\

一方\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}}\\

よって
A \equiv 0 \pmod {5^{x_1+k}}\\

しかしこれはk~が十分大きいとき成り立たない。よってg_l(x)は発散する。

[Case 2の証明]

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}\\

補題より5^{l'\varphi(10^y)}の下~y~桁の和はいくらでも大きな数をとりうるので、F_m(x)は発散する。

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

[補題Ⅱ]

aを任意の自然数として、関数h_a:{\mathbb N} \rightarrow {\mathbb　N} を次のように定める。\\

h_a(x)=\{2^{a \varphi (10^x)}を十進法表示したときの下x桁の和 \}~~(x \in {\mathbb N} )\\

このときh_a(x)は発散する。

[補題Ⅱの証明]


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}}\\

よって
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}}\\

従って
2^{a{\varphi(10^{x_2+b})}} - B \equiv 0 \pmod {2^{x_2+b}}\\
よって
B \equiv 0 \pmod {2^{x_2+b}}\\

しかしこれは~b~が十分大きいとき成り立たない。よってh_a(x)は発散する。

[Case 3の証明]

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}\\

補題Ⅱより2^{l''\varphi(10^z)}の下z~桁の和はいくらでも大きな数をとりうるので、F_m(x)は発散する。

Case 4　整数mが10の倍数のとき

m=10^cd~~~~~~(c,d \in {\mathbb N}, \frac{d}{10} \notin {\mathbb N})\\
とおけば

(m^xの各桁の和)=(d^xの各桁の和）

であり、

{\rm Case 1 ～3}よりd^xの各桁の和は発散するので
F_m(x)は発散する。

証明終。