« 「プラ・バロック」を読んだ。 | トップページ | auのCMのBGMは「幸福を売る男”Le Marchand de bonheur”」だそうです。 »

2012年2月19日 (日)

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.

« 「プラ・バロック」を読んだ。 | トップページ | auのCMのBGMは「幸福を売る男”Le Marchand de bonheur”」だそうです。 »

学問・資格」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/512682/54023842

この記事へのトラックバック一覧です: Eulerのφ関数をkeisan.casio.jpにUP.:

« 「プラ・バロック」を読んだ。 | トップページ | auのCMのBGMは「幸福を売る男”Le Marchand de bonheur”」だそうです。 »

最近のコメント

2018年9月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            
フォト
無料ブログはココログ