【５】素数定理とエラトステネスのふるい

　オイラーの関数φ（ｄ）は１からｄ−１までの整数のうち，ｄと互いに素になるものの個数として定義されます．たとえば，ｄ＝７の場合１，２，３，４，５，６なのでφ（７）＝６，ｄ＝１０の場合１，３，７，９がそうなのでφ（１０）＝４となります．

　１は素因数をもたないため，φ（１）は意味をなしませんが，特別にφ（１）＝１と定義されます．

　　φ（１）＝φ（２）＝１，

　　φ（３）＝φ（４）＝φ（６）＝２，

　　φ（５）＝φ（８）＝φ（１０）＝４，

　　φ（７）＝φ（９）＝６

　１７６０年頃，オイラーは，数ｎが素因数ｐ，ｑ，ｒ，・・・をもつときに，それらの重複度にかかわらず，

　　φ（ｎ）＝ｎ（１−１／ｐ）（１−１／ｑ）（１−１／ｒ）・・・

であることを示しました．

<DIV>　この原理は「エラトステネスのふるい」によっているのですが，たとえば，１０＝２・５，４４＝２^2・１１，１００＝２^2・５^2より，

　　φ（１０）＝１０（１−１／２）（１−１／５）＝４

　　φ（４４）＝４４（１−１／２）（１−１／１１）＝２０

　　φ（１００）＝１００（１−１／２）（１−１／５）＝４０

　また，任意の素数ｐに対して，

　　φ（ｐ^n）＝ｐ^n（１−１／ｐ）

したがって，

　　φ（ｐ）＝ｐ（１−１／ｐ）＝ｐ−１

となります．

　また，

　　ｎ＝φ（ｐ）＋φ（ｑ）＋φ（ｒ）＋φ（ｐｑ）＋・・・＋φ（ｐｑｒ）＋・・・

が成り立ちます．すなわち，どんな数ｎもすべての約数のオイラー関数を足し合わせた値と一致するのです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　なお，ｄと互いに素な任意の整数ｍに対して，

　　ｍ^φ（ｄ）＝１　　　（ｍｏｄ　ｄ）

が成り立つことを主張しているのが，オイラーの定理です．オイラーの定理はフェルマーの小定理

　　ａ^（ｐ−１）＝１　　　（ｍｏｄ　ｐ）

も一般化したものとなっています．さらに，その後，ガウスとカーマイケルによって，オイラーの定理の一般化がなされました．

　ｐが素数ならば，フェルマーの小定理により

　　ａ^ｐ＝ａ　　　（ｍｏｄ　ｐ）

ですが，その逆は成り立ちません．ｎと互いに素であるすべてのａに対して，

　　ａ^ｎ＝ａ　　　（ｍｏｄ　ｎ）

が成り立つ合成数は，カーマイケル数（完全擬素数）と呼ばれます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