投稿日
重要度 難易度

互いに素な自然数とオイラー関数

こんにちは、リンス(@Lins016)です。
今回は互いに素な自然数とオイラー関数について学習していこう。

スポンサーリンク

オイラー関数

\(\small{ \ 1 \ }\)から\(\small{ \ n \ }\)までの自然数の中で\(\small{ \ n \ }\)と互いに素な自然数を求めるときに、簡単に求めることが出来るのがオイラー関数なんだ。本当はオイラーの\(\small{ \ \phi \ }\)(ファイ)関数って言うんだけど、高校数学では簡略化してオイラー関数って呼ぶことが多いかな。

でもオイラー関数は教科書に載ってない場合が多いから、ここできちんと理解しておこう。入試で出題されることもあるからね。

オイラー関数

\(\small{ \ n \ }\)以下の自然数で\(\small{ \ n \ }\)と互いに素である自然数の個数\(\small{ \ \phi(n) \ }\)は
\(\small{ \ \phi(n)=n\displaystyle \prod_{ i = 1 }^k\left(1-\displaystyle\frac{1}{p_i}\right) \ }\)
ただし\(\small{ \ p_i \ }\)は\(\small{ \ n \ }\)の素因数

\(\small{ \ n=2^a\cdot3^b\cdot5^c \ }\)のとき
\(\small{ \ \phi(n)=n\left(1-\displaystyle\frac{1}{2}\right)\left(1-\displaystyle\frac{1}{3}\right)\left(1-\displaystyle\frac{1}{5}\right) \ }\)

互いに素な数の求め方

まずはオイラー関数を使わないやり方で\(\small{ \ 108 \ }\)と互いに素である\(\small{ \ 108 \ }\)以下の自然数の個数を考えてみよう。

\(\small{ \ 108 \ }\)を素因数分解すると\(\small{ \ 108=2^2\times3^3 \ }\)だからつまり\(\small{ \ 108 \ }\)と互いに素になる自然数は約数に\(\small{ \ 2 \ }\)と\(\small{ \ 3 \ }\)を持たないってことになるよね。

\(\small{ \ 1 \ }\)~\(\small{ \ 108 \ }\)までの自然数のうち\(\small{ \ 2 \ }\)を約数に持つ(つまり\(\small{ \ 2 \ }\)の倍数である)自然数の個数は\(\small{ \ n(\mathrm{A})=\displaystyle\frac{108}{2}=54 \ }\)個。

同様に\(\small{ \ 1 \ }\)~\(\small{ \ 108 \ }\)までの自然数のうち\(\small{ \ 3 \ }\)を約数に持つ(つまり\(\small{ \ 3 \ }\)の倍数である)自然数の個数は\(\small{ \ n(\mathrm{B})=\displaystyle\frac{108}{3}=36 \ }\)個。

互いに素な自然数とオイラー関数-01

この\(\small{ \ 54 \ }\)個と\(\small{ \ 36 \ }\)個のうち\(\small{ \ 2 \ }\)の倍数かつ\(\small{ \ 3 \ }\)の倍数である共通のものが含まれているよね。それは\(\small{ \ 6 \ }\)を約数にもつ(\(\small{ \ 6 \ }\)の倍数である)自然数になるから\(\small{ \ n(\mathrm{A\cap B})=\displaystyle\frac{108}{6}=18 \ }\)

だから\(\small{ \ 108 \ }\)と互いに素である\(\small{ \ 108 \ }\)以下の自然数の個数は
\(\small{ \ 108-\left(54+36-18\right)=36 \ }\)個になるんだ。

集合の要素の個数については下の記事を復習しておこう。

▼あわせてCHECK▼(別ウィンドウで開きます)

オイラー関数への変形

\(\small{ \ 108 \ }\)と互いに素である\(\small{ \ 108 \ }\)以下の自然数の個数は\(\small{ \ 36 \ }\)個だったけど、この式をオイラー関数の形に変形してみよう。

\(\small{ \ 108-\left(54+36-18\right)\\[10pt] =108-\left(\displaystyle\frac{108}{2}+\displaystyle\frac{108}{3}-\displaystyle\frac{108}{6}\right)\\
=108\left\{1-\left(\displaystyle\frac{1}{2}+\displaystyle\frac{1}{3}-\displaystyle\frac{1}{6}\right)\right\}\\
=108\left(1-\displaystyle\frac{1}{2}-\displaystyle\frac{1}{3}+\displaystyle\frac{1}{6}\right)\\
=108\left(1-\displaystyle\frac{1}{2}\right)\left(1-\displaystyle\frac{1}{3}\right) \ }\)

この式が\(\small{ \ 108 \ }\)のオイラー関数の式になるんだ。
「\(\small{ \ 1-\displaystyle\frac{1}{2} \ }\)」の部分は\(\small{ \ 2 \ }\)を約数に持たないものが半分って考えることができるし、\(\small{ \ 2 \ }\)を約数に持たないものにさらに「\(\small{ \ 1-\displaystyle\frac{1}{3} \ }\)」をかけることによって\(\small{ \ 3 \ }\)を約数に持たないものが\(\small{ \ \displaystyle\frac{2}{3} \ }\)あるって考えることができるよね。

