2.3.4 オイラー関数

1から$n$までの自然数のうち$n$と互いに素なもの個数を$\phi (n)$で表しオイラー関数（Euler function）といいます。本項ではオイラー関数の性質を見ていきましょう。

例 2.3.11

• $n=2$の場合
  1,2のうち2と互いに素なのものは1のみ。したがって、$\phi(2)=1$
• $n=3$の場合
  1,2,3のうち3と互いに素なものは1,2。したがって、$\phi(3)=2$
• $n=4$の場合
  1,2,3,4のうち4と互いに素なものは1,3。したがって、$\phi(4)=2$
• $n=5$の場合
  1,2,3,4,5のうち5と互いに素なものは1,2,3,4。したがって、$\phi(5)=4$
• $n=6$の場合
  1,2,3,4,5,6のうち6と互いに素なものは1,5。したがって、$\phi(6)=2$
• $n=7$の場合
  1,2,3,4,5,6,7のうち7と互いに素なものは1,2,3,4,5,6。したがって、$\phi(7)=6$
• $n=8$の場合
  1,2,3,4,5,6,7,8のうち8と互いに素なものは1,3,5,7。したがって、$\phi(8)=4$
• $n=9$の場合
  1から9までの自然数のうち9と互いに素なものは1,2,4,5,7,8。したがって、$\phi(9)=6$
• $n=10$の場合
  1から10までの自然数のうち10と互いに素なものは1,3,7,9。したがって、 $\phi(10)=4$
• $n=11$の場合
  1から11までの自然数のうち11と互いに素なものは1,2,3,4,5,6,7,8,9,10。したがって、 $\phi(11)=10$
• $n=12$の場合
  1から12までの自然数のうち12と互いに素なものは1,5,7,11。したがって、 $\phi(12)=4$

以上をまとめると、

表 2.4: オイラー関数$\phi (n)$

この表から素数$p$のとき $\phi(p)=p-1$になっていること、$n,m$が互いにそのとき $\phi(nm)=\phi(n)\phi(m)$となっていることなどが分かります。
次の定理により$\phi (n)$は求めることができます。

定理 2.3.12
（1）$p$を素数とすると $\phi(p^n)=p^n-p^{n-1}$
（2）$n,m$を互いに素な自然数とすると $\phi(nm)=\phi(n)\phi(m)$

証明
（1）1から$p^n$までの自然数のうち$p^n$と互いに素なものは、1から$p^n$までの自然数で素因数に$p$を含まないもの。 1から$p$までの自然数で素因数に$p$を含むものは、 $p,2p,3p,\cdots,p^{n-1}p$の$p^{n-1}$個ある。したがって、 $\phi(p^n)=p^n-p^{n-1}$
（2）の証明は、後に、中国剰余定理を用いて行います。

（2）は互いに素な数に対して積が保存しており、このような性質を乗法的であるといいます。

Remark 2.3.13
$\phi (n)$は、 $\mathbb{Z}/n\mathbb{Z}$のうち$n$と互いに素なものの個数ですので、 $\mathbb{Z}/n\mathbb{Z}$の乗法群 $（\mathbb{Z}/n\mathbb{Z}）^\times$の元の個数と一致します。
一方、中国剰余定理より、$n,m$が互いに素なとき $\mathbb{Z}/nm\mathbb{Z}\cong (\mathbb{Z}/n\mathbb{Z})\times(\mathbb{Z}/m\mathbb{Z})$ですのでこれらの乗法群を考えると、 $(\mathbb{Z}/nm\mathbb{Z}\cong)^\times\cong (\mathbb{Z}/n\mathbb{Z})^\times\times(\mathbb{Z}/m\mathbb{Z})\times$であり、 $\phi(nm)=\phi(n)\phi(m)$が分かります。