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

   オイラー(1707~1783)は数学の多くの分野で活躍をしましたが,数論についても重要な成果を挙げています。1760年オイラーはフェルマーの小定理の研究の中で,フェルマーの小定理を一般化した定理を発表しました。

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

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

 オイラー関数φ(n)の定義は次の通りです。

オイラー関数φ(n)

 nを正整数とする。このとき,1からnまでの整数で,nと互いに素となるものの個数をφ(n)と表す。

(ここで,整数nとaとが互いに素とは,それらの最大公約数が1となることです。)

 この定義によると,

φ(1)=1,φ(2)=1,φ(3)=2,φ(4)=2,φ(5)=4,φ(6)=2,φ(7)=6,・・・

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

pが素数なら,φ(p)=p-1

となります。実際,1,2,3,・・・,pの中で,pとの最大公約数が1となるのは,pが素数のときは,1,2,3,・・・,p-1です。

 この関数φ(n)を使うと,オイラーの定理は次のようになります。

オイラーの定理

 nを正整数とする。aをnと互いに素な整数とする。このとき,

φ(n)≡1 mod n

が成立する。

 ここで,nが素数pの場合は(n=p),φ(p)=p-1であり,aとpが互いに素はpがaを割り切らないと同じことですから,上の定理でn=p(素数)の場合がフェルマーの小定理です。


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

オイラーの定理の証明

 1からnまでの整数でnと互いに素な数を

,r,・・・,rφ(n)

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

ar,ar,・・・,arφ(n)

を考えます。aとrがnと互いに素ですから,arとnは互いに素です。更に,ar,ar,・・・,arφ(n)はそれぞれnを法にして合同ではありません。実際

ar≡ar mod n

ならば,aのnを法とする逆元をこの式の両辺に乗じて,r≡r mod n ,即ちi=jとなります。

 nと互いに素となる数はr,r,・・・,rφ(n)の どれか1つと合同になりますから,ar,ar,・・・,arφ(n)を適当に順序を入れ替えたものがr,r,・・・,rφ(n)とそれぞれ合同になります。従ってそれらを全て掛け合わせたものも合同になります。即ち,

ar1・ar・・・arφ(n)≡r・r・・・ rφ(n) mod n

が成立します。この両辺にr・r・・・rφ(n)のnを法とする逆元を乗じると,左辺はaφ(n)・r・・・ rφ(n)ですから,

φ(n)≡1 mod n

が得られます。(証明終)

 
オイラー関数の計算

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

オイラー関数の値

 nを正整数とする。 p1,p2,・・・,prをnの相異なるすべての素因数とする。このとき,

φ(n)=n(1-1/p)(1-1/p)・・・(1-1/p

が成立する。

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

証明は2つの部分(1),(2)から成ります。(2)で中国の剰余定理を使います。

(1)nが素数冪の場合,即ち,素数pに対してn=pとなる場合。このとき,

φ(p)=p-pe-1

となる。

(1)の証明。

 1,2,3,・・・,p

の中で,pと素でないものはpの倍数ですから,pcの形に書けます。ここで,1≦pc≦pですから,

1≦c≦pe-1です。従って,pと素でないものの個数は,pe-1となります。故にpと素のものの個数は

-pe-1

となります。((1)の証明終)

(2)nとmを互いに素な正整数とする。このとき,

φ(nm)=φ(n)φ(m)

が成立する。

(2)の証明。

r=φ(n),s=φ(m),t=φ(nm)

として,

,u,・・・,u を 1,2,・・・,n の中でnと互いに素な数,

,v,・・・,v を 1,2,・・・,m の中でmと互いに素な数,

,w,・・・,w を 1,2,・・・,nm の中でnmと互いに素な数

とそれぞれ置きます。そこで,wはnとmと互いに素なので,nとmでそれぞれ法を取って考えると,それぞれnとmと互いに素になり,

≡u mod n

≡v mod m

となるuとvが存在します。同様にして,wk’に対して

k’≡ui’ mod n

k’≡vj’ mod m

となるui’とvj’を取ります。

 ここで,u=ui’ かつ v=vj’ ならば,w≡wk’ mod nm より w=wk’ となります。従ってwに対応する組(u,v)はそれぞれ異なります。wの個数はtで,組(u,v)の個数はr・sなので,これから

t≦r・s

が得られます。

 逆に,組(u,v)に対して,

≡u mod n

≡v mod m

となる x が中国の剰余定理から唯一つ存在します。ここで,uとvは,それぞれ,nとmと互いに素ですから,xはnmと互いに素になります。従って,x=wkの形になります。ここで,異なる組(u,v)に対しては,異なるwkが対応します。wkの個数はtですから,

t≧r・s

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

t=r・s,即ち,φ(nm)=φ(n)φ(m)

が得られます。((2)の証明終)

(1)と(2)を組み合わせると,次が直ちに得られます。

n=pe1・pe2・・・per をnの素因数分解とする。(pは全て異なるとする。)このとき,

φ(n)=φ(pe1)φ(pe2)・・・φ(per

=(pe1-pe1-1)(pe2-pe2-1)・・・(per-per-1

=n(1-1/p)(1-1/p)・・・(1-1/p

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

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


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

 オイラーの定理を使うと,pを法とする高い冪の計算が,p-pn-1以下の冪の計算に還元されることが分かります。

例えば,5=625,φ(625)=500

9712345≡97345*((9750024)≡97345≡357 (mod 625)

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

まとめ

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