View Single Post
Old 2020-11-13, 18:44   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

Quote:
Originally Posted by axn View Post
x^n+/-1 has trivial algebraic factors. So he was suggesting to look at the nth cyclotomic polynomial instead - i.e. what is left after removing the algebraic factors.
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].

Last fiddled with by R. Gerbicz on 2020-11-13 at 18:46 Reason: grammar
R. Gerbicz is offline   Reply With Quote