オイラーのトーシェント関数とは？
オイラーのトーシェント関数は \(\varphi(n)\) と書き、1からnまでの正の整数のうち、nとの最大公約数が1である数、つまりnと互いに素な整数がいくつあるかを数えます。たとえば \(\varphi(9) = 6\) です。これは 1、2、4、5、7、8 がいずれも9と互いに素だからです。この関数は整数論の基礎をなすもので、暗号理論のさまざまな場面に登場します。最もよく知られているのが RSA 暗号で、鍵生成に用いるモジュラ逆数を求める際に \(\varphi(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 = 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個ということになります。
よくある質問
\(\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)\) が成り立ちます。互いに異なる素数についての積をとる公式が機能するのは、まさにこの性質によるものです。
