オイラー関数とは？【公式の証明や応用例２選をわかりやすく解説します】

こんにちは、ウチダです。

さて、皆さんは「オイラー関数」とは何かご存じでしょうか。

数学太郎

オイラー関数の値はどうやって求めればいいんだろう？公式とかはあるのかな？

数学花子

オイラー関数を求める問題をたくさん解きたい。他の応用例もあったら知りたいわ。

よって本記事では、オイラー関数の公式の証明（概要）から、オイラー関数の値を求める計算問題、さらにオイラー関数の応用例まで

• 東北大学理学部数学科卒業
• 教員採用試験に１発合格　→　高校教諭経験アリ

の僕がわかりやすく解説します。

オイラー関数の公式とは？【「素数のべき乗」「乗法性」に注目だ！】

オイラー関数には、とっても便利な公式があります。

なんと、素因数分解ができてしまえば、オイラー関数の値はすぐに求まってしまうのです！

ウチダ

これ、不思議ですよね～。実は、ある重要な事実 $2$ つから、この公式は成り立っています。

その重要な事実 $2$ つとは…

1. 【素数のべき乗の性質】　…　$p$ を素数、$k$ をある自然数としたとき、$$φ(p^k)=p^k-p^{k-1}$$が成り立つ。
2. 【オイラー関数の乗法性】　…　$n$ と $m$ を互いに素な自然数としたとき、$$φ(nm)=φ(n)φ(m)$$が成り立つ。

この事実 $2$ つを使うことで、$n=p^kq^lr^m$ のとき、

と公式を示すことができます。

※ $1$ 行目から $2$ 行目で「乗法性」、$2$ 行目から $3$ 行目で「素数のべき乗の性質」を用いています。

オイラー関数の計算問題４選

それでは一度、公式を使う練習をしてみましょう。

【解答】

(1)　$15=3・5$ より、

(2)　$105=3・5・7$ より、

(3)　$180=2^2・3^2・5$ より、

(4)　$625=5^4$ より、

(解答終了)

一般化されている公式を使っているため、計算が少し回りくどいですが、しっかりと求めることができます。

ウチダ

「もっと具体的な話から勉強したい」という方は、「互いに素な自然数とは？【応用例７選もわかりやすく解説します】」の記事から読み進めることをオススメします。

では、オイラー関数の公式がいかに有用であるかわかったところで、背景知識 $2$ つの証明を考えていきましょう！

重要な事実２つの証明【大学数学レベル】

まず、素数のべき乗のトーシェント関数

$$φ(p^k)=p^k-p^{k-1}$$

これについては簡単です。

だって、

• 互いに素でない　＝　$p$ の倍数である
• $1$ ～ $p^k$ までで $p$ の倍数でないものの個数は、$p^k÷p=p^{k-1}$

よって、$φ(p^k)=p^k-p^{k-1}$ とすぐに求まります。

ただ問題なのが、オイラー関数の乗法性

$$φ(nm)=φ(n)φ(m)$$

こっちなんですね～。

これについてはしっかり証明しようとすると、大学レベルの数学を要しますので、ここでは証明の概要だけ追ってみたいと思います。

【乗法性の証明の概要】

たとえば $φ(20)=φ(4)φ(5)$ を示したいとき、

と並べてみる。

ここで、薄い青色の部分を見てみると、

• $3$ を $5$ で割ったときの余り　  →　$3$
• $7$ を $5$ で割ったときの余り　  →　$2$
• $11$ を $5$ で割ったときの余り　 →　$1$
• $15$ を $5$ で割ったときの余り　 →　$0$
• $19$ を $5$ で割ったときの余り　 →　$4$

と、$5$ で割った余りがすべて異なることに気づく。

よって、薄い青色の部分で $20$ と互いに素である自然数の個数は $φ(5)=4$ 個と表すことができる。

 今の議論は、薄い赤色の部分に対しても同様に成り立つ。

よって、$φ(20)=2×φ(5)$ が成り立ち、$2=φ(4)$ であるため、

$$φ(20)=φ(4)φ(5)$$

が成り立つ。

(証明の概要終了)

縦に見る作業と横に見る作業が、こんなにも美しく連携しているのですね！

オイラー関数の応用例２選

では次に、オイラー関数の応用例を $2$ つ考えていきましょう。

具体的には、

• 格子点に関する問題
• フェルマーの小定理

以上 $2$ つを解説します。

格子点に関する問題

さて、中々複雑な問題設定ですので、一度図を書いて整理してみましょう。

たとえば $A( \ 5 \ , \ 3 \ )$ であれば、線分 $OA$ の間に格子点は存在しないため、題意を満たします。

さあ、今整理したことを踏まえて、逆に「題意を満たさない場合」なんかも考えてみてください。

解答にグッと近づきます！

↓↓↓

【解答】

題意を満たす場合。

それは $A( \ 5 \ , \ 3 \ )$ のように、$x$ 座標と $y$ 座標が互いに素であるときに他ならない。

つまり、オイラー関数 $φ(n)$ に $n=1$ ～ $8$ を入れたものをすべて足した値を求めればよい。

よって、

※この数式は横にスクロールできます。（スマホでご覧の方対象。）

ただし、ここには $A( \ 1 \ , \ 0 \ )$ の場合が含まれていない。

したがって、求める線分の本数は $22+1=23$ 本である。

(解答終了)

中々ユニークな問題でしたね。

最後の $A( \ 1 \ , \ 0 \ )$ の場合も題意を満たすことに注意しましょう。

フェルマーの小定理

フェルマーの小定理とは、整数分野において最も有名な定理の一つです。

1. $p$ を素数とし、$a$ を $p$ と互いに素な自然数とする。
   このとき、$$a^{p-1}≡1 \pmod{p}$$
2. もしくは、$$a^p≡a \pmod{p}$$

※①を「第 $1$ 形式」、②を「第 $2$ 形式」と呼ぶことがある。

実は、この定理は「オイラーの定理」と呼ばれる、オイラー関数を使った定理の特殊な場合に過ぎないのです。

実際、$n=p$（ $p$ は素数）とすると、$φ(n)=φ(p)=p-1$ なので、フェルマーの小定理第 $1$ 形式になりますね。

数学花子

中々凄そうな定理ですね…証明が知りたいです！

ウチダ

オイラーの定理はフェルマーの小定理の一般化ですので、フェルマーの小定理の証明ができれば十分でしょう。興味のある方は「フェルマーの小定理の２通りの証明とは？【京大入試を含む問題３選も解説】」の記事をぜひ読んでみてください＾＾

まあ、証明は思いついてるんですが、ここで書くには余白が足りないため、省略することにします。

（フェルマーさんの言葉を引用しましたスイマセン。）

オイラー関数についてのまとめ

本記事の要点をまとめます。

• $\displaystyle φ(n)=n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})$ の公式さえ知っていれば、互いに素な自然数の個数はすぐにわかる！
• オイラーの定理の $n$ が素数バージョン、それが「フェルマーの小定理」である。

「オイラー関数とは何か」を友達に説明できれば、めっちゃ褒められると思いますよ！

そのときは、ぜひ本記事を参考にしてみてください。

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい

整数の性質とは？【高校数学Ａの解説記事総まとめ２５選】 「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全２５個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

以上で終わりです。