互いに素な自然数の個数(オイラー関数)

スポンサーリンク
$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)\ である.

スポンサーリンク
スポンサーリンク
高校数学A 整数
シェアする
受験の月をフォローする
受験の月