Eulerのφ関数をkeisan.casio.jpにUP.

説明は： Eulerのφ関数（Euler's totient function）は、k=1,2,3,...,xのうち、xと互いに素(最大公約数が1)なものの個数である。 例えばx=7のとき、k=1,2,3,4,5,6,7と素なのは1,2,3,4,5,6なのでφ(7)=6, x=6のときは1,5なのでφ(6)=2。
参考：C言語による最新アルゴリズム事典（奥村晴彦著）

リンクはこちら。

オイラーのφ関数

さて、なぜこれを作ったかというと、フェルマーの小定理の拡張（オイラーの定理）の計算を試すため。

aとnが互いに素な整数のときこのφ関数を使って

a^φ(n) ≡1 (mod n)

と書けるというのがある。

面白い応用があって、

例えば7＾2012の下2桁を求めたいとします。mod 100でのあまりを見ればいいってことで、

φ（100）=40　（これを求めたいがためだけに計算式を作った）

7^40 ≡ 1 (mod 100)

2012=40*50+12なので、

7^2012 = 7^12 * (7^40)^50 だから

7^12を100で割ったあまり。

7＾12 ≡ 1 (mod 100)

なので下2桁は01.