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