オイラーのトーシェント関数 計算ツール

オイラーのトーシェント関数 計算ツール

成長中 AI Skill PRO

計算を入力してください

公式

φ(n)=n∏p|n(1−1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
利用統計

広告

結果

オイラーのφ関数(210)
48
と互いに素な整数 210 in [1, n]
n を入力 210
互いに異なる素因数 2, 3, 5, 7

このページの誤りを報告

オイラーのトーシェント関数とは?

オイラーのトーシェント関数は \(\varphi(n)\) と書き、1からnまでの正の整数のうち、nとの最大公約数が1である数、つまりnと互いに素な整数がいくつあるかを数えます。たとえば \(\varphi(9) = 6\) です。これは 1、2、4、5、7、8 がいずれも9と互いに素だからです。この関数は整数論の基礎をなすもので、暗号理論のさまざまな場面に登場します。最もよく知られているのが RSA 暗号で、鍵生成に用いるモジュラ逆数を求める際に \(\varphi(n)\) が重要な役割を果たします。

1から12までの整数のグリッドで、12と互いに素な数を強調表示
オイラーのトーシェント関数は、n と公約数を持たない n 以下の整数の個数を数えます。

この計算ツールの使い方

任意の正の整数nを入力して計算ボタンを押すだけです。ツールがnを互いに異なる素因数に分解し、積の公式を適用して \(\varphi(n)\) を瞬時に返します。あわせて見つかった素因数の一覧も表示します。小さな数はもちろん、最大10億までの非常に大きな数にも対応しています。

公式の解説

トーシェント関数を効率よく求める方法が、次の積の公式です。

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

ここで積はnを割り切る互いに異なるすべての素数pについてとります。

必要なのは互いに異なる素数だけで、各素数が何乗で現れるか(重複度)は関係ありません。それぞれの因子 \(\left(1 - \frac{1}{p}\right)\) が、その素数で割り切れる数の割合を取り除いていく仕組みです。

広告
n を素因数に分解し、(1 − 1/p) の項を掛ける様子を示す図
積の公式は、相異なる各素因数 p について n に \(\left(1 - \frac{1}{p}\right)\) を掛けます。

計算例

n = 36 で考えてみましょう。素因数分解は \(2^2 \times 3^2\) なので、互いに異なる素数は 2 と 3 です。したがって、

$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}.$$

つまり、1から36までのうち36と互いに素な整数は、ちょうど12個ということになります。

その他の計算例

例1:素数の場合、φ(13)

13は素数なので、その唯一の素因数は13自身です:

\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12。これは素数の近道公式 \(\varphi(p) = p-1\) と一致します。

例2:素数のべき乗の場合、φ(32)

因数分解:\(32 = 2^5\)。異なる素因数は2のみです。

\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16。

同等の素数べき形式:\(\varphi(p^k) = p^k - p^{k-1}\)。したがって \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\)。これは1から31までの奇数とちょうど一致します。

例3:3つ以上の異なる素数の場合、φ(210)

因数分解:\(210 = 2 \cdot 3 \cdot 5 \cdot 7\)。

  1. \(210\) から始めます。
  2. \(1-\frac{1}{2} = \frac{1}{2}\) を掛けます:\(210 \cdot \frac{1}{2} = 105\)。
  3. \(1-\frac{1}{3} = \frac{2}{3}\) を掛けます:\(105 \cdot \frac{2}{3} = 70\)。
  4. \(1-\frac{1}{5} = \frac{4}{5}\) を掛けます:\(70 \cdot \frac{4}{5} = 56\)。
  5. \(1-\frac{1}{7} = \frac{6}{7}\) を掛けます:\(56 \cdot \frac{6}{7} = 48\)。

したがって \(\varphi(210) = \)48。積の規則では、各異なる素数は一度だけ使われることに注意してください。例えば、\(60 = 2^2 \cdot 3 \cdot 5\) の場合は \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\) となります。

広告

φ(n)の解釈と用途

  • 素数判定との関係:\(n \ge 2\) について、\(\varphi(n) = n-1\) であることは、\(n\) が素数であることと同値です。素数より小さいすべての数はそれと互いに素です。\(n\) が合成数であれば、それより小さい数の少なくとも1つは共通因数を持つため、\(\varphi(n) < n-1\) となります。
  • 単数群:\(\varphi(n)\) は、法 \(n\) における単数群の元の個数、すなわち法 \(n\) で乗法的逆元を持つ剰余類の数です。\(n = 15\) の場合、これらは 1, 2, 4, 7, 8, 11, 13, 14 であり、8個の元があります。
  • オイラーの定理:\(\gcd(a, n) = 1\) ならば、\(a^{\varphi(n)} \equiv 1 \pmod{n}\) です。例:\(a = 2\)、\(n = 15\)、\(\varphi(15) = \)8、そして \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\)。フェルマーの小定理は、\(n = p\)(素数)の特別な場合です。
  • RSA暗号:\(n = pq\)(\(p\) と \(q\) は異なる素数)のとき、\(\varphi(n) = (p-1)(q-1)\) です。\(n = 15 = 3 \cdot 5\) の場合:\(\varphi(15) = 2 \cdot 4 = 8\)。公開指数 \(e\) は \(\varphi(n)\) と互いに素でなければならず、秘密指数 \(d\) は \(ed \equiv 1 \pmod{\varphi(n)}\) を満たします。実際のRSAでは、数百桁の長さの素数を使用します。\(n\) を因数分解できる者は \(\varphi(n)\) を計算できるため、安全性は因数分解の困難さに依存しています。
  • 比は異なる素因数にのみ依存します:\(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\)。指数は影響しません。例えば、6と12はどちらも素因数の集合が {2, 3} なので、\(\varphi(6)/6 = 2/6 = 1/3\) かつ \(\varphi(12)/12 = 4/12 = 1/3\) です。

よくある質問

\(\varphi(1)\) はいくつ? 慣例として \(\varphi(1) = 1\) とします。1はそれ自身と互いに素だからです。

素数pのφの値は? 任意の素数pについて \(\varphi(p) = p - 1\) です。1からp−1までのすべての整数がpと互いに素だからです。

φは乗法的な関数? はい。\(\gcd(a, b) = 1\) のとき \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\) が成り立ちます。互いに異なる素数についての積をとる公式が機能するのは、まさにこの性質によるものです。

最終更新:

数学と統計で人気の電卓

数学と統計の電卓をすべて見る