整数問題(^^) - 白のカピバラの逆極限 S.144-3

http://acm.pku.cn/JudgeOnline/showproblem?problem_id=2720
ようするに b i n からタワーを使って書くと
(Knuth's up-arrow notation)

b^^i `mod` 10^n

を求めたまえ、ということ。

(^^) b 0 = 1
(^^) b i = b ^ (b ^^ (i-1))
g b i n = b^^i `mod` 10^n

顔に見えてしまう(顔。

さてさて。
id:tanakhさんの[ICPC]Last Digits より。

定理1：累乗の下位桁の周期に関する定理
∃a, ∀b>=a, ∀n>=2, ∀x, x^b ≡ x^(b+10^n) (mod 10^n)

texで書き直すと、 $\Large \exists a \forall b \geq a \forall n \geq 2 \forall x \quad x^b \equiv x^{b+10^n} \quad (mod 10^n)$

これはぱっと見反例がありますね。
$\Large b=max(a,2) \quad x=10 \quad n=a^2$ とすれば、 $\Large l.h.s. = 10^a \qquad 0 < 10^a < 10^n$ なのに対して、 $\Large r.h.s. = 10^{a+10^n} \equiv 0 (mod 10^n)$ ですから。

さて。じゃあ、この定理をどのように料理しましょうか。そりゃ、xが10と互いに素の時とそうでないときに分けるのが基本でしょう。

どうみたって、主役はオイラー・フェルマーの定理ですね。平方剰余がダークホースかなと思っていたら出場すらしなくて、帰納法が片をつけてくれました。
フェルマーの小定理の復習から。

pを素数、aをpと互いに素な数とする。このとき、
$\Large a^{p-1} \equiv 1(mod p)$

オイラーの定理と一緒に証明しちゃう。

nを正整数 $\phi(n)=\left|\left\{ n |0\leq i<n, (i,n)=1 \right}\right|$ とする。( $(a,b)$ はaとbの最大公約数)このとき、
$\Large \forall a \quad (a,n)=1 \Rightarrow a^{\phi(n)} \equiv 1(mod n)$

はい。
証明。

$\mathbb{Z}$ がユークリッド整域なのでPIDで、 $\Large (a,n)=1$ から $\Large \exists b,r \in \mathbb{Z} ab+nr=1$ がいえる。さらに、 $\exists b \in \mathbb{Z} ab \equiv 1 mod n\mathbb{Z}$ なので $\Large a mod n\mathbb{Z} \in (\mathbb{Z}/n\mathbb{Z})^*$ がいえ、これらが同値であることが分かる。
よって、 $\phi(n)$ が $\Large (\mathbb{Z}/n\mathbb{Z})^*$ の位数で、
$\Large a \quad (a,n)=1$ となるような a から生成される $(\mathbb{Z}/n\mathbb{Z})^*$ の部分群の位数は $\phi(n)$ の約数であることから。
$\Large \forall a \quad (a,n)=1 \Rightarrow a^{\phi(n)} \equiv 1(mod n)$

こうなりますと、xが10と互いに素のときとそうでないときで分けるのが自然。

xが10と互いに素のとき

$\Large \exists a \forall b \geq a \forall n \geq 2 \forall x \quad x^b \equiv x^{b+10^n} \quad (mod 10^n)$
互いに素の時には、 $\mathbb{Z}/p\mathbb{Z}$ の上で x に逆元が存在するので
$\Large \forall n \geq 2 \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{10^n} \quad (mod 10^n)$ としても一般性を失わないのでこれを示す。
Euler's law でざっくりやると。
$\Large \forall n \geq 2 \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{2^{n+1}5^{n-1}} \quad (mod 10^n)$ となる。
ここで、突然、ずっと楽な方法を思いついてしまったので、方針転換して孫氏定理(中国剰余定理)を使います。

$\Large \forall n \geq 2 \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{10^n} \quad (mod 10^n)$
は
$\Large \forall n \geq 2 \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{10^n} \quad (mod 2^n)$ と
$\Large \forall n \geq 2 \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{10^n} \quad (mod 5^n)$ の両方を示せばよい。
オイラーの定理から、
$\Large \forall n \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{2^{n-1}} \quad (mod 2^n)$ と
$\Large \forall n \forall x \in (\mathbb{Z}/10^n\mathbb{Z})^* \quad 1 \equiv x^{2^2 \times 5^{n-1}} \quad (mod 2^n)$ が成立するので、すぐに上がいえて終了。

さて、

xが10と互いに素でないとき

反例もこの場合だから分かるように誤っています。
で、どうするかというと、
$\Large \forall n \geq 2 \forall x \exists a \forall b \geq a \quad x^b \equiv x^{b+10^n} \quad (mod 10^n)$
なら正しいんですね。

を孫氏定理で直積に分解します。
$\Large \forall n \geq 2 \forall x \exists a \forall b \geq a \quad x^b \equiv x^{b+10^n} \quad (mod 2^n)$
$(2,x)=1$ の場合はオイラーの定理で示せて、そうでなければ x が 2 で割り切れるので、十分に大きい $a(\geq n)$ をとれば両辺 0 にいっちゃうの〜。
$\Large \forall n \geq 2 \forall x \exists a \forall b \geq a \quad x^b \equiv x^{b+10^n} \quad (mod 5^n)$
同様。

ああ、紙に書くなら一瞬なのになんて長くなったんだ。

それで、続きは Haskell による出題者想定解答予想か。
と思ったら、なんかこれじゃない気がしてきた。オイラー関数求めなきゃいけないとなると、素因数分解しなきゃいけなくて。もうちょと考えます。