オイラーのφ関数とは？性質は？導入背景は？

本記事の内容

本記事はオイラー関数とはどういう関数なのか、及びオイラー関数が整数論で注目されるのはなぜかということを説明する記事です。

本記事を読むにあたり、素数および素因数分解を知っている必要があるため、以下の記事も合わせてご覧ください。

1が素数でないのはなぜ？素因数分解定理の証明

...

for-spring.com

2023.03.10

オイラーの$\varphi$関数とは？

結論としては

です。

オイラー関数とは何か？

$n$以下の自然数に対し、$n$と互いに素な整数の個数を対応させる関数$\varphi:\mathbb{N}\longrightarrow \mathbb{N}$をオイラーの$\varphi$関数と呼ぶのです。

書き方は色々ありますが、例えば以下のように書くことができます。

$$\begin{eqnarray} \varphi(n)&=&\left|\left\{ x\in\mathbb{N}\middle|x\leq n,\ \gcd(x,n)=1\right\}\right|\tag{1}\\ &=&\sum_{\substack{x\in\mathbb{N}\\ x\leq n\\ \gcd(x,n)=1}}1\tag{2} \end{eqnarray}$$

特に、(2)の書き方には馴染みがあまり無い方もいらっしゃると思うので、(1)と(2)が何故等しいのかということについて少々言及しておきます。
とはいえ、至ってシンプルです。

(2)式について（読み飛ばしてOK）

ここでは、
$$\left|\left\{ x\in\mathbb{N}\middle|x\leq n,\ \gcd(x,n)=1\right\}\right|=\sum_{\substack{x\in\mathbb{N}\\ x\leq n\\ \gcd(x,n)=1}}1$$
となる理由についてお話します。

(1)(上式の左辺)は読んで字の如しといったところで、「$n$以下の自然数のうち、$n$と互いに素な自然数$x$の個数」を表しています。
一方で(2)(上式の右辺)も同じことを表しています。

和の記号$\displaystyle\sum_{P}Q$の本質的な意味は以下です。

というものです。

「え？$\displaystyle\sum_{i=1}^nf(n)$みたいな書き方もあるじゃんね」となるかもしれません。
たしかにそうです。
しかしこれは本質的に
$$\sum_{i=1}^nf(n)=\sum_{\substack{i\in\mathbb{N}\\ 1\leq i\leq n}}f(n)\tag{3}$$
という意味です。
要するに、(3)式の左辺を省略して(3)式の右辺と書く、という意味なのです。

さて、本題に戻ります。
今説明しているのは、
$$\left|\left\{ x\in\mathbb{N}\middle|x\leq n,\ \gcd(x,n)=1\right\}\right|=\sum_{\substack{x\in\mathbb{N}\\ x\leq n\\ \gcd(x,n)=1}}1$$
となる理由です。

先程述べた和の記号$\displaystyle\sum_{P}Q$の本質的な意味に立ち戻ってみれば、$\displaystyle\sum_{\substack{x\in\mathbb{N}\\ x\leq n\\ \gcd(x,n)=1}}1$は

という意味です。
$P$という条件下で$1$を足し合わせなさい、と言っているわけですので、ここでは$x\in\mathbb{N}$、$x\leq n$、$\gcd(x,n)=1$を満たすような$x\in\mathbb{N}$に対して$1$を足し合わせなさいということになります。

これはまさに、「$x\leq n$、$\gcd(x,n)=1$を満たす$x\in\mathbb{N}$の個数」ということになるわけです。

具体的に計算してみる（真正直に計算してみる）

いくつか具体的な数値を導出してみましょう。

• $\varphi(1)=1$
  $\varphi(1)$は「$1$以下の自然数で、$1$と互いに素な自然数の個数」です。
  $1$以下の自然数は$1$だけであり、かつ$\gcd(1,1)=1$です。
  したがって、$1$以下の自然数で、$1$と互いに素な自然数は$1$の$1$個だけです。
  故に$\varphi(1)=1$です。
• $\varphi(2)=1$
  $\varphi(2)$は「$2$以下の自然数で、$2$と互いに素な自然数の個数」です。
  $2$以下の自然数は$1$および$2$です。
  そして、$\gcd(2,1)=1$かつ$\gcd(2,2)=2\neq1$です。
  したがって、$2$以下の自然数で、$2$と互いに素な自然数は$1$の$1$個だけです。
  故に$\varphi(2)=1$です。
• $\varphi(3)=2$
  $\varphi(3)$は「$3$以下の自然数で、$3$と互いに素な自然数の個数」です。
  $3$以下の自然数は$1$、$2$および$3$です。
  そして、$\gcd(3,1)=1$、$\gcd(3,2)=1$、$\gcd(3,3)=3\neq1$です。
  したがって、$3$以下の自然数で、$3$と互いに素な自然数は$1$と$2$の$2$個です。
  故に$\varphi(3)=2$です。
