■トーシェント関数と非トーション(その51)

オイラーの関数φ(n)は1からn−1までの整数のうち,nと互いに素になるものの個数

  φ(n)=#(Z/nZ)

として定義されます.たとえば,n=7の場合,1,2,3,4,5,6なのでφ(7)=6,n=10の場合1,3,7,9がそうなのでφ(10)=4となります.

 1760年頃,オイラーは,数nが素因数p,q,r,・・・をもつときに,それらの重複度にかかわらず,

  φ(n)=n(1−1/p)(1−1/q)(1−1/r)・・・

であることを示しました.この原理は「エラトステネスのふるい」によっているのですが,たとえば,10=2・5,44=2^2・11,100=2^2・5^2より,

  φ(10)=10(1−1/2)(1−1/5)=4

  φ(44)=44(1−1/2)(1−1/11)=20

  φ(100)=100(1−1/2)(1−1/5)=40

また,任意の素数pに対して,

  φ(p^n)=p^n(1−1/p)

したがって,

  φ(p)=p(1−1/p)=p−1

となります.

===================================

φ(15)=φ(3)φ(5)=8=15(1-1/3)(1-1/5)=8

φ(63)=φ(7)φ(9)=36=63(1-1/3)(1-1/7)=36

===================================

 φ(m)は,mと互いに素であり,mより小さい整数r,1≦r<mの個数として定義される.すなわち,φ(m)は1からm−1までの整数のうち,mと公約数をもたない数はいくつあるかを数えた数を表す.

 m=9→1,2,4,5,7,8→φ(9)=6

 m=10→1,3,7,9→φ(10)=4

 φ(1)=1,φ(2)=1,φ(3)=2,φ(4)=2

 φ(5)=4,φ(6)=2,φ(7)=6,φ(8)=4

 φ(9)=6,φ(10)=4,

 φ(p)=p−1

 φ(p^a)=(p−1)p^(a-1)=p^a(1−1/p)

 φ(m)=mΠ(1−1/pi)

 φ(10)=10(1−1/2)(1−1/5)=4

===================================

φ(p^m-1)/mを計算してみたい。p=2

m=2のとき、φ(3)/2=1

m=3のとき、φ(7)/3=2

m=4のとき、φ(15)/4

 φ(15)=φ(3)φ(5)=8よりφ(15)/4=2

m=5のとき、φ(31)/5=30/5=6

m=6のとき、φ(63)/6

 φ(63)=φ(7)φ(9)=36より

φ(36)/6=6

===================================

m|φ(p^m-1)

は任意のmに対して成り立つ、トーション関数の奇妙だが重要な性質である。

φ(2^16-1)/16=2048

===================================