オイラーの定理・オイラー関数

 　 オイラー（１７０７～１７８３）は数学の多くの分野で活躍をしましたが，数論についても重要な成果を挙げています。１７６０年オイラーはフェルマーの小定理の研究の中で，フェルマーの小定理を一般化した定理を発表しました。

　この定理とそこで使われる関数φ（ｎ）は初等整数論における重要なもので，色々なところで使われています。　ここではこれらについて説明をします。

　
オイラーの定理とオイラー関数

　オイラー関数φ（ｎ）の定義は次の通りです。

オイラー関数φ（ｎ）

　ｎを正整数とする。このとき，１からｎまでの整数で，ｎと互いに素となるものの個数をφ（ｎ）と表す。

（ここで，整数ｎとａとが互いに素とは，それらの最大公約数が１となることです。）

　この定義によると，

φ（１）＝１，φ（２）＝１，φ（３）＝２，φ（４）＝２，φ（５）＝４，φ（６）＝２，φ（７）＝６，・・・

が直接試すことで，得られます。また

ｐが素数なら，φ（ｐ）＝ｐ－１

となります。実際，１，２，３，・・・，ｐの中で，ｐとの最大公約数が１となるのは，ｐが素数のときは，１，２，３，・・・，ｐ－１です。

　この関数φ（ｎ）を使うと，オイラーの定理は次のようになります。

オイラーの定理

　ｎを正整数とする。ａをｎと互いに素な整数とする。このとき，

ａφ（ｎ）≡１　ｍｏｄ ｎ

が成立する。

　ここで，ｎが素数ｐの場合は（ｎ＝ｐ），φ（ｐ）＝ｐ－１であり，ａとｐが互いに素はｐがａを割り切らないと同じことですから，上の定理でｎ＝ｐ（素数）の場合がフェルマーの小定理です。

　オイラーの定理の証明は色々あります。ここでは，整数の合同についての基本性質を使った証明を挙げます。

オイラーの定理の証明

　１からｎまでの整数でｎと互いに素な数を

ｒ１，ｒ２，・・・，ｒφ（ｎ）

と表します。更にこれらの数にそれぞれａを掛けたもの

ａｒ１，ａｒ２，・・・，ａｒφ（ｎ）

を考えます。ａとｒｉがｎと互いに素ですから，ａｒｉとｎは互いに素です。更に，ａｒ１，ａｒ２，・・・，ａｒφ（ｎ）はそれぞれｎを法にして合同ではありません。実際

ａｒｉ≡ａｒｊ　ｍｏｄ　ｎ

ならば，ａのｎを法とする逆元をこの式の両辺に乗じて，ｒｉ≡ｒｊ　ｍｏｄ　ｎ ，即ちｉ＝ｊとなります。

　ｎと互いに素となる数はｒ１，ｒ２，・・・，ｒφ（ｎ）の どれか１つと合同になりますから，ａｒ１，ａｒ２，・・・，ａｒφ（ｎ）を適当に順序を入れ替えたものがｒ１，ｒ２，・・・，ｒφ（ｎ）とそれぞれ合同になります。従ってそれらを全て掛け合わせたものも合同になります。即ち，

ａｒ１・ａｒ２・・・ａｒφ（ｎ）≡ｒ１・ｒ２・・・ ｒφ（ｎ）　ｍｏｄ　ｎ

が成立します。この両辺にｒ１・ｒ２・・・ｒφ（ｎ）のｎを法とする逆元を乗じると，左辺はａφ（ｎ）ｒ１・ｒ２・・・ ｒφ（ｎ）ですから，

ａφ（ｎ）≡１　ｍｏｄ ｎ

が得られます。（証明終）

　
オイラー関数の計算

　オイラーの定理を実際に活用する場合，オイラー関数の値が必要になることもあります。実は，オイラー関数の値はｎの素因数分解から，容易に計算できます。即ち次の定理が成立します。

オイラー関数の値

　ｎを正整数とする。 ｐ１，ｐ２，・・・，ｐｒをｎの相異なるすべての素因数とする。このとき，

φ（ｎ）＝ｎ（１－１/ｐ１）（１－１/ｐ２）・・・（１－１/ｐｒ）

が成立する。

この定理の証明も色々あります。ここでは中国の剰余定理を使った証明を挙げます。

証明は２つの部分（１），（２）から成ります。（２）で中国の剰余定理を使います。

（１）ｎが素数冪の場合，即ち，素数ｐに対してｎ＝ｐｅとなる場合。このとき，

φ（ｐｅ）＝ｐｅ－ｐｅ－１

となる。

（１）の証明。

　１，２，３，・・・，ｐｅ

の中で，ｐと素でないものはｐの倍数ですから，ｐｃの形に書けます。ここで，１≦ｐｃ≦ｐｅですから，

