2.2 Φ[k]の素因数


☆主張☆
pを素数とする。xはK乗して初めて1(mod p)とする。次たちが成り立つ。
(1) Φ[k](x)はk=Kにおいて初めてpで割り切れる
(2) Φ[k](x)がpで割り切れるkの集合は、初項K,公比pの等比数列と一致する。
[略証]
(1): Φ[d](x)がpで割り切れるとするとx^d≡1であるからdはKの倍数である必要がある。
 またx^K-1=Φ[d](x)の積 [d:Kの約数] であるから、
 Kの約数の1つdでΦ[d](x)がpで割り切れる必要がある。以上から(1)が成り立つ。

(2): Φ[k](x)がpで割り切れるなら少なくともx^k≡1(mod p)が必要である。
 すなわちkはKの倍数であることが必要である。k=jKとおく。
 それに加えて、x^k-1はx^K-1よりもpで割り切れる回数が多い必要がある。
 なぜならΦ[jK](x)は(x^k-1)/(x^K-1)の因数であるから。
 1.2節で考察した、x が pqN+1 型 ⇔ x^p が pq+1N+1 型(ただしq≧1) を考えると、
 jがpの倍数であることが必要ということになる。
(十分性)
 x^K≡1なので、(x^Kp-1)/(x^p-1)=1+x^K+(x^K)^2+...+(x^K)^(p-1)≡1*p≡0(mod p)
 右辺=Φ[d](x)の積 [d:Kpの約数であるがKの約数ではない] なので、
 そのようなΦ[d](x)の中でpで割り切れるものが存在する。
 上記議論のようにdはKの倍数である必要があるからd=Kpだけが適である。
 すなわちΦ[pK]がpで割り切れることが示された。
(一般化へ)
 x^pKが pqN+1 型 とすると他のx^jK=pqN+1 型となるjKではΦ[jK]はpで割り切れない。
 なぜならjKはpKの倍数であり、Φ[jK](x)は(x^jK-1)/(x^pK-1)の因数であるから。
 次にΦ[jK]がpで割り切れるにはx^jK が pq+1N+1 型じゃないといけない。
 すなわちjがp^2の倍数であることが必要である。そして上記と同様にj=p^2で十分性も言える。
...その次はx^jK が pq+2N+1 型の必要があり、jがp^3の倍数である必要があり...
というような構造になっているわけである。

[整理]
xを固定した時のΦ[k](x)がpで割り切れるkの分布は、公比pの等比数列である。
しかも初項Kは(mod p)におけるxの位数である。
(よって下記のようにKはp-1の約数であるから、pと素である)

1.4節のまとめで述べたことように以下が成り立つ。
位数Kの剰余類xが存在する ⇔ Kはφ(p)=p-1の約数である
kを固定した時のΦ[k](x)がpで割り切れるxが存在するpの分布は、
kと素であるpに限ればk=KなのでNK+1型の素数の集合であることが分かる。

逆にkとpが上記の条件を満たす時、Φ[k](x)がpで割り切れるxが存在する。
それを満たすxはφ(k)個ある。つまりxの分布はx≡x[1],x[2],..,x[φ(k)] (mod p)

[φ(k)個あることについて、1.4節で述べたがもう一度理由を述べる]
pと素な剰余類xはすべて次の式を0にする。 x^(p-1)-1(=Φ[d]の積 [d:p-1の約数])
従って各xはp-1のある約数dについてΦ[d](x)≡0とならなければならない。
Φ[d]はφ(d)次式で合同式の理論(a.1節)から高々d個の解しかない。
φ(d)の和=n-1が成り立つから(1.0節)、フル活用してやっとp-1個のxをカバーできる。


 目次 inserted by FC2 system