オイラーのφ関数の解説
1から10までの数を書き、10と公約数を持つものをすべて消してみましょう。残るのは1、3、7、9の4つです。この個数 φ(10) = 4 がオイラーのφ関数で、分数や時計から、オンライン決済を守る暗号まで、整数論で最もよく使われる関数のひとつです。
互いに素な数を数える
2つの数の最大公約数が1のとき、それらは互いに素であるといいます。φ(n) は、1から n までの k のうち gcd(k, n) = 1 となるものを数えます。φ(9) = 6、φ(10) = 4、φ(12) = 4、φ(1) = 1 です。この同じ個数があちこちに現れます。0と1の間の k/n のうちすでに既約分数になっているものの個数、n 時間の文字盤で針がすべての時刻を通る歩幅の個数、そして n を法として逆数を持ち、k × x ≡ 1 (mod n) が解ける k の個数です。
積の公式
n を割り切る素数が p₁、p₂ … なら、φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … です。理由はふるいです。すべての数の半分は偶数なので、2の倍数を取り除くと割合 1 − 1/2 が残ります。残った数のうち3つに1つは3の倍数で、以下同様です。中国剰余定理により異なる素数についての条件は互いに独立なので、割合はそのまま掛け合わされます。100 = 2² × 5² なら 100 × 1/2 × 4/5 = 40 です。2つの性質が同じ結果を別の形で与えます。φ(p^k) = p^(k−1)(p − 1) と、m と n が互いに素なときの φ(mn) = φ(m) φ(n) です。したがって φ(100) = φ(4) × φ(25) = 2 × 20 = 40 です。
オイラーの定理
フェルマーは1640年に、素数 p と p で割り切れない任意の a について a^(p−1) ≡ 1 (mod p) となることに気づきました。オイラーは一般の形を証明し、1763年に発表しました。gcd(a, n) = 1 なら a^φ(n) ≡ 1 (mod n) です。証明は短いものです。n と互いに素な φ(n) 個の数にそれぞれ a を掛けると、積はやはり n と互いに素で、n を法としてすべて異なるので、同じ数を並べ替えたものになります。2つの積を比べると a^φ(n) ≡ 1 が残ります。ある a について成り立つ最小の指数がその位数で、つねに φ(n) を割り切ります。すべての a について同時に成り立つ最小の指数がカーマイケル関数 λ(n) です。561 = 3 × 11 × 17 では λ(561) = 80 が560を割り切るので、561は素数ではないのに、561と互いに素なすべての a について a^560 ≡ 1 (mod 561) となります。これが最小のカーマイケル数で、フェルマー・テストだけでは素数であることを証明できない理由です。
ガウスの約数和と平均
n の約数 d について φ(d) を足し合わせると、必ず n に戻ります。12なら φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12 です。ガウスは1801年の『整数論研究』でこれを証明しました。分数 1/12、2/12 … 12/12 を既約分数にして分母ごとに分けると、その理由がわかります。平均すると φ(k) はおよそ 0.61 k です。φ(k)/k の平均は 6/π² ≈ 0.6079 に近づき、これは無作為に選んだ2つの整数が互いに素である確率でもあります。また φ(1) + … + φ(N) は 3N²/π² に近くなります。N = 1,000 では合計が304,192で、3N²/π² ≈ 303,964 です。
決して現れない値
3以上のすべての n で φ(n) は偶数です。n と互いに素な数は k と n − k の組になって現れるからです。偶数がすべて値になるわけでもありません。14、26、34、38、50が決して現れない最初の値で、一方24は35から90までの10個の異なる数の値です。これらを見つけるのは有限の探索です。n を割り切る各素数 p について、p − 1 が φ(n) を割り切らなければならないからです。1907年、ロバート・カーマイケルはちょうど1回だけとられる値はないと主張しました。その証明は誤りで、主張はいまも未解決であり、例外があるとすれば10^(10^10)より大きくなければなりません。D・H・レーマーは1932年に、合成数 n について φ(n) が n − 1 を割り切ることがあるかと問いましたが、例は知られていません。
RSA におけるφ関数
RSA は2つの大きな素数 p と q を選び、n = pq と指数 e を公開します。φ(n) = (p − 1)(q − 1) なので、n を素因数分解できる人は φ(n) を計算でき、そこから e × d ≡ 1 (mod φ(n)) となる秘密指数 d を求められます。そのうえでオイラーの定理により (m^e)^d ≡ m (mod n) が保証されます。教科書の例 n = 3233 = 61 × 53 では φ(n) = 3,120、e = 17、d = 2,753 です。多くの実装では代わりに λ(n) = lcm(p − 1, q − 1) を使い、ここでは780なので、より小さい d = 413 が得られます。600桁の RSA の法の φ(n) を計算するのは、それを素因数分解するのと同じくらい難しいことです。n と φ(n) がわかれば、平方根を1回とるだけで2つの素数が求まるからです。
試してみる
計算機を開いて10^18までの任意の n を入力すると、φ(n) と素因数、公式が表示されます。500までは1から n までの数が描かれ、互いに素な数は塗りつぶされ、それ以外は n と共通する最小の素数の色で塗られるので、積の公式が数えられるふるいになります。数 a を選んでオイラーの定理を確かめたり、「グラフ」に切り替えて素数が直線 φ(p) = p − 1 上に並ぶ100,000までの φ(k) を見たり、「逆算」に切り替えて φ(n) = m となるすべての n を見つけたりできます。
よくある質問
なぜ φ(1) = 1 なのですか?
gcd(1, 1) = 1 だからです。1から1までの唯一の数は1と互いに素です。この約束によって公式も成り立ったままになります。たとえば n の約数についてのガウスの和は、n = 1 では単に φ(1) = 1 です。
φ は素数計数関数と同じものですか?
違います。π(n) は n 以下の素数を数え、φ(n) は n 以下で n と互いに素な数を数えます。φ(10) = 4 は1、3、7、9を数え、π(10) = 4 は2、3、5、7を数えます。ここで一致するのは偶然で、φ(12) = 4 ですが π(12) = 5 です。
φ(n) はどれくらい速く計算できますか?
n を素因数分解できる速さと同じです。素因数がわかっていれば数回の掛け算で済みますが、わからなければ速い方法は知られておらず、RSA はまさにこの点に依存しています。10^18までの数ならブラウザーでの素因数分解は数ミリ秒ですが、数百桁の数では何年もかかることがあります。
n に比べて φ(n) が最も小さいのはどんな数ですか?
小さな素因数をたくさん持つ数です。φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… は、どの素数が n を割り切るかだけで決まり、そのべきには関係しません。2のべきならちょうど 1/2、30 = 2 × 3 × 5 なら 8/30 で約27%です。最初の15個の素数の積 614,889,782,588,491,410 は φ(n)/n ≈ 14% で、10^18までのすべての数の中で最小です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
φ関数計算機を開く