オイラーの関数                              戻る

 自然数 1、2、3、・・・、n の中で、n と互いに素な数の個数は、オイラーの関数φ(n)で
表される。

例 1と1は互いに素なので、φ(1)=1

 1、2の中で2と互いに素なのは1のみで、φ(2)=1

 1、2、3の中で3と互いに素なのは1と2の2個あるので、φ(3)=2

 1、2、3、4の中で4と互いに素なのは1と3の2個あるので、φ(4)=2

 1、2、3、4、5の中で5と互いに素なのは1、2、3、4の4個あるので、φ(5)=4

 1、2、3、4、5、6の中で6と互いに素なのは1、5の2個あるので、φ(6)=2

 1、2、3、4、5、6、7の中で7と互いに素なのは1、2、3、4、5、6の6個あるので、φ(7)=6

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

  (1) 素数 p に対して、 φ(p)=p−1  特に、φ(p)=p−pn−1

  (2) a と b が互いに素ならば、 φ(ab)=φ(a)φ(b)

 (証明)はこちらを参照。

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

例 φ(2)=2−1=1 、φ(3)=3−1=2 、φ(4)=φ(22)=4−2=2、
  φ(6)=φ(2)φ(3)=1×2=2 、φ(12)=φ(4)φ(3)=2×2=4

 n=1〜20のφ(n)の値を表にまとめると、(参考→「A000010」)

10 11 12 13 14 15 16 17 18 19 20
φ(n) 10 12 16 18


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

   (1) φ(12)     (2) φ(1800)

(解)(1) φ(12)=φ(4)φ(3)=2×2=4

(2) φ(1800)=φ(23)φ(32)φ(52)=(23−22)(32−3)(52−5)=480  (終)


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

  (3) n=p・・・r のとき、 φ(n)=n(1−1/p)(1−1/q)・・・(1−1/r)

(証明) 性質(1)(2)より、n=p・・・r のとき、

 φ(n)=φ(p)φ(q)・・・φ(r)=(p−pa-1)(q−qb-1)・・・(r−rc-1

     =n(1−1/p)(1−1/q)・・・(1−1/r)  (証終)

 この性質(3)を用いれば、上記の問題(2)は次のように計算される。

  φ(1800)=1800(1−1/2)(1−1/3)(1−1/5)
         =1800(1/2)(2/3)(4/5)=480

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

 1から1800までの自然数のうち、2または3または5で割り切れる数の個数は、

  900+600+360−300−120−180+60=1320

 よって、求める個数は、 1800−1320=480(個)

 φ(1800)に絡む問題として、次は新鮮である。

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

(解) 求める和は、

 1/1800+7/1800+11/1800+・・・+1789/1800+1793/1800+1799/1800

で、項数は、φ(1800)=480 である。

 kと1800が互いに素のとき、1800−kと1800も互いに素となるので、

 和=(1+1799)×(480÷2)/1800=240

となる。  (終)


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

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

 フェルマーの小定理

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

 自然数12の正の約数は、1、2、3、4、6、12の6個ある。

 このとき、 φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12)

       =1+1+2+2+2+4=12 となる。

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

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

(解) n=p・・・r のとき、正の約数のオイラーの関数の総和は、

  (φ(1)+φ(p)+・・・+φ(p))
    ×(φ(1)+φ(q)+・・・+φ(q))
      ・・・
       ×(φ(1)+φ(r)+・・・+φ(r))

φ(1)+φ(p)+・・・+φ(p)=1+(p−1)+・・・+p−pa-1=p

 同様にして、 (φ(1)+φ(q)+・・・+φ(q))=q
           ・・・
         (φ(1)+φ(r)+・・・+φ(r))=r

なので、

  (φ(1)+φ(p)+・・・+φ(p))
    ×(φ(1)+φ(q)+・・・+φ(q))
      ・・・
       ×(φ(1)+φ(r)+・・・+φ(r))=p・・・r=n  (終)

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

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

(解) すべての頂点を通る図形の個数は、φ(n)/2であるので、 φ(n)/2=4 から、

   φ(n)=8

 n=pq とおくと、 (p−1)(q−1)=8 となるので、解は、 p=5、q=3

 よって、n=5×3=15  (終)

問題  xy座標平面上で、3直線 y=0、x=5、y=x で囲まれた直角三角形を考える。この
    三角形の周および内部には合計21個の格子点がある。

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

(解) 線分上の点で原点以外の格子点の座標を(x,y)とおくと、0≦y≦x で、

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

  1+φ(1)+φ(2)+φ(3)+φ(4)+φ(5)=1+1+1+2+2+4=11(本)  (終)


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

(参考) 横浜市立大学(平成18年度前期)

問題  mを正の整数とし、p、qを異なる素数とする。n=pのとき、φ(n)≧n/3 が
    成り立つことを示せ。

