φ(n)
素因数
互いに素な割合
約数の個数

          表示

          オイラーのφ関数についてもっと詳しく

          オイラーのφ関数計算機

          1から12までの数のうち、12と公約数を持たないのは1、5、7、11だけなので φ(12) = 4 です。オイラーのφ関数は、任意の n についてこのような互いに素な数を数えます。10^18までの数を入力すると、φ(n) とその素因数、書き出された積の公式が得られ、1から n までの数のうち互いに素なものが強調表示されます。オイラーの定理を確かめたり、一度に最大100,000個の数の φ(k) をグラフにしたり、与えられた φ(n) を持つすべての n を見つけたりもできます。 10^18までの整数 n を入力するか、計算例を選んでください。タイルには φ(n)、n の素因数、1から n までのうち n と互いに素な数の割合、約数の個数が表示され、ステップでは積の公式をあなたの数で書き出します。n = 500までは1から n までの数が描かれます。n と互いに素な数は塗りつぶされ、それ以外は n と共通する最小の素数の色で表されます。数にポインターを合わせると n との gcd が表示され、クリックするとオイラーの定理の a として使えます。「グラフ」は上限までの各 k について φ(k) を表示します。点をクリックするとその数を開きます。「逆算」は φ(n) = m となるすべての n を一覧にします。どれかをクリックすると開きます。

          使い方

          1. 10^18までの整数 n を入力するか、φ(60)、RSA の法、カーマイケル数561などの計算例を選びます。
          2. φ(n)、素因数、あなたの数で書いた積の公式を読みます。500までは1から n までの数にポインターを合わせると n との gcd が表示され、どれかをクリックするとその数でオイラーの定理を確かめられます。
          3. 「グラフ」に切り替えると100,000までの各 k の φ(k) が、「逆算」に切り替えると φ(n) = m となるすべての n が表示されます。

          φ(n) の計算方法

          n を素因数分解し、n を割り切る各素数 p について n に (1 − 1/p) を掛けます。60 = 2² × 3 × 5 なら 60 × 1/2 × 2/3 × 4/5 = 16 です。消していく方法でも同じ数になります。60個の数のうち30個は偶数、30個の奇数のうち10個は3の倍数、残り20個のうち4個は5の倍数で、16個が残ります。素数のべきについての公式は φ(p^k) = p^(k−1)(p − 1) で、値を掛け合わせると φ(60) = 2 × 2 × 4 になります。難しいのは素因数分解です。この計算機は試し割り、ミラー–ラビン素数判定法、ポラードのロー法を使うので、9桁の素数2つの積である18桁の数でも1秒もかかりません。

          φ関数が使われる場面

          φ(n) は、0と1の間にある k/n のうちすでに既約分数になっているものの個数、n 時間の文字盤で針がすべての時刻を通る歩幅の個数(12時間の文字盤では1、5、7、11)、そして n を法として逆数を持つ数の個数を数えます。オイラーは、n と互いに素なすべての a について a^φ(n) ≡ 1 (mod n) となることを証明し、RSA 暗号はこれに基づいています。n = 3233 = 61 × 53 なら φ(n) = 60 × 52 = 3,120 で、公開指数17の秘密の相手は2,753です。17 × 2,753 = 15 × 3,120 + 1 だからです。

          よくある質問

          オイラーのφ関数とは何ですか?

          φ(n) は、1から n までの整数のうち、n と1以外の公約数を持たないものの個数です。1、2、4、5、7、8は9と互いに素で、3、6、9は因数3を共有するので、φ(9) = 6 です。約束として φ(1) = 1 とします。オイラーは1760年代にこの関数を研究し、ガウスが1801年に記号 φ を与え、ジェームズ・ジョセフ・シルベスターが1879年に英語名 totient を付けました。

          素数の φ はいくつですか?

          p − 1 です。1から p − 1 までのどの数も素数 p と互いに素なので、φ(97) = 96 です。素数のべきでは φ(p^k) = p^k − p^(k−1) です。公約数を持つのは p の倍数だけだからです。φ(81) = 81 − 27 = 54 となります。

          オイラーの定理とはどんな定理ですか?

          a と n が互いに素なら、a^φ(n) を n で割った余りは1になります。n = 60、a = 7 では φ(60) = 16 で、7^16 ≡ 1 (mod 60) です。フェルマーの小定理は n が素数の場合です。もっと小さい指数で足りることもよくあります。7^4 = 2,401 = 40 × 60 + 1 です。n と互いに素なすべての a について成り立つ最小の指数はカーマイケル関数 λ(n) で、60では4です。

          2つの数の φ の値が同じになることはありますか?

          はい、ふつうは複数あります。φ(n) = 24 となるのは n = 35、39、45、52、56、70、72、78、84、90 です。φ の値に決してならない偶数もあり、最小は14です。また、n = 3 以降 φ(n) は偶数なので、1より大きい奇数も値になりません。ロバート・カーマイケルは1907年に、ちょうど1回だけとられる値はないと主張しました。これはいまも証明されておらず、ケヴィン・フォードは1998年に、例外があるとすれば10^(10^10)より大きくなければならないことを示しました。

          どのくらい大きな数を入力できますか?

          10^18までの任意の整数です。計算機はブラウザー内で厳密な整数演算によって素因数分解するので、φ(10^18) = 4 × 10^17 や φ(999,999,866,000,004,473) = 999,999,864,000,004,608 も最後の桁まで正確です。1から n までの数は500まで描かれ、グラフは100,000まで、逆算は10^10までの値に対応します。

          試してみますか?

          ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

          エディターへ