■約数関数のおおまかな上界と下界(その33)

結局

p^m-1=p1^α1・p2^α2・・・pk^αk  (p1<p2<・・・<pk)

φ(p^m-1)=Πpi^αi-1・(pi-1)

pi=Nm+1

となるものがあることを示せればよいのだが・・・。

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

[1]pを素数,qをp^m-1の素因数とする

 p^m=1  (modq)ならば,q=1  (modm)である

 q=1  (modm)ならば、p^m=1  (modq)である。

を証明すればよい。

位数の法則

modpでのaの位数をeとする。このとき

a^n=1(modp)ならば、nはeの倍数。とくにp-1はeの倍数

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

素数qをp^m-1の約数とすると

p^m=1 (modq)

modqにおけるpの位数をeとおくと、位数の法則よりeの可能性はmの約数に限られる。

eをkと仮定するとp^e=1 (modq)より

p^e+1=p、p^e+2=p^2、・・・p^m=p^e+m、となって、 p^m=1 (modq)に反する。

よって、e=m.

位数の法則よりe=mはq−1の約数。q=1(modm)

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