ある数列の発散について

正の整数 m と x に対し m^x の各桁の和を
F_m(x) と表すことにする。\\
このときmが10の冪でなければ、xが増大するにしたがいF_m(x)は発散することを証明せよ。

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

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~と互いに素な正の整数の個数を表す。

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

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)は発散する。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\

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)は発散する。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\

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)は発散する。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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)は発散する。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\

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)は発散する。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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)は発散する。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~