■円分方程式の因数分解(その8)

n<105のとき、Φn(x)に現れる0以外の係数は±1だけであるが、

Φ105(x)には2か所に-2が現れる。ほかの係数が現れる最低次数のの円分多項式である。

その理由は105が3つの奇素数の積である最小の整数であるからである。

それとは直接関係ないと思われるが…

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

【1】百五減算

 p1,p2,p3が互いに素であるとき,p1で割って余りがr1,p2で割って余りがr2,p3で割って余りがr3になる自然数Aは一意に定まる.

しかし、3つともなると探すのに手間がかかる。しかし次のような巧妙な解法が知られている。

[Q]連立合同式

  x=1  (mod3)

  x=2  (mod5)

  x=3  (mod7)

xを105で割るといくつ余るか.

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

 p1で割って1余る数かつp2p3の倍数をx,p2で割って1余る数かつp3p1の倍数をy,p3で割って1余る数かつp1p2の倍数をzとするとき,特殊解

  A=xr1+yr2+zr3

が得られる.

 p1で割って1余る数かつp2p3の倍数をx=70

 p2で割って1余る数かつp3p1の倍数をy=21

 p3で割って1余る数かつp1p2の倍数をz=15

  A=xr1+yr2+zr3=70・1+21・2+15・3=157

  p1p2p3=105

  157−105=52

52が求める余りですが、この解法は最後に105を引くところから百五減算と呼ばれている。

もっとも最後の計算は105以下であれば引けないし、210以上であれば2回引かなくてはならない。

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

         70   21   15   70・1   21・2   15・3   A

3で割った余り   1    0    0      1      0      0   1

5で割った余り   0    1    0      0      2      0   2

7で割った余り   0    0    1      0      0      3   3

70,21,15がマジックナンバーになっていて、3,5,7で割った余りの条件を満たすような数を求めることができるのである。

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

【2】一般化

  x=ai  (modmi),(mi,mj)=1

に対して、M=Πmi、Mi=M/miと定義する。

このとき、NiMi=1  (modmi)となる解Niが存在して、

  x=ΣaiNiMi   (modM)

となる。

例:a1=3,a2=5→M=15,M1=5,M2=3

5N1=1 mod3→N1=2

3N2=1 mod5→N2=1

x=10a1+6a2 (mod15)

このとき、a1=2,a2=4ならばx=44=14 (mod15)

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