<s>[INST] Factorization of polynomial with prime coefficients I'm interested in the problem linked with   this answer.  
Let  $ f(x) = a_n + a_1 x + \dots + a_{n-1} x^{n-1}  $ be polynomial with distinct $a_i$ which are  primes.    
(Polynomials like that  for $n= 4 \ \ \ \ f(x) = 7 + 11 x + 17 x^2 + 19 x^3   $)


*

*Is it for some $n$  possible that  $x^n-1$ and $f(x)$ have some common divisors?


(Negative answer would mean that it is possible to generate circulant non-singular matrices  with any prime numbers)
In other words    


*

*$x^n-1$ has roots which lie (as complex vectors) symmetrically in complex plane on the
unit circle, can such root be also a root of  $f(x) = a_n + a_1 x +
   \dots + a_{n-1} x^{n-1}$ in general case where $a_i$ are constrained
as above? 

 [/INST] This is certainly possible. The easiest way is to use pairs of twin primes and $n=4$. Such as
$$
f(x)=7+5x+11x^2+13x^3
$$
where $f(-1)=0$ and $x+1$ is a common factor of $f(x)$ and $x^4-1.$

Extending the same idea to third roots of unity. Consider
$$
f(x)=7+5x+17x^2+29x^3+31x^4+19x^5.
$$
Because $7+29=5+31=17+19=36$ we easily see that the third roots of unity $\omega=e^{\pm 2\pi i/3}$ are zeros of $f(x)$ as $f(\omega)=36(1+\omega+\omega^2)=0$. Therefore $f(x)$ has a common factor $\Phi_3(x)=x^2+x+1$ with $x^3-1$ and therefore also with $x^6-1$.

For an example of an odd $n$ I found the following. As
$$53=3+13+37=5+17+31=11+19+23$$ is the sum of three disjoint triples of primes, we can, as above, show that 
$$
f(x)=3+5x+11x^2+13x^3+17x^4+19x^5+37x^6+31x^7+23x^8
$$
has the common factor $x^2+x+1$ with $x^9-1$.
</s>