Thread: x!^n+/-1 or x#^n+/-1? View Single Post
2020-11-14, 13:58   #10
Dr Sardonicus

Feb 2017
Nowhere

2×7×11×29 Posts

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).