(解) n=pのとき、

  φ(n)=n(1−1/p)(1−1/q)≧n(1−1/2)(1−1/3)=n/3  (終)

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

問題  φ(n)=n/3 のとき、n=2 (a≧1、b≧1)であることを示せ。

(解) n=p・・・sd のとき、φ(n)=n(1−1/p)(1−1/q)(1−1/r)・・・(1−1/s)

  よって、題意より、 (1−1/p)(1−1/q)(1−1/r)・・・(1−1/s)=1/3

 すなわち、 3(p−1)(q−1)(r−1)・・・(s−1)=pqr・・・s

 ここで、 2≦p<q<r<・・・<s と仮定しても一般性を失わない。

 p≧3 とすると、 左辺=偶数、右辺=奇数 となり矛盾するので、 p=2

 このとき、 3(q−1)(r−1)・・・(s−1)=2qr・・・s で、q−1=2 でなければならない。

 よって、 q=3 で、 (r−1)・・・(s−1)=r・・・s となり、偶数=奇数 となり、矛盾。

 以上から、n=p で、p=2、q=3 に限る。

 すなわち、 n=2 (a≧1、b≧1)である。  (終)


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

フェルマーの小定理


 p が素数で、a が p とは互いに素な自然数とするとき、 ap−1 ≡ 1 (mod p)

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

フェルマーの定理

 a と n が互いに素な自然数とするとき、 aφ(n) ≡ 1 (mod n)

 (証明)は、こちらを参照。


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

問題  32020の下2桁を求めよ。

(解) φ(100)=100×(1−1/2)(1−1/5)=40 なので、

 フェルマーの定理より、 340≡1 (mod 100)

  ここで、2020÷40=50 あまり 20 なので、

 32020=(34050・(320)≡320 (mod 100)

  ここで、 310=59049≡49 (mod 100) なので、

 32020≡49×49=2401≡1 (mod 100)

 以上から、32020の下2桁は、01 である。  (終)

問題  120、220、320、・・・、2020 の20個の数について、それぞれの下2桁は何通りの
    可能性があるか調べよ。

(解) 20=5×4 に注意して、

 a≡0 (mod 5) のとき、 a20≡0 (mod 5)

  a≡0 (mod 2) のとき、 a20≡0 (mod 4)

   このとき、 a20≡0 (mod 20)

  実際に、a20=5m (mは自然数)、a20=4n (nは自然数) から、5m=4n

  5と4は互いに素なので、 m=4k (kは自然数) とおける。

  よって、 a20=5m=20k (kは自然数) となり、 a20≡0 (mod 20)

  a≡1 (mod 2) のとき、 φ(4)=2 より、a2≡1 (mod 4)

   すなわち、 a20≡1 (mod 4) より、 a20≡5 (mod 20)

  実際に、a20=5m (mは自然数)、a20=4n+1 (nは自然数) から、

   5m=4n+1 ここで、 5・1=4・1+1 より、 5(m−1)=4(n−1) なので、

 5と4は互いに素より、 m−1=4k すなわち、 m=4k+1 (kは自然数) とおける。

  よって、 a20=5m=20k+5 (kは自然数) となり、 a20≡5 (mod 20)

 a≡1、2、3、4 (mod 5) のとき、 φ(5)=4 より、 a4≡1 (mod 5)

   すなわち、 a20≡1 (mod 5)

  a≡0 (mod 2) のとき、 a20≡0 (mod 4)

   このとき、 a20≡16 (mod 20)

  実際に、a20=5m+1 (mは自然数)、a20=4n (nは自然数) から、

   5m+1=4n  ここで、 5・3+1=4・4 より、 5(m−3)=4(n−4) なので、

 5と4は互いに素より、 m−3=4k すなわち、 m=4k+3 (kは自然数) とおける。

  よって、 a20=5m+1=20k+16 (kは自然数) となり、 a20≡16 (mod 20)

  a≡1 (mod 2) のとき、 φ(4)=2 より、a2≡1 (mod 4)

   すなわち、 a20≡1 (mod 4) より、 a20≡1 (mod 20)

  実際に、a20=5m+1 (mは自然数)、a20=4n+1 (nは自然数) から、

   5m+1=4n+1 なので、 5m=4n

 5と4は互いに素より、 m=4k (kは自然数) とおける。

  よって、 a20=5m+1=20k+1 (kは自然数) となり、 a20≡1 (mod 20)

 以上から、下2桁の可能性は、 0、1、5、16 の4通りある。  (終)


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


問題  9^10^11 の十の位を求めよ。

(解) φ(100)=100×(1/2)×(4/5)=40 より、 940≡1 (mod 100)

 よって、 9^10^11=(940)^2500000000≡1 (mod 100) より、

 十の位は、0  (終)



  以下、工事中!