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

2019年11月20日2022年2月21日

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

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

【オイラー関数 $φ(n)$ とは】
自然数 $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$ のとき、

\begin{align}φ(n)&=φ(p^kq^lr^m)\\&=φ(p^k)φ(q^l)φ(r^m)\\&=(p^k-p^{k-1})(q^l-q^{l-1})(r^m-r^{m-1})\\&=p^kq^lr^m(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})\\&=n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})\end{align}

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

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

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

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

問題.　次のオイラー関数 $φ(n)$ の値を求めなさい。
(1)　$φ(15)$　　(2)　$φ(105)$
(3)　$φ(180)$　　(4)　$φ(625)$

【解答】

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

\begin{align}φ(15)&=15(1-\frac{1}{3})(1-\frac{1}{5})\\&=15・\frac{2}{3}・\frac{4}{5}\\&=8\end{align}

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

\begin{align}φ(105)&=105(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{7})\\&=105・\frac{2}{3}・\frac{4}{5}・\frac{6}{7}\\&=48\end{align}

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

\begin{align}φ(180)&=180(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})\\&=180・\frac{1}{2}・\frac{2}{3}・\frac{4}{5}\\&=48\end{align}

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

\begin{align}φ(625)&=625(1-\frac{1}{5})\\&=625・\frac{4}{5}\\&=500\end{align}

(解答終了)

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

[ふきだし 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$ つを解説します。

格子点に関する問題

問題.　座標平面上において $y=0$，$x=8$，$y=x$ に囲まれた領域を $D$ とする。このとき、$D$ の内部と周上の格子点と原点を結ぶ線分で、両端以外に格子点を持たないものの本数を求めなさい。
※格子点（こうしてん）… x 座標と y 座標がともに整数であるような点

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

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

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

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

↓↓↓

【解答】

題意を満たす場合。

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

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

よって、

\begin{align} &\quad φ(1)+φ(2)+φ(3)+φ(4)+φ(5)+φ(6)+φ(7)+φ(8)\\&=1+1+2+2+4+2+6+4\\&=22\end{align}

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

ただし、ここには $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!!

以上で終わりです。

よかったらシェアしてね！

URLをコピーしました！

URLをコピーしました！

コメントを残す

コメント一覧（2件）

通りすがりの数学苦手者 より:

2020年4月30日 5:30 PM

「互いに素でない　＝　p の倍数である」ではありませんか？

返信
- utida-syouma より:
  
  2020年4月30日 7:27 PM
  
  通りすがりの数学苦手者さん、コメントありがとうございます！
  本当ですね！お恥ずかしい…
  訂正させていただきます！(^_^;)
  
  返信