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

2019 12/14
オイラー関数とは?【公式の証明や応用例2選をわかりやすく解説します】

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

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

【オイラー関数 $φ(n)$ とは】
自然数 $n$ に対して、$1$ から $n$ までで $n$ と互いに素な自然数の個数を $φ(n)$ と表す。
たとえば素数 $p$ に対しては $φ(p)=p-1$ である。
※ φ(n) を「オイラーのファイ関数」「オイラーのトーシェント関数」または単に「オイラー関数」と呼びます。
悩む男性 悩む男性
オイラー関数の値はどうやって求めればいいんだろう?公式とかはあるのかな?
悩む女性 悩む女性
オイラー関数を求める問題をたくさん解きたい。他の応用例もあったら知りたいわ。

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

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

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

スポンサーリンク
目次

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

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

【オイラー関数の公式】
$n=p^kq^lr^m$ と素因数分解できるとき、$$φ(n)=n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})$$

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

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

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

  1. 【素数のべき乗の性質】 … $p$ を素数、$k$ をある自然数としたとき、$$φ(p^k)=p^k-p^{k-1}$$が成り立つ。
  2. 【オイラー関数の乗法性】 … $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$ 行目で「素数のべき乗の性質」を用いています。

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

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

問題. 次のオイラー関数 $φ(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}

(解答終了)

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

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

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

重要な事実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$ つ考えていきましょう。

具体的には、

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

以上 $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 \ )$ の場合も題意を満たすことに注意しましょう。

フェルマーの小定理

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

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

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

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

【オイラーの定理】
$a$ と $n$ を互いに素な自然数とする。このとき、$$a^{φ(n)}≡1 \pmod{n}$$が成り立つ。

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

考える女性 考える女性
中々凄そうな定理ですね…証明が知りたいです!
ウチダ ウチダ
オイラーの定理はフェルマーの小定理の一般化ですので、フェルマーの小定理の証明ができれば十分でしょう。興味のある方は「フェルマーの小定理の2通りの証明とは?【京大入試を含む問題3選も解説】」の記事をぜひ読んでみてください^^

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

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

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

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

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

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

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

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

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

以上で終わりです。

目次