問題の並び方

projecteulerの問題は一見、規則なしに並んでいるようにも思えるのだけど、そこには規則がある。
それは、前の問題を解くことができれば、その解法を基にして後に出てくる問題を解ける
ことになっている、というもの。
もちろん、これは原則であって、全然関係ないものもあるのだろうけど。

で、P97
Problem 97 - Project Euler
これはいくらなんでも無茶でしょう。と思えるのだけど、意外に正解者が多い。
よく見ると昨日のパスコード推測問題（P79-今時点で6898人正解−昨日から18人増えた）より多い。

後半10ケタがミソなのだけど、と思いながら、Φ関数の高速解を求めてつらつらネットを彷徨っていたら、
Φ関数はべき乗法と併用される云々の記述を見つけた。
いや、私が欲しいのは余り、ではなくて、後半10ケタなんだけど。

あ、そうか！

余りと後半何桁は等価なのか。
そこでΦ関数が出てくるわけか。
深い、深すぎて私には完全には理解できない気がする。

さて、なんとなく理解できた段でしこしこ実装してみるか、と思ったものの、その前にちょっとだけ
pyshellを走らせてみたくなった。せっかく、演算子mod（python的には%）が用意されているんだから、
使わない手はないよね。でも、Hungするか、やたら時間がかかるだろうな、と思いながら。
ほら、やっぱり、と思った瞬間、答えが返ってきた。
後は、掛け算して足し算して、答えが出た。

これがフェルマーのΦ関数の威力なのか。

フェルマーつながりで言えば、フェルマーの最終定理（正確には最終予想、とのこと）の証明
については当初、世界で理解できるのは数人しかいないであろう、といわれていた。
結局どうなったんだろうか。
もっとも、その証明、300ページ以上あるらしいから余白に書ききれるわけもないし、
読む気も失せてしまうのだけど。