検索用コード
nを自然数とするとき,\ m\leqq nでmとnの最大公約数が1となる自然$ \\[.2zh] \hspace{.5zw}$数mの個数を\phi(n)とする.            \ \ [名古屋大・改]$ \\[1zh] \hspace{.5zw} (1)\ \ $\phi(13),\ \ \phi(15),\ \ \phi(16),\ \ \phi(30)\ を求めよ.$ \\[.5zh] \hspace{.5zw} (2)\ \ $p,\ qを互いに異なる素数とするとき,\ \phi(pq)を求めよ.$ \\[.5zh] \hspace{.5zw} (3)\ \ $pを素数,\ kを正の整数とするとき,\ \phi(p^k)を求めよ.$ \\ 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)}\ \ $よって \bm{\phi(15)}=\textcolor{red}{15-(5+3-1)}=\bm{8}$ \\[1zh] \phantom{ (1)}\ \ $\textcolor[named]{ForestGreen}{16=2^4\,と互いに素\underline{でない}のは2の倍数}であり,\ 16までに8個ある.$ \\[.2zh] \phantom{ (1)}\ \ $よって \bm{\phi(16)}=\textcolor{red}{16-8}=\bm{8}$ \\[1zh] \phantom{ (1)}\ \ $30までに,\ \textcolor{cyan}{2の倍数15個,\ 3の倍数10個,\ 5の倍数6個,}$ \\[.2zh] \phantom{ (1)}\ \ $\textcolor{cyan}{6の倍数5個,\ 10の倍数3個,\ 15の倍数2個,\ 30の倍数1個}ある.  (2)\ \ $pの倍数は,\ \ \textcolor{cyan}{p,\ 2p,\ \cdots\cdots,\ (q-1)p,\ qp\ \ のq個}ある.$ \\[.2zh] \phantom{ (1)}\ \ $qの倍数は,\ \ \textcolor{cyan}{q,\ 2q,\ \cdots\cdots,\ (p-1)q,\ pq\ \ のp個}ある.$ \\[.2zh] \phantom{ (1)}\ \ $pqの倍数は,\ \textcolor{cyan}{pqの1個}である.$ \\[.5zh] p^kと互いに素\underline{でない}ものは素数pの倍数}であり,\ \bunsuu{p^k}{p}=p^{k-1}\,個ある.$ 30程度までなら\bm{全て書き出す}ほうが確実だったりする. \\ ここでは,\ (2)(3)の一般化を見据えて解くことにする. \\[1zh] \bm{n=(素数)ならば,\ それより小さい全ての自然数と互いに素}である. \\ よって,\ 13ならば,\ 1~12全てと互いに素である. \\[1zh] 15=3\cdot5\ より,\ 3の倍数でも5の倍数でもない数の個数を求める必要がある. \\ これは,\ \bm{3の倍数\,\underline{または}\,5の倍数の個数を15から除く}ことで得られる. \\ 各集合を\bm{ベン図}でとらえ,\ 個数を数えるのがわかりやすいだろう. \\ \bm{(3の倍数または5の倍数)=(3の倍数)+(5の倍数)-(3かつ5の倍数)} \\ なお,\ 3かつ5の倍数は,\ その最小公倍数15の倍数である. \\[1zh] 16は2^4であるから,\ \bm{互いに素でないものを取り除く}ほうが速い. \\ 2の倍数のとき16と互いに素でなくなり,\ 16\div2=8\ 個ある. \\[1zh] 30=2\cdot3\cdot5より,\ 2の倍数でも3の倍数でも5の倍数でもない数の個数を求める. \\ \bm{2の倍数または3の倍数または5の倍数の個数を30から除く}ことで得られる. \\ 2の倍数または3の倍数または5の倍数の個数を集合の記号を用いて表すと (2)\ (1)の\ \phi(15)を一般化したものである. \\ \phantom{(2)}\ p,\ qは互いに素であるから,\ \bm{pの倍数でもqの倍数でもない数の個数}を求める. \\ \phantom{(2)}\ pqまでのpの倍数は,\ 1\cdot p,\ 2\cdot p,\ \cdots\cdots,\ (q-1)\cdot p,\ q\cdot p\ のq個ある. \\ \phantom{(2)}\ 15までの3の倍数が,\ 1\cdot3,\ 2\cdot3,\ 3\cdot3,\ 4\cdot3,\ 5\cdot3\ の5個だったのと等しい. \\ \phantom{(2)}\ 後は\ \phi(15)と同様に考えて\ \phi(pq)が求められる. \\ \phantom{(2)}\ うまく因数分解できることを覚えておくとよい. \\[1zh] (3)\ (1)の\ \phi(16)を一般化したものである. {p^kまでのpで割り切れる数の個数を求め,\ 取り除く.} オイラー関数\ \phi(n)}}:\bm{\textcolor{red}{自然数nと互いに素なn以下の自然数の個数}}$ \\\\   $[1]\ \ \bm{\textcolor{cyan}{素数p}}異なる素数素数p,\ 正の整数n} \phi\ は「ファイ」と読む.\ 関係は覚なくてよいが,\ 知識があれば見通しがよくなる. \\ \text{[1]}は\ \phi(13)\ の一般化である. \\ \text{[2]},\ [4]は\ \phi(15),\ \phi(16)の一般化であり,\ (2)(3)で示した. \\ \text{[3]}は\ \phi(30)\ の一般化で,\ [2]の拡張である. \\[1zh] \text{[3]}は,\ \bm{確率的観点でとらえる}と直感的に理解できる. \\ 試しに,\ 確率的観点で\ \phi(30)\ を求めてみる. \\ 2の倍数は2個に1個,\ 3の倍数は3個に1個,\ 5の倍数は5個に1個表れる. \\ よって,\ 30個のうち2の倍数でないものは 30\cdot\bunsuu12=15\ 個 \\[.5zh] このうち,\ 3の倍数でないものは このうち,\ 5の倍数でないものは, これは[3]の\ \phi(pqr)\ の式と同じ形である. \\ \text{[2]},\ [3]は,\ 4つ以上の素数に対しても同様の規則で拡張できる. \\[1zh] ちなみに,\ 次のような\bm{既約分数の個数を求める問題もオイラー関数に帰着}する. \\ 「\bunsuu{n}{30}が1より小さい既約分数となるような自然数nの個数を求めよ」 \\ nは1~30までの数の中で30と互いに素である数なので,\ 個数は\ \phi(30)\ である.