オイラー関数

次にオイラー関数\(\small{ \ \phi(n) \ }\)について考えていこう。
①素数\(\small{ \ p \ }\)に対して\(\small{ \ \phi(p)=p-1 \ }\)
\(\small{ \ p \ }\)が素数なら\(\small{ \ 1 \ }\)から\(\small{ \ p-1 \ }\)のうち\(\small{ \ p \ }\)の素因数である\(\small{ \ p \ }\)を因数に持つものは存在しないから\(\small{ \ \phi(p)=p-1 \ }\)になるよね。

②素数\(\small{ \ p \ }\)、自然数\(\small{ \ n \ }\)に対して\(\small{ \ \phi\left(p^n\right)=p^n-p^{n-1}=p^n\left(1-\displaystyle\frac{1}{p}\right) \ }\)
\(\small{ \ 1 \ }\)から\(\small{ \ p^n \ }\)の中で\(\small{ \ p \ }\)を因数として持つもの(つまり\(\small{ \ p \ }\)の倍数)は\(\small{ \ p^{n-1} \ }\)個あるから互いに素になる数は\(\small{ \ p^n-p^{n-1} \ }\)個ある。

\(\small{ \ 1 \ }\)から\(\small{ \ p^n \ }\)の中で\(\small{ \ p \ }\)を因数として持つもの(つまり\(\small{ \ p \ }\)の倍数)は\(\small{ \ p^{n-1} \ }\)個あるってところがすこしわかりにくいけど、 \(\small{ \ p \ }\)の倍数だけ取り出して書くと
\(\small{ \ p, \ 2p, \ 3p,\cdots, \ p^{n-2}p, \ p^{n-1}p \ }\)ってなるから\(\small{ \ p \ }\)の倍数は\(\small{ \ p^{n-1} \ }\)個あるよね。

③異なる素数\(\small{ \ p, \ q \ }\)に対して\(\small{ \ \phi(pq)=(p-1)(q-1)=pq\left(1-\displaystyle\frac{1}{p}\right)\left(1-\displaystyle\frac{1}{q}\right) \ }\)
この式は合同式を利用した証明とか色々な証明方法があるけど、今回は感覚的にこの式を掴んでみよう。
\(\small{ \ p, \ q \ }\)は素数だから\(\small{ \ pq \ }\)以下の自然数で\(\small{ \ p \ }\)の倍数は\(\small{ \ q \ }\)個、\(\small{ \ q \ }\)の倍数は\(\small{ \ p \ }\)個あるよね。
その内共通なものは\(\small{ \ pq \ }\)の\(\small{ \ 1 \ }\)個しかないから\(\small{ \ p, \ q \ }\)を因数に持つ\(\small{ \ pq \ }\)以下の自然数は\(\small{ \ p+q-1 \ }\)個ある。
だから\(\small{ \ pq \ }\)と互いに素になる数は
\(\small{ \ pq-(p+q-1)=(p-1)(q-1) \ }\)個
ってことになるよね。

この①②③を利用することで自然数\(\small{ \ n=2^a3^b5^c \ }\)と互いに素である\(\small{ \ n \ }\)以下の自然数は\(\small{ \ n\left(1-\displaystyle\frac{1}{2}\right)\left(1-\displaystyle\frac{1}{3}\right)\left(1-\displaystyle\frac{1}{5}\right) \ }\)って言えるんだ。

例題を確認
問題解答

\(\small{ \ 504 \ }\)以下の自然数で\(\small{ \ 504 \ }\)と互いに素な自然数について答えよ。
(1)このような自然数はいくつあるか。
(2)このような自然数の和はいくつになるか。

(1)\(\small{ \ 504=2^3\times3^2\times7 \ }\)より
\(\small{ \ 504\left(1-\displaystyle\frac{1}{2 }\right)\left(1-\displaystyle\frac{1}{3 }\right)\left(1-\displaystyle\frac{1}{7 }\right)\\
=144 \ }\)

(2)自然数\(\small{ \ k \ }\)が\(\small{ \ 504 \ }\)と互いに素なら\(\small{ \ 504-k \ }\)も互いに素である
この\(\small{ \ 2 \ }\)つの数の和は\(\small{ \ 504 \ }\)になる
\(\small{ \ 504 \ }\)と互いに素になる自然数は全部で\(\small{ \ 144 \ }\)個あるから
\(\small{ \ 504\times\displaystyle\frac{144}{2 }=36288 \ }\)

point
\(\small{ \ 108 \ }\)と互いに素な自然数を小さい順に並べると\(\small{ \ 1, \ 5, \ 11, \ 13,\cdots, \ 499, \ 503 \ }\)になって、前からと後ろから同じだけ数えて同じ順番の数をそれぞれを足すと\(\small{ \ 504 \ }\)になるよね。

