円分数の素因数分解

「円分多項式」 Φn(x) は、次の多項式によって、帰納的に定義される。
Φ1(x) = x - 1
x^m - 1 = Π Φn(x)
ここで Π は自然数 m の約数 n にわたっての積を表す。

n と x を自然数としたとき、円分多項式 Φn(X) の X = x における値 N = Φn(x) を「円分数」と言う。円分多項式 Φn(x) は、次数 φ(n) の既約多項式であるが、円分数 N はもちろん素数とは限らない。ここで、 φ(n) はオイラーの関数である。

我々の目標は、
φ(n) ≦ 100, 2 ≦ x ≦ 1000
なる自然数 n と x に対して、円分数 N = Φn(x) の素因数分解をすることである。

φ(n) ≦ 54, 2 ≦ x ≦ 1000
なるすべての円分数 Φn(x) の素因数分解は既に完成している。
次の段階は、φ(n) = 56 となる場合、すなわち
n = 87, 116, 174
の場合である。それぞれについて、円分多項式の具体的な形は次の通りである。
Φ87(X) = X^56 - X^55 + X^53 - X^52 + X^50 - X^49 + X^47 - X^46 + X^44 - X^43 + X^41 - X^40 + X^38 - X^37 + X^35 - X^34 + X^32 - X^31 + X^29 - X^28 + X^27 - X^25 + X^24 - X^22 + X^21 - X^19 + X^18 - X^16 + X^15 - X^13 + X^12 - X^10 + X^9 - X^7 + X^6 - X^4 + X^3 - X + 1
Φ116(X) = X^56 - X^54 + X^52 - X^50 + X^48 - X^46 + X^44 - X^42 + X^40 - X^38 + X^36 - X^34 + X^32 - X^30 + X^28 - X^26 + X^24 - X^22 + X^20 - X^18 + X^16 - X^14 + X^12 - X^10 + X^8 - X^6 + X^4 - X^2 + 1
Φ174(X) = X^56 + X^55 - X^53 - X^52 + X^50 + X^49 - X^47 - X^46 + X^44 + X^43 - X^41 - X^40 + X^38 + X^37 - X^35 - X^34 + X^32 + X^31 - X^29 - X^28 - X^27 + X^25 + X^24 - X^22 - X^21 + X^19 + X^18 - X^16 - X^15 + X^13 + X^12 - X^10 - X^9 + X^7 + X^6 - X^4 - X^3 + X + 1

素因数分解すべき最大の整数は 168 桁です。素因数分解の（不完全な）表のファイルを見るためには次をクリックしてください。何か新しい結果があれば連絡をお願いします。

φ(n) = 1 の場合の分解結果
φ(n) = 2 の場合の分解結果
φ(n) = 4 の場合の分解結果
φ(n) = 6 の場合の分解結果
φ(n) = 8 の場合の分解結果
φ(n) = 10 の場合の分解結果
φ(n) = 12 の場合の分解結果
φ(n) = 16 の場合の分解結果
φ(n) = 18 の場合の分解結果
φ(n) = 20 の場合の分解結果
φ(n) = 22 の場合の分解結果
φ(n) = 24 の場合の分解結果
φ(n) = 28 の場合の分解結果
φ(n) = 30 の場合の分解結果
φ(n) = 32 の場合の分解結果 complete 1998/08/31
φ(n) = 36 の場合の分解結果 complete 2001/02/23
φ(n) = 40 の場合の分解結果 complete 2002/01/13
φ(n) = 42 の場合の分解結果 complete 2002/07/24
φ(n) = 44 の場合の分解結果 complete 2003/04/27
φ(n) = 46 の場合の分解結果 complete 2003/08/13
φ(n) = 48 の場合の分解結果 complete 2005/11/15
φ(n) = 52 の場合の分解結果 complete 2007/02/27
φ(n) = 54 の場合の分解結果 complete 2007/02/17
φ(n) = 56 の場合の分解結果（未完成） last update 2009/04/01
φ(n) = 58 の場合の分解結果（未完成） last update 2008/11/17
φ(n) = 60 の場合の分解結果（未完成） last update 2009/03/02