オイラーの関数　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　

　自然数 １、２、３、・・・、ｎ の中で、ｎ と互いに素な数の個数は、オイラーの関数φ（ｎ）で
表される。この関数は、オイラーのφ関数とかオイラーのトーシェント関数とも言われる。

例　１と１は互いに素なので、φ（１）＝１

　１、２の中で２と互いに素なのは１のみで、φ（２）＝１

　１、２、３の中で３と互いに素なのは１と２の２個あるので、φ（３）＝２

　１、２、３、４の中で４と互いに素なのは１と３の２個あるので、φ（４）＝２

　１、２、３、４、５の中で５と互いに素なのは１、２、３、４の４個あるので、φ（５）＝４

　１、２、３、４、５、６の中で６と互いに素なのは１、５の２個あるので、φ（６）＝２

　１、２、３、４、５、６、７の中で７と互いに素なのは１、２、３、４、５、６の６個あるので、φ（７）＝６

　ｎの値が大きくなると、上記の計算では辛いものになるので、オイラーの関数の次の性質
を利用した方がいいだろう。

　　（１）　素数 ｐ に対して、　φ（ｐ）＝ｐ−１　　特に、φ（ｐ^ｎ）＝ｐ^ｎ−ｐ^ｎ−1

　　（２）　ａ と ｂ が互いに素ならば、　φ（ａｂ）＝φ（ａ）φ（ｂ）

　（証明）はこちらを参照。

　この性質を用いると、上記の計算は次のようにも出来る。

例　φ（２）＝２−１＝１　、φ（３）＝３−１＝２　、φ（４）＝φ（２²）＝４−２＝２、
　　φ（６）＝φ（２）φ（３）＝１×２＝２　、φ（１２）＝φ（４）φ（３）＝２×２＝４

　ｎ＝１〜２０のφ（ｎ）の値を表にまとめると、（参考→「A000010」）

問題　次のオイラーの関数の値を求めよ。

　　　（１）　φ（１２）　　　　　（２）　φ（１８００）

（解）（１）　φ（１２）＝φ（４）φ（３）＝２×２＝４

（２）　φ（１８００）＝φ（２³）φ（３²）φ（５²）＝（２³−２²）（３²−３）（５²−５）＝４８０　　（終）


　オイラーの関数の性質で、次の公式も実用的でしょう。

　　（３）　ｎ＝ｐ^ａｑ^ｂ・・・ｒ^ｃ　のとき、　φ（ｎ）＝ｎ（１−１/ｐ）（１−１/ｑ）・・・（１−１/ｒ）

（証明）　性質（１）（２）より、ｎ＝ｐ^ａｑ^ｂ・・・ｒ^ｃ　のとき、

　φ（ｎ）＝φ（ｐ^ａ）φ（ｑ^ｂ）・・・φ（ｒ^ｃ）＝（ｐ^ａ−ｐ^ａ-1）（ｑ^ｂ−ｑ^ｂ-1）・・・（ｒ^ｃ−ｒ^ｃ-1）

　　　　 ＝ｎ（１−１/ｐ）（１−１/ｑ）・・・（１−１/ｒ）　　（証終）

　この性質（３）を用いれば、上記の問題（２）は次のように計算される。

　　φ（１８００）＝１８００（１−１/２）（１−１/３）（１−１/５）
　　　　　　　　　＝１８００（１/２）（２/３）（４/５）＝４８０

　また、個数定理を用いても求められる。

　１から１８００までの自然数のうち、２または３または５で割り切れる数の個数は、

　　９００＋６００＋３６０−３００−１２０−１８０＋６０＝１３２０

　よって、求める個数は、　１８００−１３２０＝４８０（個）

　φ（１８００）に絡む問題として、次は新鮮である。

問題　０より大きく１より小さい分数のうち、分母が１８００である既約分数の総和を求めよ。

（解）　求める和は、

　１/１８００＋７/１８００＋１１/１８００＋・・・＋１７８９/１８００＋１７９３/１８００＋１７９９/１８００

で、項数は、φ（１８００）＝４８０　である。

