Quote:
Originally Posted by R. Gerbicz
Exactly. There is a not hard pattern for these factors: if additionally you remove all lower exponents factors then for the remaining p prime factors what divides polcyclo(n,x) we have p%n=1. You really need to do this, because for example:
Code:
? factor(polcyclo(20,2))
%24 =
[ 5 1]
[41 1]
Ofcourse after the sieve with these special primes you need to do only a few gcd's on the remaining candidates. [or start the sieve removing these].

Right, the factor 5 in the above is sometimes called an "intrinsic" prime factor. It shows up because 5 divides polcyclo(4,2). An additional factor of 5 shows up in polcyclo(4*5, 2); another in polcyclo(4*5^2, 2), another in polcyclo(4*5^3, 2) and so on. This is described in detail in
The Cyclotomic Polynomials.
There is at most one "intrinsic" prime factor. Let P be the evaluation of the cyclotomic polynomial, and n the exponent. If P has an intrinsic prime factor, it is gcd(P,n).