Cyclotomic Polynomial

[2001.12.01]円分多項式

円分多項式を求めるプログラム(pari/gp)

■M\"obius関数
M\"obius関数μ(n)は、以下のように定義される。

μ(1)=1
μ(n)=0 if nが平方因子を持つとき
μ(p₁p₂・・・p_k)=(-1)^k if 素数p₁,p₂,...,p_kが互いに異なるとき

M\"ebius関数は、乗法的(multiplicative)である。つまり、(m,n)=1ならばμ(mn)=μ(m)μ(n)である。

■円分多項式(cyclotomic polynomial)
円分多項式Φ_n(x)は、以下のように定義される。
     Φ_n(x)=Π_d|n(x^n/d-1)^μ(d)

このとき、
     xⁿ-1=Π_d|nΦ_n(x)
である。また、素数pに対して、
     Φ_p(x)=x^p-1+x^p-2+...+x+1
     Φ_p^e(x)=x^t(p-1)+x^t(p-2)+...+x^t+1 ただし, t=p^e

円分多項式Φ_n(x)  (1≦n≦30)をpari/GPで求めてみると、以下のようになる。

n	Φ_n(x)
1	x-1
2	x+1
3	x²+x+1
4	x²+1
5	x⁴+x³+x²+x+1
6	x²-x+1
7	x⁶+x⁵+x⁴+x³+x²+x+1
8	x⁴+1
9	x⁶+x³+1
10	x⁴-x³+x²-x+1
11	x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
12	x⁴-x²+1
13	x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
14	x⁶-x⁵+x⁴-x³+x²-x+1
15	x⁸-x⁷+x⁵-x⁴+x³-x+1
16	x⁸+1
17	x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²+x¹¹+x¹⁰+x⁹ +x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
18	x⁶-x³+1
19	x¹⁸+x¹⁷+x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²+x¹¹+x¹⁰ +x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
20	x⁸-x⁶+x⁴-x²+1
21	x¹²-x¹¹+x⁹-x⁸+x⁶-x⁴+x³-x+1
22	x¹⁰-x⁹+x⁸-x⁷+x⁶-x⁵+x⁴-x³+x²-x+1
23	x²²+x²¹+x²⁰+x¹⁹+x¹⁸+x¹⁷+x¹⁶+x¹⁵+x¹⁴+x¹³+x¹² +x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
24	x⁸-x⁴+1
25	x²⁰+x¹⁵+x¹⁰+x⁵+1
26	x¹²-x¹¹+x¹⁰-x⁹+x⁸-x⁷+x⁶-x⁵+x⁴-x³+x²-x+1
27	x¹⁸+x⁹+1
28	x¹²-x¹⁰+x⁸-x⁶+x⁴-x²+1
29	x²⁸+x²⁷+x²⁶+x²⁵+x²⁴+x²³+x²²+x²¹+x²⁰+x¹⁹+x¹⁸+x¹⁷+x¹⁶+x¹⁵ +x¹⁴+x¹³+x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
30	x⁸+x⁷-x⁵-x⁴-x³+x+1

[参考文献]

[1]G.H.Hardy, E.M.Wright, "An Introduction to the Theory of Numbers 5th edition", Oxford University Press, p238-239, 1979, ISBN0-19-853171-0.
[2]山口周, "整数論 美しき円分体論・ベルヌーイ数への旅路", 産業図書, p162-163, 1994, ISBN4-7828-9013-3, {5871円}.
[3]Paulog Ribenboim, "The Little Book of Big Primes", Springer-Verlag, 1991, p136, ISBN0-367-97508-X.
[4]Richard Crandall, Carl Pomerance, "Prime Numbers A Computational Perspective", Springer-Verlag New York, Inc., 2001, p11, ISBN0-387-94777-9.

Last Update: 2005.06.12

H.Nakao

Cyclotomic Polynomial

[2001.12.01]円分多項式

円分多項式を求めるプログラム(pari/gp)

[参考文献]

[Homeに戻る] [一覧に戻る]