　ｋと１８００が互いに素のとき、１８００−ｋと１８００も互いに素となるので、

　和＝（１＋１７９９）×（４８０÷２）/１８００＝２４０

となる。　　（終）


　オイラーの関数は、当ＨＰでも各所に登場している。例えば、

　１．整数論の基礎知識　、フェルマーの定理　、隣り合う分数　、公開鍵暗号の作り方

　フェルマーの小定理

　このページでは、オイラーの関数について更なる深みを目指してまとめていきたいと思う。

　自然数１２の正の約数は、１、２、３、４、６、１２の６個ある。

　このとき、　φ（１）＋φ（２）＋φ（３）＋φ（４）＋φ（６）＋φ（１２）

　　　　　　　＝１＋１＋２＋２＋２＋４＝１２　となる。

　このことを一般化すると、次の問題となる。

問題　自然数ｎの正の約数のオイラーの関数の総和は、ｎであることを示せ。

（解）　ｎ＝ｐ^ａｑ^ｂ・・・ｒ^ｃ　のとき、正の約数のオイラーの関数の総和は、

　　（φ（1）＋φ（ｐ）＋・・・＋φ（ｐ^ａ））
　　　　×（φ（1）＋φ（ｑ）＋・・・＋φ（ｑ^ｂ））
　　　　　　・・・
　　　　　　　×（φ（1）＋φ（ｒ）＋・・・＋φ（ｒ^ｃ））

φ（1）＋φ（ｐ）＋・・・＋φ（ｐ^ａ）＝１＋（ｐ−１）＋・・・＋ｐ^ａ−ｐ^ａ-1＝ｐ^ａ

　同様にして、　（φ（1）＋φ（ｑ）＋・・・＋φ（ｑ^ｂ））＝ｑ^ｂ
　　　　　　　　　　　・・・
　　　　　　　　　（φ（1）＋φ（ｒ）＋・・・＋φ（ｒ^ｃ））＝ｒ^ｃ

なので、

　　（φ（1）＋φ（ｐ）＋・・・＋φ（ｐ^ａ））
　　　　×（φ（1）＋φ（ｑ）＋・・・＋φ（ｑ^ｂ））
　　　　　　・・・
　　　　　　　×（φ（1）＋φ（ｒ）＋・・・＋φ（ｒ^ｃ））＝ｐ^ａｑ^ｂ・・・ｒ^ｃ＝ｎ　　（終）

問題　正ｎ角形の１つの頂点から出発して、長さの等しい対角線、または、辺を連続して左
　　　回りに引く。何周かして元の頂点に戻るまでに全ての頂点を通過して、一つの図形を
　　　描く。

　　　　この図形が４通りであるとき、自然数ｎの値を求めよ。ただし、ｎは２つの素数を掛け
　　　合わせたものとする。

（解）　すべての頂点を通る図形の個数は、φ（ｎ）/２であるので、　φ（ｎ）/２＝４　から、

　　　φ（ｎ）＝８

　ｎ＝ｐｑ　とおくと、　（ｐ−１）（ｑ−１）＝８　となるので、解は、　ｐ＝５、ｑ＝３

　よって、ｎ＝５×３＝１５　　（終）

問題　　ｘｙ座標平面上で、３直線 ｙ＝０、ｘ＝５、ｙ＝ｘ で囲まれた直角三角形を考える。この
　　　　三角形の周および内部には合計２１個の格子点がある。

　　　今、原点以外の格子点の一つと原点を結ぶ線分を引くとき、両端以外に格子点が存在
　　しない線分は何本引けるか。

（解）　線分上の点で原点以外の格子点の座標を（ｘ，ｙ）とおくと、０≦ｙ≦ｘ　で、

　　題意より、ｘとｙは互いに素である。このとき、求める線分の本数は、

　　１＋φ(１)＋φ(２)＋φ(３)＋φ(４)＋φ(５)＝１＋１＋１＋２＋２＋４＝１１（本）　　（終）


　オイラーの関数は大学入試問題としても手頃なのか出題されやすいようだ。