ちなみにこの問題を集合で考えてとくと

\(\small{ \ n(\mathrm{A}\cup\mathrm{B}\cup\mathrm{C})\\=n(\mathrm{A})+n(\mathrm{B})+n(\mathrm{C})\\
\ \ -n(\mathrm{A}\cap\mathrm{B})-n(\mathrm{A}\cap\mathrm{C})-n(\mathrm{B}\cap\mathrm{C})\\
\ \ \ \ +n(\mathrm{A}\cap\mathrm{B}\cap\mathrm{C}) }\)

を利用することになるよね。
つまり\(\small{ \ n(\mathrm{U})-n(\mathrm{A}\cup\mathrm{B}\cup\mathrm{C}) \ }\)ってことだからね。

互いに素な自然数とオイラー関数-02

Point 互いに素な自然数とオイラー関数

①互いに素は共通の約数を持たないこと
②オイラー関数の式の原理を理解する

それじゃあ次は入試レベルの問題にチャレンジしてみよう。
入試レベルにチャレンジ
問題解答

自然数\(\small{ \ n \ }\)に対して、\(\small{ \ n \ }\)以下の自然数で\(\small{ \ n \ }\)との最大公約数が\(\small{ \ 1 \ }\)であるような自然数の個数を\(\small{ \ f(n) \ }\)とする。例えば、\(\small{ \ n=12 \ }\)に対しては、このような自然数は、\(\small{ \ 1, \ 5, \ 7, \ 11 \ }\)の\(\small{ \ 4 \ }\)個なので、\(\small{ \ f(12)=4 \ }\)である。また、\(\small{ \ f(1)=1 \ }\)、素数\(\small{ \ p \ }\)に対しては\(\small{ \ f(p)=p-1 \ }\)である。
(1)\(\small{ \ f(77) \ }\)の値を求めよ。
(2)\(\small{ \ f(pq)=24 \ }\)となる\(\small{ \ 2 \ }\)つの素数\(\small{ \ p, \ q \ }\)(ただし、\(\small{ \ p\lt q \ }\)とする)の組を求めよ。
(3)\(\small{ \ k, \ n \ }\)を自然数とするとき、\(\small{ \ f(2^k3^n) \ }\)の値を\(\small{ \ k \ }\)と\(\small{ \ n \ }\)の式で表せ。

(1)\(\small{ \ 77=7\times11 \ }\)より
\(\small{\begin{eqnarray} \ f(77)&=&77-\left(\displaystyle\frac{77}{7}+\displaystyle\frac{77}{11}-\displaystyle\frac{77}{7\times11 }\right)\\
&=&60 \ \end{eqnarray}}\)

(2)\(\small{ \ p, \ q \ }\)は素数だから
\(\small{\begin{eqnarray} \ f(pq)&=&pq-\left(\displaystyle\frac{pq}{p}+\displaystyle\frac{pq}{q}-\displaystyle\frac{pq}{p\times q }\right)\\
&=&pq-p-q+1\\
&=&(p-1)(q-1) \ \end{eqnarray}}\)
\(\small{ \ f(pq)=24 \ }\)より
\(\small{ \ (p-1)(q-1)=24 \ }\)
\(\small{ \ p, \ q \ }\)は素数かつ\(\small{ \ p\lt q \ }\)より
\(\small{\begin{array}{c|cccc} \ p-1&1&2&3&4\\
\hline
q-1&24&12&8&6 \ \end{array}}\)
\(\small{\begin{array}{c|cccc} \ p&2&3&4&5\\
\hline
q&25&13&9&7 \ \end{array}}\)
\(\small{ \ p, \ q \ }\)は素数より
\(\small{ \ (p, \ q)=(3, \ 13), \ (5, \ 7) \ }\)

(3)

\(\small{\begin{eqnarray} \ f(2^k3^n)&=&2^k3^n-\left(\displaystyle\frac{2^k3^n}{3}+\displaystyle\frac{2^k3^n}{2}-\displaystyle\frac{2^k3^n}{2\times3 }\right)\\
&=&2^k3^n-2^k3^{n-1}-2^{k-1}3^n+2^{k-1}3^{n-1}\\
&=&2^{k-1}3^{n-1}\left(6-2-3+1\right)\\
&=&2^k3^{n-1} \ \end{eqnarray}}\)

point
この問題はオイラー関数の証明のような問題で、オイラー関数を知っていると一瞬で解ける問題だよね。

ここで気になるのがオイラー関数を入試に使っていいのかってこと。この辺についてはまた別な記事で紹介しようと思う。

学校で教わらないけど入試に使いたい式って結構あるもんね。
ただ使うか使わないかに関わらず便利な式であることは間違いないから、使わないにしても検算用に覚えておくことは重要だよ。

この記事が気に入ったら
いいね ! しよう

Twitter で

  整数の性質

  , ,