• $\varphi(4)=2$
  同じです。
  $\varphi(4)$は「$4$以下の自然数で、$4$と互いに素な自然数の個数」です。
  $4$以下の自然数は$1,2,3,4$です。
  そして、$\gcd(4,1)=1,\ \gcd(4,2)=2\neq1,\ \gcd(4,3)=1,\ \gcd(4,4)=4\neq1$です。
  したがって、$4$以下の自然数で、$4$と互いに素な自然数は$1$と$3$の$2$個です。
  故に$\varphi(4)=2$です。
• $\varphi(5)=4$
  同じです。
  $\varphi(5)$は「$5$以下の自然数で、$5$と互いに素な自然数の個数」です。
  $5$以下の自然数は$1,2,3,4,5$です。
  そして、$\gcd(5,1)=1,\ \gcd(5,2)=2,\ \gcd(5,3)=1,\ \gcd(5,4)=1,\ \gcd(5,5)=5\neq1$です。
  したがって、$5$以下の自然数で、$5$と互いに素な自然数は$1,2,3,4$の$4$個です。
  故に$\varphi(5)=4$です。
• $\varphi(6)=2$
  同じです。
  $\varphi(6)$は「$6$以下の自然数で、$6$と互いに素な自然数の個数」です。
  $6$以下の自然数は$1,2,3,4,5,6$です。
  そして、$\gcd(6,1)=1,\ \gcd(6,2)=2\neq1,\ \gcd(6,3)=3\neq1,\ \gcd(6,4)=2\neq1$,$\gcd(6,5)=1,\ \gcd(6,6)=6\neq1$です。
  したがって、$6$以下の自然数で、$6$と互いに素な自然数は$1,5$の$2$個です。
  故に$\varphi(6)=2$です。

このくらいなら、特に問題なくスッと計算できると思います。

では、$\varphi(100)$はどうでしょう。
$100$以下の自然数で、$100$と互いに素な自然数は
$$\begin{eqnarray} &&1,\ 3,\ 7,\ 9,\ 11,\ 13,\ 17,\ 19,\ 21,\ 23,\ 27,\ 29,\ 31,\ 33,\ 37,\ 39,\ 41,\ 43,\ 47,\ 49,\\ &&51,\ 53,\ 57,\ 59,\ 61,\ 63,\ 67,\ 69,\ 71,\ 73,\ 77,\ 79,\ 81,\ 83,\ 87,\ 89,\ 91,\ 93,\ 97,\ 99 \end{eqnarray}$$
ですので、$\varphi(100)=40$です。

ここまで計算してみたわけですが、

と思いませんでしたか？
確かに$n=100$のときは、$100$以下で$100$と互いに素な自然数にはある程度の規則性があったため、そこまで面倒ではなかったかもしれませんが、より大きな数だったり、素因数の種類が多い自然数に対してはどうでしょう？
面倒ですよね。

これをさらっと解決するオイラーの$\varphi$関数の性質は、後ほど紹介します。

オイラーの$\varphi$関数の基本的な性質

では、オイラーの$\varphi$関数の諸性質について述べます。

$n$が素数のときの$\varphi(n)$はすぐ分かりそうじゃない？

そうです。
すぐ分かります。
実は、$p$が素数のとき、$\varphi(p)=p-1$です。
すなわち、$p$以下の自然数で、$p$と互いに素な自然数の個数は$p-1$なのです。

明示して証明しましょう。

定理1.の証明

一瞬で終わります。

$p\in\mathbb{N}$を素数とすると、$p$は$1$と$p$自身以外を約数として持ちません。
すなわち、
$$(\forall i\in\mathbb{N}:1< i< p)\quad i\not\mid p$$
ということになります。
これを言い換えれば
$$(\forall i\in\mathbb{N}:1\leq i< p)\quad \gcd(i,p)=1$$
です。
ただし、任意の$n\in\mathbb{N}$に対して、$\gcd(1,n)=1$に注意です。

すなわち、$i=1,2,\cdots,p-1$に対しては$\gcd(i,p)=1$なわけですから、$p$以下の自然数で$p$と互いに素であるような自然数は、$p$自身を除いて$p-1$個です。

したがって、素数$p$に対して$\varphi(p)=p-1$です。

定理1.の証明終わり

$n$が素数のベキ乗ときの$\varphi(n)$もすぐ分かりそうじゃない？

そうです。
すぐ分かります。
実は、$p$が素数、$e\in\mathbb{N}$のとき$\varphi(p^e)=p^e-p^{e-1}$です。
すなわち、$p^e$以下の自然数で、$p^e$と互いに素な自然数の個数は$p^e-p^{e-1}$なのです。