（参考）　横浜市立大学（平成１８年度前期）

問題　　ｍを正の整数とし、ｐ、ｑを異なる素数とする。ｎ＝ｐ^ｍｑ^ｍのとき、φ（ｎ）≧ｎ/３　が
　　　　成り立つことを示せ。

（解）　ｎ＝ｐ^ｍｑ^ｍのとき、

　　φ（ｎ）＝ｎ（１−１/ｐ）（１−１/ｑ）≧ｎ（１−１/２）（１−１/３）＝ｎ/３　　（終）

　上記の問題のほとんど逆バージョンです。

問題　　φ（ｎ）＝ｎ/３　のとき、ｎ＝２^ａ３^ｂ　（ａ≧１、ｂ≧１）であることを示せ。

（解）　ｎ＝ｐ^ａｑ^ｂｒ^ｃ・・・ｓ^d　のとき、φ（ｎ）＝ｎ（１−１/ｐ）（１−１/ｑ）（１−１/ｒ）・・・（１−１/ｓ）

　　よって、題意より、　（１−１/ｐ）（１−１/ｑ）（１−１/ｒ）・・・（１−１/ｓ）＝１/３

　すなわち、　３（ｐ−１）（ｑ−１）（ｒ−１）・・・（ｓ−１）＝ｐｑｒ・・・ｓ

　ここで、　２≦ｐ＜ｑ＜ｒ＜・・・＜ｓ　と仮定しても一般性を失わない。

　ｐ≧３　とすると、　左辺＝偶数、右辺＝奇数　となり矛盾するので、　ｐ＝２

　このとき、　３（ｑ−１）（ｒ−１）・・・（ｓ−１）＝２ｑｒ・・・ｓ　で、ｑ−１＝２　でなければならない。

　よって、　ｑ＝３　で、　（ｒ−１）・・・（ｓ−１）＝ｒ・・・ｓ　となり、偶数＝奇数　となり、矛盾。

　以上から、ｎ＝ｐ^ａｑ^ｂ　で、ｐ＝２、ｑ＝３　に限る。

　すなわち、　ｎ＝２^ａ３^ｂ　（ａ≧１、ｂ≧１）である。　　（終）


　次の定理は有名でしょう。

フェルマーの小定理

　ｐ が素数で、ａ が ｐ とは互いに素な自然数とするとき、　ａ^ｐ−1 ≡ １　（ｍｏｄ　ｐ）

は、オイラーの関数 φ（ｎ） を用いて、次のように一般化される。

フェルマーの定理

　ａ と ｎ が互いに素な自然数とするとき、　ａ^φ（n） ≡ １　（ｍｏｄ　n）

　（証明）は、こちらを参照。


　フェルマーの定理を用いると、次の問題が鮮やかに解かれる。

問題　　３²⁰²⁰の下２桁を求めよ。

（解）　φ（１００）＝１００×（１−１/２）（１−１/５）＝４０　なので、

　フェルマーの定理より、　３⁴⁰≡１　（ｍｏｄ　１００）

　　ここで、２０２０÷４０＝５０　あまり　２０　なので、

　３²⁰²⁰＝（３⁴⁰）⁵⁰・（３²⁰）≡３²⁰　（ｍｏｄ　１００）

　　ここで、　３¹⁰＝５９０４９≡４９　（ｍｏｄ　１００）　なので、

　３²⁰²⁰≡４９×４９＝２４０１≡１　（ｍｏｄ　１００）

　以上から、３²⁰²⁰の下２桁は、０１　である。　　（終）

問題　　１²⁰、２²⁰、３²⁰、・・・、２０²⁰ の２０個の数について、それぞれの下２桁は何通りの
　　　　可能性があるか調べよ。

（解）　２０＝５×４　に注意して、

　ａ≡０　（ｍｏｄ　５）　のとき、　ａ²⁰≡０　（ｍｏｄ　５）

　　ａ≡０　（ｍｏｄ　２）　のとき、　ａ²⁰≡０　（ｍｏｄ　４）

