美的数学のすすめ

初等整数論のうち、平方剰余の相互法則の意味を当面の目標としたいと思います。ゆくゆくは、ガウス和、円分体論まで到達したいです。

Eulerのファイ函数(その2)

 \(n\)以下の自然数で\(n\)と互いに素なものの数を\(\varphi(n)\)と書き、オイラーのファイ函数といいました。  Eulerの\(\varphi\)函数が、なぜこのように定義されたのか、どんな場面で役に立つのかについては、下記をご覧ください。

Eulerのファイ函数 - 美的数学のすすめ

2.1 \(\varphi\)函数の性質

 さて、今回は、\(\varphi\)函数の値を具体的に求める際に、必要となるオイラー函数の性質を説明します。オイラー函数を算出する際に押さえておくべき性質は次の2つです

(オイラー函数の性質)

 1.\(n\)と\(m\)が互いに素のとき、\(\varphi(nm)=\varphi(n)\varphi(m)\)

 2.\(p\)を素数、\(k\)を自然数とすると、\(\varphi(p^{k})=p^{k}-p^{k-1}\)

 これを使うと、任意の自然数の\(\varphi\)函数の値は、性質1により、素数のべき乗の場合に帰着します。そして、性質2により、求められるということになります。

 性質1は、オイラー関数についての補足 - tsujimotterのノートブックにうまくその感覚が説明されています。

 性質2は、\(k=1\)の場合に、\(\varphi(p)=p-1\)となります。これは、\(p\)が素数であることから、1から\(p-1\)までの全ての自然数が\(p\)と互いに素であるから成り立っていますね。

2.2 例

 2つの性質を使い、いくつか\(\varphi(n)\)を求めてみましょう。

(例) \(n=10\)とすると、 \[\begin{align} \varphi(10)&=\varphi(2)\varphi(5) \\ &=(2-1)(5-1) \\ &=4 \end{align} \] これは、 \(10\)以下の自然数で\(10\)と互いに素なものは、\(1,\ 3,\ 7,\ 9\ \)の4つであることと整合していますね。

(例) \(n=2015=5\cdot 13\cdot 31\)とすると \[\begin{align} \varphi(2015)&=\varphi(5)\varphi(13)\varphi(31) \\ &=(5-1)(13-1)(31-1) \\ &=1440 \end{align} \]

(例) \(n=2016=2^{5}\cdot 3^{2}\cdot 7\)とすると \[\begin{align} \varphi(2016)&=\varphi(2^{5})\varphi(3^{2})\varphi(7) \\ &=(2^{5}-2^{4})(3^{2}-3)(7-1) \\ &=(32-16)(9-3)6\\ &=576 \end{align} \]

(例) \(n=2017\)とすると\(2017\)は素数なので \[\begin{align} \varphi(2017)&=2017-1 \\ &=2016 \end{align} \]

 \(\varphi(2015)=1440,\varphi(2016)=576,\varphi(2017)=2016\)ということから分かるように、\(n\)を動かすとき、\(\varphi(n)\)は全くばらばらな値をとります。これは、\(\varphi(n)\)が\(n\)の素因数分解の結果に依存しているためですね。

 どうやら、\(n\)を素因数分解せずに\(\varphi(n)\)を求める方法は知られていないようです。この事実と、巨大な合成数(特に(巨大な素数)×(巨大な素数)の場合)の素因数分解が現代のコンピューターをしても困難であるという事実が、公開鍵暗号(RSA)の前提となっているようです。しかし、突如、\(\varphi(n)\)を簡単に求める方法が見つかったりすることはないんでしょうか?

RSA 暗号がようやく分かった気がしたのでまとめてみる - tsujimotterのノートブック

2.3 証明

 性質1は、\(\varphi(n)\)が\( \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\)の位数と等しいことを使って次のように証明することができます。\(\varphi(n)\)が\( \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\)の位数と等しいことは、次をご覧下さい。

Eulerのファイ函数 - 美的数学のすすめ

 \(n\)と\(m\)が互いに素とすると、下の2つの環が同型となります。 \[\left(\mathbb{Z}/nm\mathbb{Z}\right)\cong\left(\mathbb{Z}/n\mathbb{Z}\right)\times \left(\mathbb{Z}/m\mathbb{Z}\right)\]  これは、いわゆる中国剰余定理(Chinese Remainder Theorem)ですね。

  この同型を導く際に、もちろん左の環の元に対し、右の環の元を対応させてもよいですが、むしろ、\(\mathbb{Z}\)からの自然な準同型写像 \[ f\ :\ \mathbb{Z} \longrightarrow \left(\mathbb{Z}/n\mathbb{Z}\right)\times \left(\mathbb{Z}/m\mathbb{Z}\right)\] が全射であること(この部分が本当の中国剰余定理です!)と、\(f\)のKernel(核)が\( (nm\mathbb{Z})\)になることを示すのがエレガントですね!

 すると、両方の既約元(逆元をもつ元)をとることにより、 \[\left(\mathbb{Z}/nm\mathbb{Z}\right)^{\times}\cong\left(\mathbb{Z}/n\mathbb{Z}\right) ^{\times}\times \left(\mathbb{Z}/m\mathbb{Z}\right) ^{\times}\]  が成り立ちます。両辺の位数(元の個数)を比べると、 \[\varphi(nm)=\varphi(n)\varphi(m)\] で証明ができました。

 

 性質2は、次のように証明できます。\(\varphi(p^{k})\)は、\(p^{k}\)以下の自然数で、\(p^{k}\)と互いに素なものの数です。\(p\)が素数であることを考えると、\(p^{k}\)以下の自然数で\(p\)と互いに素でないものは、 \[ p,2p,3p,\cdots, p^{k-1}p\] の\(p^{k-1}\)個あります。つまり、\(p^{k}\)以下の自然数\(p^{k}\)個のうち\(p\)と互いに素でないものは、\(p^{k-1}\)個あることになります。したがって、互いに素なものは、\(p^{k}-p^{k-1}\)となります。つまり、 \[\varphi(p^{k})=p^{k}-p^{k-1}\]

 次回は、剰余類の基本的な性質に戻ります。