This question is inspired by a recent one : Let $c$ be a variable and define a sequence by $a_0=0$ $a_1=1$ and $a_{n+1}=a_{n}c-a_{n-1}$ . So

$$\begin{align*} a_2 &= c \\ a_3 &={c}^{2}-1= \left( c-1 \right) \left( c+1 \right) \\ a_4 &= {c}^{3}-2\,c=c \left( {c}^{2}-2 \right) \\ a_5 &={c}^{4}-3\,{c}^{2}+1 = \left( {c}^{2}+c-1 \right) \left( {c}^{2}-c-1 \right) \\ a_6 &={c}^{5}-4\,{c}^{3}+3\,c= c \left( c-1 \right) \left( c+1 \right) \left( {c}^{2}-3 \right) \\ a_7 &={c}^{6}-5\,{c}^{4}+6\,{c}^{2}-1= \left( {c}^{3}-{c}^{2}-2\,c+1 \right) \left( {c}^{3}+{c}^{2}-2\,c-1 \right) \end{align*}$$

Note that $$a_{n+1}=\sum_{j=0}^t (-1)^j\binom{n-j}{j}c^{n-2j}$$ where $t=\lfloor\frac{n}{2}\rfloor.$ So the array of coefficients is just Pascal's triangle shifted with alternating signs. Not that I see a connection to the questions below.

The defining recurrence $a_{n+1}=a_{n}c-a_{n-1}$ i.e. $$a_{n+1}=a_{n}a_{2}-a_{n-1}a_1$$ is the first non-trivial case (and base for an induction proof of) of the more general $$a_{n+m}=a_{n}a_{m+1}-a_{n-1}a_{m}. \tag{$\ast$}$$

From this is follows that $$\gcd(a_n,a_m)=a_{\gcd(n,m)} \tag{$\ast \ast$}$$ so the polynomial $a_n$ factors unless, possibly, $n$ is prime. But for any odd index $2m+1$ we have $$a_{(m+1)+m}=a_{m+1}^2-a_{m}^2=(a_{m+1}+a_m)(a_{m+1}-a_m)$$

Q: If $p=2m+1$ is prime, must the monic polynomials $s_p=a_{m+1}+a_m$ and $d_p=a_{m+1}-a_m$ be irreducible in $\mathbb{Z}[c]$?

random remarks

This is the case up to $p=199$ (according to Maple) so it seems likely.

Replacing $c$ by $-c$ changes $s_p$ into $\pm d_p$ so either both are irreducible or both factor (in the same way).


A heuristic argument (which should perhaps not be trusted) is as follows: For a fixed integer value $c \ge 2$ the $a_n$ become integers but $(\ast)$ and $(\ast \ast)$ remain true (now as statements in $\mathbb{Z}$) so if a prime $q$ divides $a_k$ for the first time at $k=n$ then it divides $a_k$ exactly when $n \mid k$. Accordingly, when $p=2m+1$ is prime, we have the factorization $a_p=s_p \cdot d_p$ where the two factors are co-prime and any prime $q$ which divides either of them (and hence $a_p$) does not divide $a_k$ for any $k \lt p$. Of course for a given $c$ one or both of $s_p,d_p$ might be composite, but it seems likely (weak!) that each (or even just one or the other) is prime for some value of $c$ and that would require both to be irreducible as polynomials.

When $c$ is set to $c=2$ we have $a_k=k$ so $d_p=a_{m+1}-a_m=1$ and $s_p=a_{m+1}+a_m=2m+1$ is prime when $p$ is. This makes it seem somewhat more likely that the polynomial $s_p$ is irreducible, however there could be factors of the form $(c-2)f(c)+1.$

  • $\begingroup$ See comments in oeis.org/A115139 $\endgroup$
    – rwst
    Oct 29, 2013 at 9:28
  • $\begingroup$ I was thinking about factoring over $Z[\zeta_n]$ (as in Peter's answer) which gives a lot of factors then computing the gcd of the norm and $a_n$ in hope to find more factors, but according to Peter this won't work... $\endgroup$
    – joro
    Oct 29, 2013 at 10:58
  • $\begingroup$ Is $c$ an integer? If it is not they might be reducible over Z[c]... $\endgroup$
    – joro
    Oct 29, 2013 at 11:01
  • $\begingroup$ @joro: The question says that $c$ is a variable. $\endgroup$ Oct 29, 2013 at 11:03

2 Answers 2


The polynomials $s_p$ and $d_p$ are indeed irreducible: We have $a_p(c)=s_p(c)d_p(c)$ with $s_p$ and $d_p$ monic of degree $m=(p-1)/2$. Let $z$ be another variable. Then $z^{2m}a_p(z+1/z)=(z^ms_p(z+1/z))(z^md_p(z+1/z))$. The two factors on the right hand side are monic polynomials, and if we show that they are irreducible, then $s_p(x)$ and $d_p(c)$ are irreducible even more.

Using the explicit expression of $a_p(c)$ from Paolo's answer to this related question shows that \begin{equation} z^{2m}a_p(z+1/z)=(1+z+\dots+z^{p-2}+z^{p-1})(1-z+\dots-z^{p-2}+z^{p-1})=\Phi(z)\Phi(-z), \end{equation} where $\Phi(z)$ is the $p$-th cyclotomic polynomial. But $\Phi(z)$ is well known to be irreducible, and the claim follows.


With the substitution $c=x+2$, Eisentstein's criterion can be used. Then the first few polynomials $a_{m}+a_{m+1}$ become

$$\begin{align*} a_0+a_1&=1 \\a_1+a_2&=3+x \\ a_2+a_3&=5+5x+x^2\\a_3+a_4&=7+14x+7x^2+x^3\\a_4+a_5&=9+30x+27x^2+9x^3+x^4\\a_5+a_6&=11+55x+77x^2+44x^3+11x^4+x^5 \end{align*}$$

Evidently,when $p=2m+1$ is prime, the monic polynomial $$a_{m}+a_{m+1}=\left(\sum_{j=0}^{2m}b_jx^j\right)+x^{2m+1}$$ is such that all the coeffcients $b_i$ are multiples of $p$ including $b_0=p.$ If true (which it is), this is exactly what is needed to prove irreducibility.

It turns out (eventually) that $$ \begin{align*} b_0&=(2m+1)\\b_1&=(2m+1)\frac{m(m+1)}{3!}\\b_2&=(2m+1)\frac{m(m+1)(m+2)(m+3)}{5!}\end{align*}$$ and in general $$b_i=b_i(m)=\frac{2m+1}{2i+1}\binom{m+i}{2i}.$$

It may not be obvious that these are integers, but they are, and hence, as claimed, $b_i(m)$ is divisible by $p=2m+1$ when that number is prime.

After the fact, an easier description of the coefficients is as follows:

The odd integers give the constant terms $b_0(m)$

$[1,3,5,7,9,11,13,\cdots]$ whose partial sums are the squares

$[1,4,9,16,25,36,49,\cdots]$ whose partial sums (with a shift) are the $b_1(m)$

$[0,1,5,14,30,55,91,140,\cdots]$ and their partial sums are

$[0,1,6,20,50,105,196,236,\cdots]$ and their partial sums (with a shift) are the $b_2(m)$

$[0,0,1,7,27,77,182,378,714,\cdots]$ whose partial sums

$[0,0,1,8,35,\cdots]$ have as partial sums the $b_3(m)$

$[0,0,0,1,9,44,\cdots]$ etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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