　　　このとき、　ａ²⁰≡０　（ｍｏｄ　２０）

　　実際に、ａ²⁰＝５ｍ　（ｍは自然数）、ａ²⁰＝４ｎ　（ｎは自然数）　から、５ｍ＝４ｎ

　　５と４は互いに素なので、　ｍ＝４ｋ　（ｋは自然数）　とおける。

　　よって、　ａ²⁰＝５ｍ＝２０ｋ　（ｋは自然数）　となり、　ａ²⁰≡０　（ｍｏｄ　２０）

　　ａ≡１　（ｍｏｄ　２）　のとき、　φ（４）＝２　より、ａ²≡１　（ｍｏｄ　４）

　　　すなわち、　ａ²⁰≡１　（ｍｏｄ　４）　より、　ａ²⁰≡５　（ｍｏｄ　２０）

　　実際に、ａ²⁰＝５ｍ　（ｍは自然数）、ａ²⁰＝４ｎ＋１　（ｎは自然数）　から、

　　　５ｍ＝４ｎ＋１　ここで、　５・１＝４・１＋１　より、　５（ｍ−１）＝４（ｎ−１）　なので、

　５と４は互いに素より、　ｍ−１＝４ｋ　すなわち、　ｍ＝４ｋ＋１　（ｋは自然数）　とおける。

　　よって、　ａ²⁰＝５ｍ＝２０ｋ＋５　（ｋは自然数）　となり、　ａ²⁰≡５　（ｍｏｄ　２０）

　ａ≡１、２、３、４　（ｍｏｄ　５）　のとき、　φ（５）＝４　より、　ａ⁴≡１　（ｍｏｄ　５）

　　　すなわち、　ａ²⁰≡１　（ｍｏｄ　５）

　　ａ≡０　（ｍｏｄ　２）　のとき、　ａ²⁰≡０　（ｍｏｄ　４）

　　　このとき、　ａ²⁰≡１６　（ｍｏｄ　２０）

　　実際に、ａ²⁰＝５ｍ＋１　（ｍは自然数）、ａ²⁰＝４ｎ　（ｎは自然数）　から、

　　　５ｍ＋１＝４ｎ　　ここで、　５・３＋１＝４・４　より、　５（ｍ−３）＝４（ｎ−４）　なので、

　５と４は互いに素より、　ｍ−３＝４ｋ　すなわち、　ｍ＝４ｋ＋３　（ｋは自然数）　とおける。

　　よって、　ａ²⁰＝５ｍ＋１＝２０ｋ＋１６　（ｋは自然数）　となり、　ａ²⁰≡１６　（ｍｏｄ　２０）

　　ａ≡１　（ｍｏｄ　２）　のとき、　φ（４）＝２　より、ａ²≡１　（ｍｏｄ　４）

　　　すなわち、　ａ²⁰≡１　（ｍｏｄ　４）　より、　ａ²⁰≡１　（ｍｏｄ　２０）

　　実際に、ａ²⁰＝５ｍ＋１　（ｍは自然数）、ａ²⁰＝４ｎ＋１　（ｎは自然数）　から、

　　　５ｍ＋１＝４ｎ＋１　なので、　５ｍ＝４ｎ

　５と４は互いに素より、　ｍ＝４ｋ　（ｋは自然数）　とおける。

　　よって、　ａ²⁰＝５ｍ＋１＝２０ｋ＋１　（ｋは自然数）　となり、　ａ²⁰≡１　（ｍｏｄ　２０）

　以上から、下２桁の可能性は、　０、１、５、１６　の４通りある。　　（終）


（コメント）　解答を少し詳しいものに書き換えました。


問題　　９＾１０＾１１　の十の位を求めよ。

（解）　φ（１００）＝１００×（１/２）×（４/５）＝４０　より、　９⁴⁰≡１　（ｍｏｄ　１００）

　よって、　９＾１０＾１１＝（９⁴⁰）＾２５００００００００≡１　（ｍｏｄ　１００）　より、

　十の位は、０　　（終）



　　以下、工事中！