こんにちは、ウチダです。
さて、皆さんは「オイラー関数」とは何かご存じでしょうか。
自然数 $n$ に対して、$1$ から $n$ までで $n$ と互いに素な自然数の個数を $φ(n)$ と表す。
たとえば素数 $p$ に対しては $φ(p)=p-1$ である。
※ φ(n) を「オイラーのファイ関数」「オイラーのトーシェント関数」または単に「オイラー関数」と呼びます。
[ふきだし set=”悩む男性”]オイラー関数の値はどうやって求めればいいんだろう？公式とかはあるのかな？[/ふきだし]
[ふきだし set=”悩む女性”]オイラー関数を求める問題をたくさん解きたい。他の応用例もあったら知りたいわ。[/ふきだし]
よって本記事では、オイラー関数の公式の証明（概要）から、オイラー関数の値を求める計算問題、さらにオイラー関数の応用例まで
- 東北大学理学部数学科卒業
- 教員採用試験に１発合格 → 高校教諭経験アリ
の僕がわかりやすく解説します。
オイラー関数の公式とは？【「素数のべき乗」「乗法性」に注目だ！】
オイラー関数には、とっても便利な公式があります。
$n=p^kq^lr^m$ と素因数分解できるとき、$$φ(n)=n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})$$
なんと、素因数分解ができてしまえば、オイラー関数の値はすぐに求まってしまうのです！
[ふきだし set=”ウチダ”]これ、不思議ですよね～。実は、ある重要な事実 $2$ つから、この公式は成り立っています。[/ふきだし]
その重要な事実 $2$ つとは…
- 【素数のべき乗の性質】 … $p$ を素数、$k$ をある自然数としたとき、$$φ(p^k)=p^k-p^{k-1}$$が成り立つ。
- 【オイラー関数の乗法性】 … $n$ と $m$ を互いに素な自然数としたとき、$$φ(nm)=φ(n)φ(m)$$が成り立つ。
この事実 $2$ つを使うことで、$n=p^kq^lr^m$ のとき、
と公式を示すことができます。
※ $1$ 行目から $2$ 行目で「乗法性」、$2$ 行目から $3$ 行目で「素数のべき乗の性質」を用いています。
オイラー関数の計算問題４選
それでは一度、公式を使う練習をしてみましょう。
(1) $φ(15)$ (2) $φ(105)$
(3) $φ(180)$ (4) $φ(625)$
【解答】
(1) $15=3・5$ より、
(2) $105=3・5・7$ より、
(3) $180=2^2・3^2・5$ より、
(4) $625=5^4$ より、
(解答終了)
一般化されている公式を使っているため、計算が少し回りくどいですが、しっかりと求めることができます。
[ふきだし set=”ウチダ”]「もっと具体的な話から勉強したい」という方は、「互いに素な自然数とは？【応用例７選もわかりやすく解説します】」の記事から読み進めることをオススメします。[/ふきだし]
では、オイラー関数の公式がいかに有用であるかわかったところで、背景知識 $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)$ を示したいとき、
| $1$ | $2$ | $3$ | $4$ |
| $5$ | $6$ | $7$ | $8$ |
| $9$ | $10$ | $11$ | $12$ |
| $13$ | $14$ | $15$ | $16$ |
| $17$ | $18$ | $19$ | $20$ |
と並べてみる。
ここで、薄い青色の部分を見てみると、
- $3$ を $5$ で割ったときの余り → $3$
- $7$ を $5$ で割ったときの余り → $2$
- $11$ を $5$ で割ったときの余り → $1$
- $15$ を $5$ で割ったときの余り → $0$
- $19$ を $5$ で割ったときの余り → $4$
と、$5$ で割った余りがすべて異なることに気づく。
よって、薄い青色の部分で $20$ と互いに素である自然数の個数は $φ(5)=4$ 個と表すことができる。
今の議論は、薄い赤色の部分に対しても同様に成り立つ。
| $1$ | $2$ | $3$ | $4$ |
| $5$ | $6$ | $7$ | $8$ |
| $9$ | $10$ | $11$ | $12$ |
| $13$ | $14$ | $15$ | $16$ |
| $17$ | $18$ | $19$ | $20$ |
よって、$φ(20)=2×φ(5)$ が成り立ち、$2=φ(4)$ であるため、
$$φ(20)=φ(4)φ(5)$$
が成り立つ。
(証明の概要終了)
縦に見る作業と横に見る作業が、こんなにも美しく連携しているのですね！
オイラー関数の応用例２選
では次に、オイラー関数の応用例を $2$ つ考えていきましょう。
具体的には、
- 格子点に関する問題
- フェルマーの小定理
以上 $2$ つを解説します。
格子点に関する問題
※格子点（こうしてん）… x 座標と y 座標がともに整数であるような点
さて、中々複雑な問題設定ですので、一度図を書いて整理してみましょう。
たとえば $A( \ 5 \ , \ 3 \ )$ であれば、線分 $OA$ の間に格子点は存在しないため、題意を満たします。
さあ、今整理したことを踏まえて、逆に「題意を満たさない場合」なんかも考えてみてください。
解答にグッと近づきます！
↓↓↓
【解答】
題意を満たす場合。
それは $A( \ 5 \ , \ 3 \ )$ のように、$x$ 座標と $y$ 座標が互いに素であるときに他ならない。
つまり、オイラー関数 $φ(n)$ に $n=1$ ～ $8$ を入れたものをすべて足した値を求めればよい。
よって、
※この数式は横にスクロールできます。（スマホでご覧の方対象。）
ただし、ここには $A( \ 1 \ , \ 0 \ )$ の場合が含まれていない。
したがって、求める線分の本数は $22+1=23$ 本である。
(解答終了)
中々ユニークな問題でしたね。
最後の $A( \ 1 \ , \ 0 \ )$ の場合も題意を満たすことに注意しましょう。
フェルマーの小定理
フェルマーの小定理とは、整数分野において最も有名な定理の一つです。
- $p$ を素数とし、$a$ を $p$ と互いに素な自然数とする。
このとき、$$a^{p-1}≡1 \pmod{p}$$ - もしくは、$$a^p≡a \pmod{p}$$
※①を「第 $1$ 形式」、②を「第 $2$ 形式」と呼ぶことがある。
実は、この定理は「オイラーの定理」と呼ばれる、オイラー関数を使った定理の特殊な場合に過ぎないのです。
$a$ と $n$ を互いに素な自然数とする。このとき、$$a^{φ(n)}≡1 \pmod{n}$$が成り立つ。
実際、$n=p$（ $p$ は素数）とすると、$φ(n)=φ(p)=p-1$ なので、フェルマーの小定理第 $1$ 形式になりますね。
[ふきだし set=”考える女性”]中々凄そうな定理ですね…証明が知りたいです！[/ふきだし]
[ふきだし set=”ウチダ”]オイラーの定理はフェルマーの小定理の一般化ですので、フェルマーの小定理の証明ができれば十分でしょう。興味のある方は「フェルマーの小定理の２通りの証明とは？【京大入試を含む問題３選も解説】」の記事をぜひ読んでみてください＾＾[/ふきだし]
まあ、証明は思いついてるんですが、ここで書くには余白が足りないため、省略することにします。
（フェルマーさんの言葉を引用しましたスイマセン。）
オイラー関数についてのまとめ
本記事の要点をまとめます。
- $\displaystyle φ(n)=n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})$ の公式さえ知っていれば、互いに素な自然数の個数はすぐにわかる！
- オイラーの定理の $n$ が素数バージョン、それが「フェルマーの小定理」である。
「オイラー関数とは何か」を友達に説明できれば、めっちゃ褒められると思いますよ！
そのときは、ぜひ本記事を参考にしてみてください。
「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!
以上で終わりです。
コメントを残す
コメント一覧 （2件）
「互いに素でない ＝ p の倍数である」ではありませんか？
通りすがりの数学苦手者さん、コメントありがとうございます！
本当ですね！お恥ずかしい…
訂正させていただきます！(^_^;)