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

スポンサーリンク
nを自然数とするとき,\ m nでmとnの最大公約数が1となる自然$ $数mの個数をφ(n)とする.            [名古屋大・改]$  $φ(13),φ(15),φ(16),φ(30)\ を求めよ.$  $p,\ qを互いに異なる素数とするとき,\ φ(pq)を求めよ.$  $pを素数,\ kを正の整数とするとき,\ φ(p^k)を求めよ.$ n以下で,\ nと互いに素な自然数の個数が\ φ(n)である.$  $素数13より小さい自然数は全て13と互いに素}である.$ { }よって ${φ(13)=12}$ { }$15までに,\ 3の倍数は5個,\ 5の倍数は3個,\ 15の倍数は1個}ある.$ { }$よって {φ(15)}=15-(5+3-1)}={8}$ { }$16=2⁴と互いに素でない}のは2の倍数}であり,\ 16までに8個ある.$ { }$よって {φ(16)}=16-8}={8}$ { }$30までに,\ 2の倍数15個,\ 3の倍数10個,\ 5の倍数6個,}$ { }$6の倍数5個,\ 10の倍数3個,\ 15の倍数2個,\ 30の倍数1個}ある.  $pの倍数は,p,\ 2p,\ ,\ (q-1)p,\ qpのq個}ある.$ { }$qの倍数は,q,\ 2q,\ ,\ (p-1)q,\ pqのp個}ある.$ { }$pqの倍数は,\ pqの1個}である.$ p^kと互いに素でない}ものは素数pの倍数}であり,\ {p^k}{p}=p^{k-1}個ある.$ 30程度までなら{全て書き出す}ほうが確実だったりする. ここでは,\ の一般化を見据えて解くことにする. {n=(素数)ならば,\ それより小さい全ての自然数と互いに素}である. よって,\ 13ならば,\ 1~12全てと互いに素である. 15=35\ より,\ 3の倍数でも5の倍数でもない数の個数を求める必要がある. これは,\ {3の倍数または}5の倍数の個数を15から除く}ことで得られる. 各集合を{ベン図}でとらえ,\ 個数を数えるのがわかりやすいだろう. {(3の倍数または5の倍数)=(3の倍数)+(5の倍数)-(3かつ5の倍数)} なお,\ 3かつ5の倍数は,\ その最小公倍数15の倍数である. 16は2⁴であるから,\ {互いに素でないものを取り除く}ほうが速い. 2の倍数のとき16と互いに素でなくなり,\ 162=8\ 個ある. 30=235より,\ 2の倍数でも3の倍数でも5の倍数でもない数の個数を求める. {2の倍数または3の倍数または5の倍数の個数を30から除く}ことで得られる. 2の倍数または3の倍数または5の倍数の個数を集合の記号を用いて表すと \ の\ φ(15)を一般化したものである. \ p,\ qは互いに素であるから,\ {pの倍数でもqの倍数でもない数の個数}を求める. \ pqまでのpの倍数は,\ 1 p,\ 2 p,\ ,\ (q-1) p,\ q p\ のq個ある. \ 15までの3の倍数が,\ 13,\ 23,\ 33,\ 43,\ 53\ の5個だったのと等しい. \ 後は\ φ(15)と同様に考えて\ φ(pq)が求められる. \ うまく因数分解できることを覚えておくとよい. \ の\ φ(16)を一般化したものである. {p^kまでのpで割り切れる数の個数を求め,\ 取り除く.} オイラー関数\ φ(n):{自然数nと互いに素なn以下の自然数の個数$   ${素数p異なる素数素数p,\ 正の整数n} φ\ は「ファイ」と読む.\ 関係は覚なくてよいが,\ 知識があれば見通しがよくなる. }は\ φ(13)\ の一般化である. },\ [4]は\ φ(15),\ φ(16)の一般化であり,\ で示した. [3]}は\ φ(30)\ の一般化で,\ の拡張である. [3]}は,\ {確率的観点でとらえる}と直感的に理解できる. 試しに,\ 確率的観点で\ φ(30)\ を求めてみる. 2の倍数は2個に1個,\ 3の倍数は3個に1個,\ 5の倍数は5個に1個表れる. よって,\ 30個のうち2の倍数でないものは 3012=15\ 個 このうち,\ 3の倍数でないものは このうち,\ 5の倍数でないものは, これは[3]の\ φ(pqr)\ の式と同じ形である. },\ [3]は,\ 4つ以上の素数に対しても同様の規則で拡張できる. ちなみに,\ 次のような{既約分数の個数を求める問題もオイラー関数に帰着}する. 「{n}{30}が1より小さい既約分数となるような自然数nの個数を求めよ」 nは1~30までの数の中で30と互いに素である数なので,\ 個数は\ φ(30)\ である.
スポンサーリンク
スポンサーリンク
高校数学A 整数
受験の月をフォローする
受験の月
タイトルとURLをコピーしました