今回は以下のような問題を解いてみたいと思います。必要な知識は合同式だけですので、
高校生でも十分に理解できる内容です。
問題
正の整数 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)は発散する。
証明終。