§オイラー関数(Euler's function)

オイラー関数(Euler's function)

n を自然数として、 n 以下の自然数のうち、n と互いに素な自然数の個数を、Φ(n) と表し、これをオイラー関数(Euler's function)という。「オイラーのトーション関数」(Euler's totient function)という場合もある。

1 < n のときは、 n と n は互いに素ではないので、 n - 1 以下の自然数のうち、n と互いに素な自然数の個数を数えればいい。

n = 6 のとき、
1 , 2 , 3 , 4 , 5 の中で 6 と互いに素なのは 1 , 5 の 2個だから、Φ(6) = 2 となる。

Φ(1) = 1 である。
Φ(2) = 1 である。
Φ(3) = 2 である。

では、オイラー関数を計算してみましょう。

整数を入れてください。7*11というような積でもOKです。
n =

結果です。
Φ(n) =
nと互いに素な数 :

オイラーの関数に関する定理

ここでは、字が小さくなりすぎて見にくいということがないように、便宜上 pn を p[n] と表記することにする。

自然数nを素因数分解し、同じ素数をまとめて、 a = p[1]e[1]p[2]e[2] ... p[n]e[n] となったとすると、
euler(n)=n(1-1/p1)(1-1/p2)...(1-1/pn)
である。
p , q が互いに素ならば、
Φ(pq) = Φ(p)Φ(q)
n が素数のとき、Φ(n) = n - 1 である。
n が 3 以上の素数ならば、 n は奇数だから、 n - 1 は偶数である。従って、 Φ(n) は偶数である。
n を 3 以上の素数、 e を自然数とすると、 Φ(ne) は偶数である。
なぜなら、 Φ(n) = n - 1 は偶数だから、 Φ(n) = 2a とすると、
Φ(n) = 2a
Φ(n2) = 2an
Φ(n3) = 2an2
Φ(n4) = 2an3
…
となる。偶数と整数を掛けると、結果は偶数になるから、Φ(ne) は偶数である。
sigma(condition:=(d is divisor of n),sum_of:=(euler(d)=n))=n
オイラーの定理 (Euler's theorem)
gcd( a , n ) = 1 のとき、 aΦ(n) ≡ 1 (mod n)

(ちなみに、位相幾何学の分野でもオイラーの定理と呼ばれるもの

「球面と位相が同じ二次元閉多面体について、
頂点の数 - 辺の数 + 面の数 = 2 」
がある。また、オイレルとは Euler の別の読み方なので、オイレルの定理とはオイラーの定理のこと。)
フェルマーの定理(Fermat's theorem)または、フェルマーの小定理(Fermat's little theorem)とも呼ばれる定理
p を素数として、 gcd( a , p ) = 1 のとき、 ap - 1 ≡ 1 (mod p)