定理2.の証明

これも一瞬です。

$1$から$p^e$までの自然数のうち、$p^e$と互いに素でない自然数は$p$で割り切れる自然数です。
そしてそれらは
$$1\cdot p,\ 2\cdot p,\cdots,p^{e-1}\cdot p,\ $$
の$p^{e-1}$個です。
したがって、$1$から$p^e$までの$p^e$個の自然数のうち、$p^{e-1}$個の自然数が$p^e$と互いに素でない為
$$\varphi(p^e)=p^e-p^{e-1}$$
となるわけです。

定理2.の証明終わり

$\varphi(n)$を計算するのって面倒くさくない？

面倒です。
なぜなら、真正直にやると$n\in\mathbb{N}$に対して、$1,2,\cdots,n$の全てに対して$n$自身と互いに素かを検証する必要があるからです。
操作の回数は$n$回ですね。

実はイチイチ$n$個の数を$n$と互いに素かを検証する必要はありません。
なぜなら、次の事実が成り立っているからです。

定理3.は以下の事実から導けます。

※この定理0.の証明は次回行います。

今回は、定理0.が成り立ったと仮定して定理1.を証明します。

定理0.が成り立ったと仮定した上での定理3.の証明

定理0.が成り立ったと仮定します。

このとき、定理0.から$c_1,c_2,\cdots,c_m$が2つずつ互いに素、すなわち
$$(\forall i,j\in\mathbb{N}:1\leq i,j\leq m)\ i\neq j\Longrightarrow \gcd(c_i,c_j)=1$$
であるならば、
$$\begin{eqnarray} \varphi\left( \prod_{l=1}^mc_l\right)&=&\varphi\left( c_1c_2\cdots c_m\right)\\ &=&\varphi(c_1)\varphi(c_2)\cdots \varphi(c_m) \end{eqnarray}$$
です。

$n\in\mathbb{N}$を

と素因数分解したとしましょう(素因数分解については【代数学の基礎シリーズ】初等整数論編 その8を御覧ください)。
このとき、$p_1,p_2,\cdots,p_k$は全て素数ですので、どの2つの素数も互いに素です。
すなわち、
$$(\forall s,t\in\mathbb{N}:1\leq s,t\leq k)\ s\neq t\Longrightarrow \gcd(p_s,p_t)=1$$
です。
また、各$p_1,p_2,\cdots,p_k$は何乗したとて、どの2つにも共通な因数は出現しません。
故に任意の$r_1,r_2\in\mathbb{N}$に対して
$$\gcd(p_s^{r_1},p_t^{r_2})=1$$
です。

したがって、定理2.を使えば、
$$\begin{eqnarray} \varphi(n)&=&\varphi\left( p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right)\\ &=&\varphi\left( p_1^{a_1}\right)\varphi\left( p_2^{a_2}\right)\cdots\varphi\left( p_k^{a_k}\right)\\ &=&\left( p_1^{a_1}- p_1^{a_1-1}\right)\left( p_2^{a_2}- p_2^{a_2-1}\right)\cdots\left( p_k^{a_k}- p_k^{a_k-1}\right)\\ &=&\left\{ p^{a_1}\left( 1-\frac{1}{p_1}\right)\right\}\left\{ p^{a_2}\left( 1-\frac{1}{p_2}\right)\right\}\cdots\left\{ p^{a_k}\left( 1-\frac{1}{p_k}\right)\right\}\\ &=&p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\cdot\left( 1-\frac{1}{p_1}\right)\left( 1-\frac{1}{p_2}\right)\cdots\left( 1-\frac{1}{p_k}\right)\\ &=&n\left( 1-\frac{1}{p_1}\right)\left( 1-\frac{1}{p_2}\right)\cdots\left( 1-\frac{1}{p_k}\right) \end{eqnarray}$$
となります。

定理0.が成り立ったと仮定した上での定理3.の証明終わり

具体的に計算してみる（オイラーの$\varphi$関数の性質を使って）

では、今証明した性質を使って実際に計算してみましょう。

例1. $\varphi\left( 2^{10}\right)=?$

$\varphi\left( 2^{10}\right)$を真正直に計算しようとすると、$1024$と互いに素な自然数を見つけなければいけません。

面倒くさいですね。
しかし定理2.を使えば
$$\begin{eqnarray} \varphi\left( 2^{10}\right)&=&2^{10}-2^{10-1}\\ &=&2^{10}-2^{9}\\ &=&1024-\frac{1024}{2}\\ &=&1024-512\\ &=&512 \end{eqnarray}$$
と求まるわけです。

ちなみに、この問題についてはうまく発想すると直ちに分かります。
というもの、$2^{10}$は素因数を$2$しか持ちません。
故に、$2^{10}$と互いに素な$2^{10}$以下の自然数は、$2^{10}$以下の奇数です。
$2^{10}=1024$までの自然数のうち奇数は、半分の$512$個です。
故に、$\varphi\left( 2^{10}\right)=2^5=512$と求まります。

