オイラーのφ関数

オイラーのトーシェント関数（オイラーのトーシェントかんすう、英: Euler's totient function）とは、正の整数 n に対して、 n と互いに素である 1 以上 n 以下の自然数の個数 φ(n) を与える数論的関数 φ である。これは と表すこともできる（ここで (m, n) は m と n の最大公約数を表す）。慣例的にギリシャ文字の φ （あるいは）で表記されるため、オイラーの φ 関数（ファイかんすう、phi function）とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。 例えば、1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 5 の 2 個であるから、定義によれば φ(6) = 2 である。また例えば 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6 と定まる。なおトーシェント関数の値域に含まれない自然数をノントーシェントという。 1 から 20 までの値は以下の通りである。 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8,… 1761年にレオンハルト・オイラーが発見したとされるが、それより数年前に日本の久留島義太が言及したとも言われる。