14
$\begingroup$

Numerical evidence suggests the following.

For $c \in \mathbb{N}, c > 2$ define the sequence $a_n$ by $a_0=0,a_1=1, \; a_n=c a_{n-1} - a_{n-2}$

For $ 5 < n < 500, \; 2 < c < 100$ there are no primes in $a_n$ though semiprimes exist.

Is it true that $a_n$ is always composite for $n > 5$

If yes is there explicit partial factorization?

Searching OEIS solved the case $c=6$ with a Pell equation.

Counterexamples are welcome.

$\endgroup$

5 Answers 5

6
$\begingroup$

Here is another approach to show that $a_n$ is not prime when $c \gt 2$ and $n \gt 2$

We have (proof at end) $$a_{n+m}=a_na_{m+1}-a_{n-1}a_{m} \tag{*}$$ So, by induction on $j \ge 1$, $$a_{n+jn}=a_{n}a_{jn+1}-a_{n-1}a_{jn}$$ is always divisible by $a_n.$

Hence the only question is for $p \gt 2$ 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)$$

That is about enough. We should check that $a_{m+1}-a_{m} \gt 1$. In fact, in the case $c=2$, the sequence is $0,1,2,3,4,5,\cdots$ but for $c \gt 2$ we have $a_{n+1}-a_{n}$ increasing since $$a_{n+1}-a_n =(c-1)a_n-a_{n-1}=(c-2)a_n+(a_n-a_{n-1}).$$


To prove $(*)$, replace $m+n$ by $s$ and write $$a_s=a_{s-m}a_{m+1}-a_{s-m-1}a_{m}$$ where $m \lt s$ so

$\begin{align*} a_s &= a_{s-1}a_2-a_{s-2}a_1 \\ &= a_{s-2}a_3-a_{s-3}a_2 \\ &=a_{s-3}a_4-a_{s-4}a_3 \\ &=\cdots. \end{align*}$

The first line is jut the defining recurrence relation $a_s=a_{s-1}c-a_{s-2}1$ and then the difference between successive lines is $$\left(a_{s-m}a_{m+1}-a_{s-m-1}a_{m}\right)-\left(a_{s-m-1}a_{m+2}-a_{s-m-2}a_{m+1}\right)$$ $$=\left(a_{s-m}+a_{s-m-2}\right)a_{m+1}-a_{s-m-1}\left(a_{m+2}+a_m \right)$$ $$=\left(ca_{s-m-1}\right)a_{m+1}-a_{s-m-1}\left(ca_{m+1} \right)=0$$


Observe that putting $c=i$ yields Fibonacci numbers times powers of $i$: $$0,1,i,-2,-3i,5,8i,-13,\cdots $$

This suggests that the divisibility result above (considering the $a_n$ as monic polynomials in variable $c$) can be sharpened to $$\gcd(a_n,a_m)=a_{\gcd(n,m)} $$ The usual proof applies mutatis mutandis.

This means that for any chosen integer value of $c$ the same fact holds, if $p$ is prime and $k=m$ is the least positive index with $p \mid a_k$ then $p \mid a_n$ exactly when $m \mid n$.

$\endgroup$
1
  • $\begingroup$ Interesting, thank you. I knew about c=1,2 but didn't know about $c=i$. $\endgroup$
    – joro
    Oct 29, 2013 at 6:34
21
$\begingroup$

Put $u = (c + \sqrt{c^2-4})/2$. We have

$$a_{2n} = \frac{u^{2n}-u^{-2n}}{u-u^{-1}} = \left( \frac{ u^n-u^{-n}}{u-u^{-1}} \right) \left( \vphantom{\frac{ u^n-u^{-n}}{u-u^{-1}}} u^n + u^{-n} \right)$$

$$a_{2n+1} = \frac{u^{2n+1}-u^{-2n-1}}{u-u^{-1}} = \left( \frac{u^{n+1/2}-u^{-2n-1}}{u^{1/2}-u^{-1/2}} \right) \left( \frac{u^{n+1/2}+u^{-n-1/2}}{u^{1/2}+u^{-1/2}} \right) =$$ $$\left( \frac{u^{n+1/2}-u^{-n-1/2}}{u^{1/2}-u^{-1/2}} \right) \left( \frac{u^{n+1/2}+u^{-n-1/2}}{u^{1/2}+u^{-1/2}} \right)=\left( \frac{u^{n+1}-u^{-n}}{u-1} \right) \left( \frac{u^{n+1}+u^{-n}}{u+1} \right).$$

