# Factorization of polynomial with prime coefficients

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?
• if $f(x) = g(x)k(x)$ and $x^n-1 = g(x)l(x)$, you notice that you must achieve a leading term coefficient of $1$. Therefore the leading coefficient of $g$ and $l$ are both $1$ – Alvin Lepik Jul 18 '17 at 15:30
• @AlvinLepik As we know $x^n-1=(x-1)(x^{n-1}+ x^{n-2}+...+1)$ – Widawensen Jul 18 '17 at 15:34
• Indeed. Can for some $n$ the second term be reduced? If not then you have your unique representation of $x^n-1$ as a product of irreducible polynomials. – Alvin Lepik Jul 18 '17 at 15:38
• $x^3+x^2+x+1$, for instance can be further reduced. – Alvin Lepik Jul 18 '17 at 15:42
• All, I posted a follow-up question asking about the possibility of $f(x)$ having primitive $n$th roots of unity as roots. – Jyrki Lahtonen Jul 19 '17 at 11:26

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

• ok. Good example. Good rule. Why I was so blind? Probably for odd $n$ it could be also possible, but what would be the rule then ? – Widawensen Jul 19 '17 at 10:04
• @Widawensen For odd $n$ I would try to find three triples of primes with identical sums, and build a degree $9-1=8$ polynomial that has the third roots of unity as zeros, and thus a common factor with $x^9-1$. – Jyrki Lahtonen Jul 19 '17 at 10:08
• so the circlulant matrices built from primes can be singular.. I was hoping that not...thank you Jyrki and Gerry – Widawensen Jul 19 '17 at 10:10

For $n=4$, $x^4-1$ and $13+11x+17x^2+19x^3$ both have the root $x=-1$. Any number of similar examples can be produced.