スポンサーリンク

オイラー関数(ファイ関数)の使い方|整数・互いに素な自然数の個数

数学(大学入試問題)

オイラー関数について

 

「レオンハルト・オイラー」という名前は聞いたことありますか?

数学者としての膨大な業績と、後世の数学界に大きな影響を与え、19世紀のカール・フリードリヒ・ガウスと並ぶ数学界の二大巨人の一人です。

数々の業績の中の1つに、オイラー関数というものがあります。

この記事では、簡単な例題を交えながら、オイラー関数が使えるようになるように解説していきます。

オイラー関数 (\(φ(n)\))

自然数 \(n\) に対して、\(1\) から \(n\) までで \(n\) と互いに素な自然数の個数を \(φ(n)\) と表す.

\(n=a^p\times b^q\times c^r\times \cdots\) と素因数分解できるとき、

\(φ(n)=n\times\left(1-\displaystyle\frac{1}{a}\right)\times\left(1-\displaystyle\frac{1}{b}\right) \times\left(1-\displaystyle\frac{1}{c}\right)\times\cdots\)

いきなりこのようなことを言われても、???だと思います。

具体例で考えてみましょう!

具体例を交えて

例① \(n=5\) のとき

\(1\) から \(5\) までで \(5\) と互いに素な自然数は、\(1 , 2 , 3 , 4\) の \(4\) 個

よって、\(φ(5)=4\) と言うことです.

 

これを公式を使って求めると、

\(n=5\) は素数であるから、これ以上分解は出来ない.

つまり、公式の \(a=5\) として、

\(φ(5)=5\times\left(1-\displaystyle\frac{1}{5}\right)=4\)

と求めることが出来る.

※ \(n\) が素数のとき、\(φ(n)=n-1\)

例② \(n=9\) のとき

\(1\) から \(9\) までで \(9\) と互いに素な自然数は、\(1 , 2 , 4 , 5 , 7 , 8\) の \(6\) 個

よって、\(φ(9)=6\) と言うことです.

 

これを公式を使って求めると、

\(n=9=3^2\) より

\(φ(9)=9\times\left(1-\displaystyle\frac{1}{3}\right)=6\)

と求めることが出来る.

例③ \(n=12\) のとき

\(1\) から \(12\) までで \(12\) と互いに素な自然数は、\(1 , 5 , 7 , 11\) の \(4\) 個

よって、\(φ(12)=4\) と言うことです.

 

これを公式を使って求めると、

\(n=12=2^2\times3\) より

\(φ(12)=12\times\left(1-\displaystyle\frac{1}{2}\right) \times\left(1-\displaystyle\frac{1}{3}\right)=4\)

と求めることが出来る.

2021一橋大学 にチャレンジ

2021 一橋大学[整数]1000以下の素数は250個以下であることを示せ
素数に関する一行問題。集合を用いた解法と、オイラー関数を利用した解法を紹介。 【参考】1000以下の素数は168個

 

最後に

例①~③で行ったような \(n\) の値が小さいときは数え上げでも問題ないが、値が大きくなると公式を知らないと厳しい.

直接的にオイラー関数という言葉は出ずとも、入試問題では知っていると楽に処理できる問題は存在します.

是非知識として、知っておいてください.

コメント

タイトルとURLをコピーしました