View Single Post
Old 2020-11-14, 13:58   #10
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

26·71 Posts

Originally Posted by R. Gerbicz View Post
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:
? 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).
Dr Sardonicus is offline   Reply With Quote