１≦ｃ≦ｐｅ－１です。従って，ｐと素でないものの個数は，ｐｅ－１となります。故にｐと素のものの個数は

ｐｅ－ｐｅ－１

となります。（（１）の証明終）

（２）ｎとｍを互いに素な正整数とする。このとき，

φ（ｎｍ）＝φ（ｎ）φ（ｍ）

が成立する。

（２）の証明。

ｒ＝φ（ｎ），ｓ＝φ（ｍ），ｔ＝φ（ｎｍ）

として，

ｕ１，ｕ２，・・・，ｕｒ　を　１，２，・・・，ｎ　の中でｎと互いに素な数，

ｖ１，ｖ２，・・・，ｖｓ　を　１，２，・・・，ｍ　の中でｍと互いに素な数，

ｗ１，ｗ２，・・・，ｗｔ　を　１，２，・・・，ｎｍ　の中でｎｍと互いに素な数

とそれぞれ置きます。そこで，ｗｋはｎとｍと互いに素なので，ｎとｍでそれぞれ法を取って考えると，それぞれｎとｍと互いに素になり，

ｗｋ≡ｕｉ　ｍｏｄ　ｎ

ｗｋ≡ｖｊ　ｍｏｄ　ｍ

となるｕｉとｖｊが存在します。同様にして，ｗｋ’に対して

ｗｋ’≡ｕｉ’　ｍｏｄ　ｎ

ｗｋ’≡ｖｊ’　ｍｏｄ　ｍ

となるｕｉ’とｖｊ’を取ります。

　ここで，ｕｉ＝ｕｉ’　かつ ｖｊ＝ｖｊ’　ならば，ｗｋ≡ｗｋ’　ｍｏｄ　ｎｍ　より　ｗｋ＝ｗｋ’　となります。従ってｗｋに対応する組（ｕｉ，ｖｊ）はそれぞれ異なります。ｗｋの個数はｔで，組（ｕｉ，ｖｊ）の個数はｒ・ｓなので，これから

ｔ≦ｒ・ｓ

が得られます。

　逆に，組（ｕｉ，ｖｊ）に対して，

ｗｋ≡ｕｉ　ｍｏｄ　ｎ

ｗｋ≡ｖｊ　ｍｏｄ　ｍ

となる　ｘ　が中国の剰余定理から唯一つ存在します。ここで，ｕｉとｖｊは，それぞれ，ｎとｍと互いに素ですから，ｘはｎｍと互いに素になります。従って，ｘ＝ｗkの形になります。ここで，異なる組（ｕｉ，ｖｊ）に対しては，異なるｗkが対応します。ｗkの個数はｔですから，

ｔ≧ｒ・ｓ

が得られます。以上から，

ｔ＝ｒ・ｓ，即ち，φ（ｎｍ）＝φ（ｎ）φ（ｍ）

が得られます。（（２）の証明終）

（１）と（２）を組み合わせると，次が直ちに得られます。

ｎ＝ｐ１ｅ１・ｐ２ｅ２・・・ｐｒｅｒ　をｎの素因数分解とする。（ｐｉは全て異なるとする。）このとき，

φ（ｎ）＝φ（ｐ１ｅ１）φ（ｐ２ｅ２）・・・φ（ｐｒｅｒ）

＝（ｐ１ｅ１－ｐ１ｅ１－１）（ｐ２ｅ２－ｐ２ｅ２－１）・・・（ｐｒｅｒ－ｐｒｅｒ－１）

＝ｎ（１－１/ｐ１）（１－１/ｐ２）・・・（１－１/ｐｒ）

となる。この最後の式が求めるものでした。（証明終）

この公式を使うとｎの素因数が全て分かれば（このことは素因数分解が出来るということと殆んど同じことです），φ（ｎ）の計算は簡単に可能です。この公式を使ったプログラムを以下に挙げます。

Function Phi(n)
   If ((n<=0) or (n<>Int(n))) then 
      Print "引数がφの定義外です。"
   Else
      Result = n
      While n>1
         p=PFactor(n)
         While n/p = Int(n/p)
            n = n/p
         Wend
         Result = Result - Result/p
      Wend
      Phi = Result
   End if
End Function

　オイラーの定理を使うと，ｐｎを法とする高い冪の計算が，ｐｎ-ｐｎ－１以下の冪の計算に還元されることが分かります。

例えば，５４＝６２５，φ（６２５）＝５００

９７１２３４５≡９７３４５＊（（９７５００）２４）≡９７３４５≡３５７　(mod ６２５）

となります。大きな冪の計算は冪乗法で可能ですが，φ（ｎ）が小さい場合は，オイラーの定理を使ってから，冪乗法を使う方が効率的です。

まとめ

　オイラーの定理・オイラー関数についてここで紹介したことは，ほんの始めの部分です。機会をみて先に進みます。