オイラー関数の定義・性質4つとその証明

数論

オイラー関数,あるいはオイラーのファイ関数・オイラーのトーシェント関数とは, 1,2,3,\dots, n-1 のうち,n と互いに素なものの個数を指します。

これについて,その定義・性質を述べ,証明していきましょう。

オイラー関数(トーシェント関数)とは

定義(オイラー関数)

1,2,3,\dots, n-1 のうち,n と互いに素なものの個数を \color{red}\boldsymbol{\phi(n)} と表し,オイラー関数 (Euler’s function) またはオイラーのファイ関数オイラーのトーシェント関数 (Euler’s totient function) という。

「互いに素」とは,最大公約数が 1 であるということです。

たとえば, 1 から 9 のうち, 10 と互いに素なものは 1,3, 7,9 ですから, \phi(10)=4 になります。

定義から明らかに \phi(n)\le n-1 が成立しますね。

オイラー関数の性質とその証明

さて,ここからはオイラー関数の重要な性質を述べ,それを証明しましょう。

オイラー関数の性質

定理(オイラー関数の性質)

  1. m,n を互いに素な正の整数とするとき, \color{red}\phi(mn)=\phi(m)\phi(n) である(乗法的関数という)。
  2. n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} を素因数分解とすると, \color{red}\begin{aligned}\phi(n)&= n\prod_{j=1}^k \left(1-\frac{1}{p_j}\right) \\&=\small{n\!\left(1-\frac{1}{p_1}\right)\! \!\left(1-\frac{1}{p_2}\right)\dots \left(1-\frac{1}{p_k}\right) }.\end{aligned}
  3. \color{red}\displaystyle \sum_{d\mid n}\phi(d) =n. ただし, \displaystyle \sum_{d\mid n} とは,n の正の約数 d 全体で和を取ることを指す。
  4. a,n を互いに素な整数とするとき,\color{red} a^{\phi(n)}\equiv 1 \pmod n (オイラーの定理→【数論】オイラーの定理とその2通りの証明)。

2.はオイラー関数の計算に便利ですね。たとえば, 1260=2^2\times3^2\times5\times 7 ですから,

\begin{aligned} \phi(1260) &= 1260(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{7})\\ &= 288\end{aligned}


と計算できるわけです。

また,4.はフェルマーの小定理の一般化です。

オイラー関数の性質の証明

さて,証明していきましょう。

証明

1. \phi(mn)=\phi(m)\phi(n)\; (\operatorname{gcd}(m,n)=1) について

中国剰余定理より, m と互いに素な整数 a と, n と互いに素な整数 b の組 (a,b) に対し,

c\equiv a\pmod m,\quad c\equiv b\pmod n


となる, mn と互いに素である整数 c mn を法としてただ一つ存在し,この対応は1対1である。これは, \phi(mn)=\phi(m)\phi(n) を意味する。

2. \phi(n)= n\prod_{j=1}^k \left(1-\frac{1}{p_j}\right) について

まず,素数のべき乗のときに成立することを示す。 p を素数,k を正の整数とし, n=p^k とする。p と互いに素でないものは,p の倍数であるから, \phi(p^k)=p^k-p^{k-1}=p^k(1-1/p) が成り立つ。

これと,1.より,結論を得る。

3. \sum_{d\mid n}\phi(d) =n について

A_d=\{x_{1}, x_{2}, \dots ,x_{\phi(d)}\} を,1,2,3,\dots, d-1 のうち,d と互いに素な整数の集合とする。

さらに T_d = \{(d, x)\mid x\in A_d\} とし, T= \bigcup_{d\mid n} T_d とする( T=\bigoplus_{d\mid n} A_d とかくこともある)。このとき,特に \#A_d= \# T_d =\phi(d),\; \# T = \sum_{d\mid n} \phi(d) である。

f\colon \{1,2,3\dots, n\} \to T


f(m) = (n/d', {m}/{d'})\in T_{n/d'} \subset T(ただし d'=\operatorname{gcd} (m,n) )と定めると,これは全単射である。実際, f^{-1} (d,x) = (n/d) x となる。

したがって,\# T = \#\{1,2,3,\dots, n\}=n となって,結論を得る。

4. オイラーの定理について

以下で証明している。

証明終

3.の証明が少々難しいかもしれません。たとえば,n=10 で考えることにすると,f(1)=(10,1), f(2)= (5,1), f(3)=(10, 3), f(4)= (5, 2),f(5)=(2,1), f(6)= (5,3),f(7)=(10,7),f(8)=(5,4), f(9)= (10,9), f(10)=(1,1) となります。

タイトルとURLをコピーしました