オイラーの関数φ（ｎ）は１からｎ−１までの整数のうち，ｎと互いに素になるものの個数

　　φ（ｎ）＝＃（Ｚ／ｎＺ）

として定義されます．たとえば，ｎ＝７の場合，１，２，３，４，５，６なのでφ（７）＝６，ｎ＝１０の場合１，３，７，９がそうなのでφ（１０）＝４となります．

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

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

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

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

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

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

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

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

したがって，

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

となります．

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

φ（１５）＝φ（３）φ（５）＝８＝１５（１-１/３）（１-１/５）＝８

φ（６３）＝φ（７）φ（９）＝３６＝６３（１-１/３）（１-１/７）＝３６

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

　φ（ｍ）は，ｍと互いに素であり，ｍより小さい整数ｒ，１≦ｒ＜ｍの個数として定義される．すなわち，φ（ｍ）は１からｍ−１までの整数のうち，ｍと公約数をもたない数はいくつあるかを数えた数を表す．

　ｍ＝９→１，２，４，５，７，８→φ（９）＝６

　ｍ＝１０→１，３，７，９→φ（１０）＝４

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

　φ（５）＝４，φ（６）＝２，φ（７）＝６，φ（８）＝４

　φ（９）＝６，φ（１０）＝４，

　φ（ｐ）＝ｐ−１

　φ（ｐ^a）＝（ｐ−１）ｐ^(a-1)＝ｐ^a（１−１／ｐ）

　φ（ｍ）＝ｍΠ（１−１／ｐi）

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

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