$nを自然数とする.\ \ n以下の自然数で,\ nとの最大公約数が1となる自然数の個数を$ \\ \hspace{.5zw} (2)\ \ $p,\ qを互いに異なる素数とするとき,\ \phi(pq)を求めよ.$ \\[.8zh] \hspace{.5zw} (3)\ \ $pを素数,\ kを正の整数とするとき,\ \phi(p^k)を求めよ.$ \\[.8zh] \hspace{.5zw} (4)\ \ $p,\ q,\ rを互いに異なる素数とするとき,\ \phi(pqr)を求めよ.$ \\ {互いに素な自然数の個数（オイラー関数）}}}} \\\\[.5zh] 要は,\ $\bm{\textcolor{magenta}{自然数nと互いに素なn以下の自然数の個数が\ \phi(n)}}である.$ \\\\[.5zh] (1)\ \ $\textcolor{red}{13は素数であるから,\ それより小さい自然数はすべて13と互いに素}である.$ \\[.2zh] \phantom{ (1)}\ \ よって $\bm{\phi(13)=12}$ \\[1zh] \phantom{ (1)}\ \ $15までに,\ \textcolor{cyan}{3の倍数は5個,\ 5の倍数は3個,\ 15の倍数は1個}ある.$ \\[.2zh] \phantom{ (1)}\ \ $30までに,\ \textcolor{cyan}{2の倍数は15個,\ 3の倍数は10個,\ 5の倍数は6個,}$ \\[.2zh] \phantom{ (1)}\ \ $\textcolor{cyan}{6の倍数は5個,\ 10の倍数は3個,\ 15の倍数は2個,\ 30の倍数は1個}ある. 30程度までならすべて書き出すことも可能だが,\ それでは(2)(3)に通用しない. \\[.2zh] 一旦本質を理解してしまえば実に単純な構造であり,\ 容易に一般化できる. \\[1zh] \bm{n=(素数)ならば,\ それより小さいすべての自然数と互いに素}である. \\[.2zh] n=13ならば,\ 1\,～\,12すべてと互いに素である.\ 13とは最大公約数が13になるので不適である. \\[1zh] 自然数nと互いに素である自然数の個数を直接的に数えるは難しい. \\[.2zh] \bm{全体の自然数の個数nからnと互いに素でない自然数の個数を引く}と考えることになる. \\[1zh] 15=3\cdot5\ より,\ 15と互いに素ではないのは3の倍数と5の倍数である. \\[.2zh] つまり,\ \bm{3の倍数\dot{ま}\dot{た}\dot{は}\,5の倍数の個数を全体の個数15から引く}ことで,\ \phi(15)を求められる. \\[.2zh] 個数を数えるとき,\ 3の倍数かつ5の倍数を二重に数えないように注意する必要がある. \\[.2zh] 要するに,\ \bm{(3の倍数または5の倍数)=(3の倍数)+(5の倍数)-(3かつ5の倍数)}\ である. \\[.2zh] なお,\ 3かつ5の倍数は,\ その最小公倍数15の倍数である. \\[.2zh] 各集合を\bm{ベン図}でとらえると一目瞭然である. \\[.2zh] 結局,\ 周りの色塗り部分の個数を求めればよいわけである. \\[1zh] 30=2\cdot3\cdot5より,\ \bm{2の倍数または3の倍数または5の倍数の個数を30から引く}と\,\phi(30)が求まる. \\[.2zh] 2,\ 3,\ 5の倍数の集合をそれぞれA,\ B,\ Cとすると \\[.2zh] n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C) {$pqまでに,\ \textcolor{cyan}{pの倍数は\,\bunsuu{pq}{p}=q個,\ \ qの倍数は\,\bunsuu{pq}{q}=p個,\ \ pqの倍数は\,\bunsuu{pq}{pq}=1個}ある.$} \\[1zh] \centerline{$\therefore \bm{\phi(pq)}=\textcolor{red}{pq-(q+p-1)}=pq-p-q+1=\bm{(p-1)(q-1)}$} {p^kと互いに素\underline{でない}ものは素数pの倍数}であり, (4)\ \ $pqrまでに,\ \textcolor{cyan}{pの倍数は\,\bunsuu{pqr}{p}=qr個,\ \ qの倍数は\,\bunsuu{pqr}{q}=pr個,}$ \\[.8zh] \phantom{ (1)}\ \ $\textcolor{cyan}{rの倍数は\,\bunsuu{pqr}{r}=pq個,\ \ pqの倍数は\,\bunsuu{pqr}{pq}=r個,\ \ qrの倍数は\,\bunsuu{pqr}{qr}=p個,}$ \\[.8zh] \phantom{ (1)}\ \ $\textcolor{cyan}{rpの倍数は\,\bunsuu{pqr}{rp}=q個,\ \ pqrの倍数は\,\bunsuu{pqr}{pqr}=1個}ある.$ \\[1.2zh] \centerline{$\therefore \bm{\phi(pqr)}=\textcolor{red}{pqr-(qr+pr+pq-p-q-r+1)}=\bm{(p-1)(q-1)(r-1)}$} (2)\ \ (1)の\ \phi(15)を一般化したものである. \\[.2zh] \phantom{(2)}\ \ p,\ qは互いに異なる素数なので,\ \bm{pの倍数またはqの倍数の個数を全体の個数pqから引く.} \\[.2zh] \phantom{(2)}\ \ pqまでのpの倍数はpqをpで割るとわかる. \\[.2zh] \phantom{(2)}\ \ 具体的には,\ p,\ 2p,\ 3p,\ \cdots\cdots,\ (q-1)p,\ qp\ のq個ある. \\[.2zh] \phantom{(2)}\ \ 15までの3の倍数が\ 1\cdot3,\ 2\cdot3,\ 3\cdot3,\ 4\cdot3,\ 5\cdot3\ の5個であるのと同じである. \\[.2zh] \phantom{(2)}\ \ 後は\ \phi(15)と同様にして\ \phi(pq)が求まる.\ 最終的に\bm{因数分解できる}ことを覚えておくとよい. \\[1zh] (3)\ \ (1)の\ \phi(16)を一般化したものである. \\[1zh] (4)\ \ (1)の\ \phi(30)を一般化したものである. オイラー関数\ \phi(n)}} \bm{\textcolor{red}{自然数nと互いに素なn以下の自然数の個数}}$ \\\\ $[1]\ \ \bm{\textcolor{cyan}{素数p}}に対して \bm{\textcolor{red}{\phi(p)=p-1}}$ \\[1.5zh] $[2]\ \ \bm{\textcolor{cyan}{異なる素数p,\ q}}に対して$ \\[.2zh] $\bm{\textcolor{red}{\phi(pq)=(p-1)(q-1)=pq\hspace{-.3zw}\left(1-\bunsuu1p\right)\hspace{-.5zw}\left(1-\bunsuu1q\right)}}$ \\\\ $[3]\ \ \bm{\textcolor{cyan}{異なる素数p,\ q,\ r}}に対して$ \\[.5zh] $\bm{\textcolor{red}{\phi(pqr)=(p-1)(q-1)(r-1)}}$ \\[.5zh] $\bm{\textcolor{red}{\phantom{\phi(pqr)}=pqr\hspace{-.3zw}\left(1-\bunsuu1p\right)\hspace{-.5zw}\left(1-\bunsuu1q\right)\hspace{-.5zw}\left(1-\bunsuu1r\right)}}$ \\\\[.5zh] $[4]\ \ \bm{\textcolor{cyan}{素数p,\ 正の整数n}}に対して$ \\[.5zh] $\bm{\textcolor{red}{\phi(p^n)=p^n-p^{n-1}=p^n\hspace{-.3zw}\left(1-\bunsuu1p\right)}}$ \phi\ は「ファイ」と読む.\ 結果を覚えておくと,\ 問題の見通しがよくなる. \\[1zh] \text{[1]}は\ \phi(13)\ の一般化である. \\[.2zh] \text{[2]},\ [3],\ [4]は\ \phi(15),\ \phi(30),\ \phi(16)の一般化であり,\ (2)(3)(4)で示した. \\[1zh] p,\ q,\ rをくくりだして分数にした形は,\ \bm{確率的な観点でとらえる}と直感的に理解できる. \\[.2zh] 例として,\ 確率的な観点で\ \phi(30)\ を求めてみよう. \\[.2zh] 自然数には,\,2の倍数は2個に1個,\,3の倍数は3個に1個,\,5の倍数は5個に1個の割合で含まれる. \\[.2zh] よって,\ 2,\ 3,\ 5の倍数である確率はそれぞれ\,\bunsuu12,\ \bunsuu13,\ \bunsuu15\,である. \\[.8zh] ゆえに,\ 30個の自然数うち2の倍数でないものは 30\cdot\bunsuu12=15\ 個 \\[.8zh] この15個のうち,\ さらに3の倍数でないものは \ \ \,15\cdot\bunsuu23=10\ 個 \\[.8zh] この10個のうち,\ さらに5の倍数でないものは \ \ \,10\cdot\bunsuu45=8\ 個 \\[.8zh] は,\ 4つ以上の素数に対しても同様の法則で拡張できる. \\[1zh] 次のような\bm{既約分数の個数を求める問題もオイラー関数に帰着}する. \\[.5zh] 「\,\bunsuu{n}{30}\,が1より小さい既約分数となるような自然数nの個数を求めよ」 \\[.8zh] nは1\,～\,30までの自然数の中で30と互いに素である数なので,\ その個数は\ \phi(30)\ である.