例2. $\varphi\left( 202356\right)=?$

筆者がこの記事を書いている日付を例にとって計算してみましょう。

$$202356=2^2\cdot3^2\cdot7\cdot11\cdot73$$
と素因数分解できるため、
$$\begin{eqnarray} \varphi\left( 202356\right)&=&202356\cdot\left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{3}\right)\left( 1-\frac{1}{7}\right)\left( 1-\frac{1}{11}\right)\left( 1-\frac{1}{73}\right)\\ &=&202356\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{6}{7}\cdot\frac{10}{11}\cdot \frac{72}{73}\\ &=&2^2\cdot3^2\cdot7\cdot11\cdot73\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{6}{7}\cdot\frac{10}{11}\cdot \frac{72}{73}\\ &=&2\cdot3\cdot2\cdot6\cdot10\cdot72\\ &=&72\cdot10\cdot72\\ &=&5184\cdot10\\ &=&51840 \end{eqnarray}$$
と求まります。

オイラーの$\varphi$関数の導入背景

なぜそもそもこのような関数が導入されたのでしょうか。
一番最初と言われているのは

という素朴な疑問だったようです。
この疑問は「素数が自然数の中でどのように分布しているのか？」という疑問に通じます。

余談(豆知識)

オイラーの$\varphi$関数は、その名の通り、レオンハルト・オイラーが1761年に発見、導入したものと言われています。
しかし、実はさらにその数年前に日本の久留島義太が言及していたという説もあるようです。
ちなみにこの久留島義太はラプラスよりも早くラプラス展開(余因子展開)を発見していたとも言われています。

ある数と$n\in\mathbb{N}$が互いに素である、または素でないということは、その数を$n$の倍数だけ増やしたり減らしたりしても変わりません。
一般に、
$$\gcd(r+nt,n)=\gcd(r,n)$$
ですから(ユークリッドの互除法)、$n$を法とする1つの類(合同類)に属する数は、全て$n$とは互いに素か、もしくは$n$と組み合わせたとき、一定の最大公約数を持ちます。

今、その最大公約数を$d$と書いたとしましょう。
$\gcd(r,n)=d$、$n=n^\prime d$、$r=r^\prime d$と書いたとすると、$r$によって代表される、法$n$に関する1つの類の数であるような$nt+r=d\left( n^\prime t+r^\prime\right)$は、法$n^\prime$に関して、$\gcd(r^\prime,n^\prime)=1$であるような$r^\prime$によって代表される1つの類の各数に$d$を乗じて得られるものにほかなりません。

つまり、数の類の中で方と互いに素であるような数のみを含む類が最も基本的だ、ということになります。

例えば、$4$を法とするときの数の4つの類(合同類)のうち、2つは奇数だけの類です。
それは$4h+1$型および$4h-1$型の奇数です。
偶数のみを含む他の2つの類の中で、$4h$の形のものは偶数の$2$倍であるような整数の集合で、また、$4h+2$型の整数は奇数の$2$倍であるような数の集合です。
偶数の$2$倍、または奇数の$2$倍というのは、つまり$2$を法としての区別です。

さて、数の類の中で方と互いに素であるような数のみを含む類が最も基本的だ、ということでしたが、これにより$n$を法とするときの数の類の中で$n$と互いに素である数のみを含むものを$n$を方としての既約類と呼ぶことにしましょう。

すると、$n$を法としての既約類の個数が、すなわち$\varphi(n)$なのです。

オイラーの$\varphi$関数が出現する定理

代表例はフェルマーの小定理でしょう。
この定理はかの有名なフェルマーの最終定理を大定理とよび、それに対して小定理と呼ばれています。

定理の内容は次回以降、本ブログで解説します。

皆様のコメントを下さい！

2023年のGWも終わりかけています。
今年のGWはどうでしたか？

どこかお出かけしましたか？それとも家でまったりしていましたか？

もしかすると、GW中はずっと数学漬けの方もいらっしゃったりして…

ぜひ今年のGWがどうだったかの感想をコメントで教えて下さい！(○○に行ったよ！とか)

結

今回は、オイラー関数を導入しその性質のうち重要なものを解説しました。
オイラーの$\varphi$関数は、自然数を定義域と値域にもち「“とある自然数”と互いに素な、“とある自然数”以下の自然数の個数」で定められた関数です。

導入背景は素朴な疑問「$1$から$n$までの自然数の中に、$n$と互いに素なものがいくつあるのか」のようです。
これは素数の分布にもつながる問題意識です。

次回は、オイラーの$\varphi$関数の性質の1つの証明を完成させます。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！