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?
  • $\begingroup$ 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$ $\endgroup$ – Alvin Lepik Jul 18 '17 at 15:30
  • $\begingroup$ @AlvinLepik As we know $x^n-1=(x-1)(x^{n-1}+ x^{n-2}+...+1)$ $\endgroup$ – Widawensen Jul 18 '17 at 15:34
  • $\begingroup$ 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. $\endgroup$ – Alvin Lepik Jul 18 '17 at 15:38
  • $\begingroup$ $x^3+x^2+x+1$, for instance can be further reduced. $\endgroup$ – Alvin Lepik Jul 18 '17 at 15:42
  • 1
    $\begingroup$ All, I posted a follow-up question asking about the possibility of $f(x)$ having primitive $n$th roots of unity as roots. $\endgroup$ – 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$.

  • $\begingroup$ 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 ? $\endgroup$ – Widawensen Jul 19 '17 at 10:04
  • $\begingroup$ @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$. $\endgroup$ – Jyrki Lahtonen Jul 19 '17 at 10:08
  • $\begingroup$ so the circlulant matrices built from primes can be singular.. I was hoping that not...thank you Jyrki and Gerry $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.