Put $v_{n} = u^n + u^{-n}$, $x_{n} = \frac{u^{n+1}-u^{-n}}{u-1} $, $y_{n}=\frac{u^{n+1}+u^{-n}}{u+1} $ so $a_{2n} = a_n v_n$ and $a_{2n+1} = x_n y_n$. I claim that each of $v$, $x$ and $y$ are integer valued sequences which are greater than $1$ for $n \geq 2$, thus proving the claim.

The fastest way to see this is to note the recursions: $$v_n = c v_{n-1} - v_{n-2} \quad v_0=2 \quad v_1 =c $$ $$x_n = c x_{n-1} - x_{n-2} \quad x_0=1 \quad x_1 =c+1 $$ $$y_n = c y_{n-1} - y_{n-2} \quad y_0=1 \quad y_1 =c-1 $$

A more conceptual way to see the rationality is to note that the Galois symmetry $\sqrt{c^2-4} \mapsto - \sqrt{c^2-4}$ takes $u$ to $u^{-1}$ and takes each of $v_n$, $x_n$ and $y_n$ to themselves.

$\endgroup$
0
12
$\begingroup$

For even $n$ it follows by induction that $a_n$ is divisible by $c$. Also, $a_n>c$ for $n\ge3$, so $a_n$ is not a prime.

For odd $n=2m+1$, one can do the following: Consider $c$ as an indeterminate. Then $a_n=P_n(c)$, where $P_n(X)\in\mathbb Z[X]$ (by binomially expanding Paolo's answer). One can show that there is a polynomial $h_m(X)\in\mathbb Z[X]$ of degree $m$ such that $P_n(X)=(-1)^mh_m(-X)h_m(X)$.

An explicit expression of $h_m$ is \begin{equation} h_m(X)=\prod_{k=1}^m(X-\zeta^k-\frac{1}{\zeta^k}), \end{equation} where $\zeta$ is a primitive $n$-th root of unity.

Now if $\lvert\gamma\rvert\ge3$, then each factor of $h_m(\gamma)$ has absolute value $\gt1$, so $h_m(\pm c)\ne\pm1$.

Thus $a_n$ is never a prime for $n\ge3$ and $c\ge 3$.

$\endgroup$
3
  • $\begingroup$ Thanks I see. This answers the second part of the question :-) $\endgroup$
    – joro
    Oct 28, 2013 at 14:58
  • $\begingroup$ Have you tried to squeeze more factors for $n$ prime? Over $\mathbb{Q}[\zeta_n]$ you have a lot of factors of $h_m(X)$. Can for certain $c$ substituting $X=c$ and computing the gcd of the norm of the factors and $a_n$ produce more factors of $a_n$? Experimentally this doesn't work for me, not sure. $\endgroup$
    – joro
    Oct 29, 2013 at 10:26
  • $\begingroup$ @joro: No, generically there are no more factors, because the polynomials $h_m(X)$ are irreducible over the rationals. See the question/answer at mathoverflow.net/questions/146251/…. $\endgroup$ Oct 29, 2013 at 10:32
3
$\begingroup$

Just to start with: $$a_n=\frac{1}{\sqrt{c^2-4}}\left(\frac{c+\sqrt{c^2-4}}{2}\right)^n-\frac{1}{\sqrt{c^2-4}}\left(\frac{c-\sqrt{c^2-4}}{2}\right)^n$$

$\endgroup$
2
$\begingroup$

Your $a_n$ is a divisibility sequence, right? That means $a_n \mid a_{mn}$, so to get prime values, you'll pretty much need the index to be prime. Next, note that $a_n$ is approximately $c^n$. So the probability that $a_p$ is prime is approximately $1/p\log(c)$. Hence in the range you've checked, it's not so surprising that you didn't find any primes. This probabilistic model suggests that there are likely to be infinitely many primes in each sequence, i.e., for each $c>2$. But proving this is likely beyond our capabilities, just as we can't currently prove that there are infinitely many Mersenne primes.

$\endgroup$
2
  • $\begingroup$ Thanks. The example $c=6$ and OEIS certainly contradict your heuristic. $\endgroup$
    – joro
    Oct 28, 2013 at 13:59
  • 1
    $\begingroup$ Okay, what I should have said is except when there are obvious divisors. So for example, it's conjectured that $2^p-1$ is prime infinitely often. But clearly $3^p-1$ is not, since it's even! But it is conjectured that $(3^p-1)/2$ is prime infinitely often. There's a whole literature on this sort of stuff. (Hmmm... Maybe I should edit my answer; or is it enough to leave the correction as a comment?) $\endgroup$ Oct 28, 2013 at 17:14

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.