定義
オイラーのトーシェント関数、オイラーのφ関数とも。totientとは数学用語で「与えられた数以下でこれと素な整数の個数」というこの関数の意味そのもの。
例
φ(6) = 2 (1, 5)
φ(12) = 4 (1, 5, 7, 11)
φ(20) = 8 (1, 3, 7, 9, 11, 13, 17, 19)
素数に対するオイラー関数値
素数はそれ自身と1以外に約数を持たないので、オイラー関数値はその値から自身の分1を減じた値となる。
φ(p) = p − 1
2つの素数の積のオイラー関数値は、双方から1を減じた値の積になる。
φ(pq) = (p − 1)(q − 1)
これを納得するのに時間がかかった。まどろっこしいが以下のように考えた。
まず以下のことに気づく。
(1) 
次に2つの素数5と3で以下のように考えてみる。
まずφ(15)に関して。15以下の数のうち15と互いに素であるのは以下の8個。
1, 2, 4, 7, 8, 11, 13, 14
逆に互いに素でない(15と公約数を持つ)数は以下の6個。
3, 5, 6, 9, 10, 12
ここで以下のように考える。
- φ(5)に関してはカウントされる数は1, 2, 3, 4の4つで、φ(3)に関してはカウントされる数は1, 2の2つ
- これらの数に任意の自然数を掛けて15以下の自然数を作り出すことができる
- ところが3×5は素数の掛け算であり、上記の数に3や5以外の数をかけてもその結果は3×5と互いに素であることに変わりはない
- φ(3)でカウントする1, 2に対して5を掛ければ、3×5以下でこれと互いに素でない数が得られる
- またφ(5)でカウントする1, 2, 3, 4に対して3を掛ければ、3×5以下でこれと互いに素でない数が得られる
- しかも3と5はいずれも素数で互いに素なので、上記の結果に重複は生じない
φ(3)に関しては、対象となる数に5を掛けて以下が得られる。
1, 2 → 5, 10
φ(5)に関しては、対象となる数に3を掛けて以下が得られる。
1, 2, 3, 4 → 3, 6, 9, 12
以上を併せて、15に対して1を除いて互いに素でない6個の数が得られる。
すなわち、φ(pq)は以下のようにして得られる。
- 重複しないp − 1個、q − 1個の数がpqと互いに素でない
- pq自身1個もpqと互いに素でない
したがって以下のようになる。
(2) 