# A partition in three classes of the set of all prime numbers?

This is a continuation (and kind of simplification) of this question.

Let the integer sequences $(r_n)$, $(s_n)$ and $(t_n)$, ($n \ge 0$) be defined by the same second order linear recurrence, but with slightly different initial conditions: $$r_n=4r_{n-1}-r_{n-2}\ \ \text{ with} \ r_0 =1, \ r_1=2$$ $$s_n=4s_{n-1}-s_{n-2}\ \ \text{ with} \ s_0 =1, \ s_1=5$$ $$t_n=4t_{n-1}-t_{n-2}\ \ \text{ with} \ t_0 =1, \ t_1=3$$ These are the sequences A001075, A001834 and A001835 (shifted), respectively.

Let $\mathbb{R}$ (respectively $\mathbb{S}$ and $\mathbb{T}$) be the set of the prime divisors of the members of the sequence $(r_n)$ (respectively $(s_n)$ and $(t_n)$). $$\mathbb{R}=\{2,7,13,31,37,61,73,79,97,103,109,127,151,157,181,193,199,223,229,271,…\}$$ $$\mathbb{S}=\{5,19,23,29,43,47,53,71,101,149,163,167,173,191,197,239,263,269,...\}$$ $$\mathbb{T}=\{3,11,17,41,59,67,83,89,107,113,131,137,139,179,211,227,233,241,251,257,…\}$$

Is it true that $\mathbb{R}$, $\mathbb{S}$ and $\mathbb{T}$ make a partition in three classes of the set of all prime numbers?

Edit: Thanks to the observation of @Yong Hao Ng that no known member of $\mathbb {R}$ is $19 \pmod {24}$, and given the known fact that the density of the primes which are in $\mathbb {S}$ (resp. in $\mathbb {T}$) is $\frac{1}{3}$, [Lagarias, J.C., The set of primes dividing the Lucas numbers has density 2/3, Pac. J. Math. 118, 449-461 (1985). ZBL0569.10003.], we venture the following conjectural table about the density of the primes in a given residue class modulo $24$ in $\mathbb {R}$ (resp. in $\mathbb {S}$, in $\mathbb {T}$): \begin{matrix} &|&1&5&7&11&13&17&19&23\\ -&&---&---&---&---&---&---&---&---\\ \mathbb{T}&|&\frac{1}{48} & &&\frac{1}{8}&&\frac{1}{8}&\frac{1}{16}&\\ \mathbb{S}&|&\frac{1}{48} & \frac{1}{8}&&&&&\frac{1}{16}&\frac{1}{8}\\ \mathbb{R}&|&\frac{1}{12} && \frac{1}{8}&&\frac{1}{8}&&&&\\ \end{matrix}

The sum of each row is $\frac{1}{3}$ and the sum of each column is $\frac{1}{8}$, as expected since $\phi(24)=8$.

Edit (14/03/18): actually I just found a paper relevant to this question:

Ballot, Christian & Elia, Michele. (2007). Rank and period of primes in the Fibonacci sequence. A trichotomy. The Fibonacci Quarterly. 45.

explaining in a very general way, when and why these kind of sequences obtained from second order linear recurrences can produce a trichotomy of the prime numbers. This is quite complicated, but in our particular case, we can conclude more simply since Yong Hao Ng already proved the coprimality. The argument is as follows: Introduce
$$u_n=4u_{n-1}-u_{n-2}\ \ \text{ with} \ u_0 =0, \ u_{1}=1$$ $(u_n)$ is a Lucas sequence of Fibonacci type and therefore for every odd prime $p$, $p$ divides $u_{p-(12|p)}$; i.e. for all $p$ there exists some index $n$ for which $p$ divides $u_n$. $12$ is the discriminant of the characteristic polynomial associated with the linear recurrence and $(12|p)=-1,0$ or $1$ is the quadratic character of $12$ modulo $p$ (Legendre symbol). On the other hand, it is not too difficult to see that \begin{align*} u_{2n+1}&=s_nt_n\\ u_{2n}&=2r_nu_{n} \end{align*} therefore any $p$ must divide some member of one the three sequences $(r_n), (s_n)$ or $(t_n)$.

• I would have used $\mathcal{R}, \mathcal{S}, \mathcal{T}$ instead of $\mathbb{R}, \mathbb{S}, \mathbb{T}$. Hope no one downvotes you for such a petty detail. – Mr. Brooks Feb 21 '18 at 22:13
• One could start with finding the direct formulae for these recursions. They are all of the form $$A\left(\frac{4+\sqrt{12}}2\right)^n+B\left(\frac{4-\sqrt{12}}2\right)^n$$ for some constants $A$ and $B$. – Mastrem Feb 22 '18 at 8:28
• The direct formulae are: $$r_n=\frac12\left(\frac{4+\sqrt{12}}2\right)^n+\frac12\left(\frac{4-\sqrt{12}}2\right)^n$$ $$s_n=\frac{6\sqrt{12}+12}{24}\cdot\left(\frac{4+\sqrt{12}}2\right)^n+\frac{-6\sqrt{12}+12}{24}\cdot\left(\frac{4-\sqrt{12}}2\right)^n$$ $$t_n=\frac{2\sqrt{12}+12}{24}\cdot\left(\frac{4+\sqrt{12}}2\right)^n+\frac{-2\sqrt{12}+12}{24}\cdot\left(\frac{4-\sqrt{12}}2\right)^n$$ – Mastrem Feb 22 '18 at 8:44

It can be shown that $(r_n),(s_n),(t_n)$ are coprime, so primes occurring in one cannot occur in another. However I am not so sure if all the primes will occur. Looking at quadratic reciprocity, we can see that \begin{align*} \mathbb R&: p\equiv 7,13,1,19 \pmod{24}\\ \mathbb S&: p\equiv 5,23,1,19 \pmod{24}\\ \mathbb T&: p\equiv 11,17,1,19 \pmod{24} \end{align*} Edit 1: see appendix B
So at least it does cover all classes $\pmod{24}$. This method is a lot shorter, but unfortunately there is overlap so it cannot partition the primes on it own.

0. Outline of proof
We want to show that primes occuring in $(s_n)$ does not appear in $(r_n)$ or $(t_n)$, hence a direct way is to show that $$\gcd(r_i,s_j)=\gcd(t_i,s_j)=1$$ for all $i,j\geq 0$. (Similarly checking $\gcd(r_i,t_j)=1$.)

To do this, we prove a set of 6 equalities for all $n,k\geq 0$: \begin{align*} \gcd(r_{n+1+k},s_n) &= \gcd(t_k,s_n)\\ \gcd(r_n,s_{n+k}) &= \gcd(r_n,t_k)\\ \gcd(t_{n+k},s_n) &= \gcd(r_k,s_n)\\ \gcd(t_n,s_{n+k}) &= \gcd(t_n,r_k)\\ \gcd(t_{n+k},r_n) &= \gcd(s_k,r_n)\\ \gcd(t_n,r_{n+1+k}) &= \gcd(t_n,s_k) \end{align*} (Notice that the indices are not balanced, which happens for $r$ with the higher index.)

Observe that upon repeated application the indices are strictly decreasing. This does not cover $\gcd(r_n,s_n)$ and $\gcd(t_n,r_n)$, but the proof will cover it along the way.

Hence given a starting $\gcd(r_i,s_j)$ or $\gcd(t_i,s_j)$, we can reduce it to a $\gcd(r_l,s_m)$ or $\gcd(t_l,s_m)$ for some small $l,m$, say $0\leq l,m\leq 2$. These can all be shown to be equal to $1$, hence $(s_n)$ is coprime to $(r_n)$ and $(t_n)$. (Similarly $(r_n)$ coprime to $(t_n)$.)

1. Linear relation between the sequences.
The update formula are of the forms \begin{align*} \begin{bmatrix} 1 & 1\\ 2 & 3 \end{bmatrix} \begin{bmatrix} r_n\\ s_n \end{bmatrix} = \begin{bmatrix} r_{n+1}\\ s_{n+1} \end{bmatrix}, \begin{bmatrix} 2 & 1\\ 3 & 2 \end{bmatrix} \begin{bmatrix} t_n\\ s_n \end{bmatrix} = \begin{bmatrix} t_{n+1}\\ s_{n+1} \end{bmatrix}, \begin{bmatrix} 5 & -2\\ 3 & -1 \end{bmatrix} \begin{bmatrix} t_n\\ r_n \end{bmatrix} = \begin{bmatrix} t_{n+1}\\ r_{n+1} \end{bmatrix} \end{align*}

This can be shown as follows: \begin{align*} r_{n+1} &= r_n + s_n = r_n + 2r_{n-1}+3s_{n-1} = r_k + 2r_{n-1} + 3(r_n-r_{n-1}) = 4r_n-r_{n-1}\\ s_{n+1} &= 2r_n+3s_n = 2(r_{n-1}+s_{n-1})+3s_n= (s_n-3s_{n-1})+2s_{n-1}+3s_n=4s_n-s_{n-1}\\ t_{n+1} &= 2t_n+s_n = 2t_n+3t_{n-1}+2s_{n-1}=2t_n+3t_{n-1}+2(t_n-2t_{n-1})=4t_n-t_{n-1}\\ s_{n+1} &= 3t_n+2s_n=3(2t_{n-1}+s_{n-1})+2s_n=2(s_n-2s_{n-1})+3s_{n-1}+2s_n=4s_n-s_{n-1}\\ t_{n+1} &= 5t_n-2r_n = 5t_n-2(3t_{n-1}-r_{n-1})=5t_n-6t_{n-1}-(t_n-5t_{n-1})=4t_n-t_{n-1}\\ r_{n+1} &= 3t_n-r_n=3(5t_{n-1}-2r_{n-1})-r_n = 5(r_n+r_{n-1})-6r_{n-1}-r_n=4r_n-r_{n-1} \end{align*}

2. Showing that $r_n,s_n,t_n$ are pairwise coprime
Since $\gcd(r_1,s_1)=\gcd(t_1,s_1)=\gcd(r_1,t_1)=1$, we can find $u_1,v_1,w_1,z_1,f_1,g_1$ such that \begin{align*} u_1r_1 + v_1s_1 &= 1\\ w_zt_1 + z_1s_1 &= 1\\ f_1t_1 + g_1r_1 &= 1 \end{align*} We can write this in matrix form: \begin{align*} \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} = 1, \begin{bmatrix} w_1 & z_1 \end{bmatrix} \begin{bmatrix} t_1\\ s_1 \end{bmatrix} = 1 , \begin{bmatrix} f_1 & g_1 \end{bmatrix} \begin{bmatrix} t_1\\ r_1 \end{bmatrix} = 1 \end{align*} Since the update matrices are invertible, more generally we have \begin{align*} 1= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} &= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} 3 & -1\\ -2 & 1 \end{bmatrix}^{n-1} \begin{bmatrix} 1 & 1\\ 2 & 3 \end{bmatrix}^{n-1} \begin{bmatrix} r_1\\ s_1 \end{bmatrix}\\ &= \begin{bmatrix} u_n & v_n \end{bmatrix} \begin{bmatrix} r_n\\ s_n \end{bmatrix}\\ 1 &= u_nr_n + v_ns_n \end{align*} So $\gcd(r_n,s_n)=1$ for all $n$. Similarly, $\gcd(t_n,s_n)=\gcd(r_n,t_n)=1$ since \begin{align*} 1= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} &= \begin{bmatrix} w_1 & z_1 \end{bmatrix} \begin{bmatrix} 2 & -1\\ -3 & 2 \end{bmatrix}^{n-1} \begin{bmatrix} 2 & 1\\ 3 & 2 \end{bmatrix}^{n-1} \begin{bmatrix} t_1\\ s_1 \end{bmatrix}\\ 1 &= w_nt_n + z_ns_n\\ 1= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} &= \begin{bmatrix} f_1 & g_1 \end{bmatrix} \begin{bmatrix} -1 & 2\\ -3 & 5 \end{bmatrix}^{n-1} \begin{bmatrix} 5 & -2\\ 3 & -1 \end{bmatrix}^{n-1} \begin{bmatrix} t_1\\ r_1 \end{bmatrix}\\ 1 &= f_nt_n + g_nr_n \end{align*} In particular this covers the cases $\gcd(r_n,s_n)=\gcd(t_n,r_n)=1$, as mentioned in [0].

3. Showing the descent equalities
Instead of computing $\gcd(a,b)$ directly, we use the fact that $$\gcd(a,b) = \gcd(a\pmod b,b)$$ to reduce $a$ to something smaller.

Using $u_nr_n+v_ns_n=1$, we have \begin{align*} u_nr_n &\equiv 1 \pmod{s_n}\\ u_nr_{n+1} &= u_n(r_n+s_n) \equiv 1 \equiv t_0 \pmod{s_n}\\ u_nr_{n+1+1} &= u_n(4r_{n+1}-r_n) \equiv 4\cdot 1 -1 \equiv t_1 \pmod{s_n}\\ u_nr_{n+1+k} &= u_n(4r_{n+k}-r_{n+k-1}) \equiv 4t_{k-1}-t_k\equiv t_k \pmod{s_n} \end{align*} Therefore, using $\gcd(u_n,s_n)=1$, \begin{align*} \gcd(r_{n+1+k},s_n) &= \gcd(u_nr_{n+1+k},s_n)\\ &= \gcd(u_nr_{n+1+k}\pmod{s_n},s_n)\\ &= \gcd(t_k,s_n) \end{align*} showing the first of the six equality. The rest of the five are similar, which completes the proof. (They are listed in the next section for completeness, with the last one being a little different.)

A. Misc. computations
\begin{align*} v_ns_n &\equiv 1 \equiv t_0 \pmod{r_n}\\ v_ns_{n+1} &= v_n(2r_n+3s+n) \equiv 3 \equiv t_1 \pmod{r_n}\\ v_ns_{n+k} &= v_n(4s_{n+k-1}+s_{n+k-2}) \equiv 4t_{k-1}-t_{k-2}\equiv t_k \pmod{r_n}\\ \gcd(r_n,s_{n+k}) &= \gcd(r_n,v_ns_{n+k})\\ &= \gcd(r_n,v_ns_{n+k}\pmod{r_n})\\ &= \gcd(r_n,t_k)\\ w_nt_n &\equiv 1 \equiv r_0 \pmod{s_n}\\ w_nt_{n+1} &=w_n(2t_n+s_n)\equiv 2\equiv r_1 \pmod{s_n}\\ w_nt_{n+k} &= w_n(4t_{n+k-1}-t_{n+k-2}) \equiv 4r_{k-1}-r_{k-2}\equiv r_k \pmod{s_n}\\ \gcd(t_{n+k},s_n) &=\gcd(w_nt_{n+k},s_n)\\ &= \gcd(w_nt_{n+k}\pmod{s_n},s_n)\\ &= \gcd(r_k,s_n)\\ z_ns_n &\equiv 1 \equiv r_0 \pmod{t_n}\\ z_ns_{n+1} &= z_n(3t_n+2s_n) \equiv 2 \equiv r_1 \pmod{t_n}\\ z_ns_{n+k} &= z_n(4s_{n+k-1}-s_{n+k-2}) \equiv 4r_{k-1}-r_{k-2} \equiv r_k\pmod{t_n}\\ \gcd(t_n,s_{n+k}) &= \gcd(t_n,z_ns_{n+k})\\ &= \gcd(t_n,z_ns_{n+k}\pmod{t_n})\\ &= \gcd(t_n,r_k)\\ f_nt_n &\equiv 1 \equiv s_0\pmod{r_n}\\ f_nt_{n+1} &= f_n(5t_n-2r_n)\equiv 5 \equiv s_1\pmod{r_n}\\ f_nt_{n+k} &= f_n(4t_{n+k-1}-t_{n+k-2}) \equiv 4s_{k-1}-s_{k-2}\equiv s_k \pmod{r_n}\\ \gcd(t_{n+k},r_n) &= \gcd(f_nt_{n+k},r_n)\\ &= \gcd(f_nt_{n+k}\pmod{r_n},r_n)\\ &= \gcd(s_k,r_n)\\ g_nr_n &\equiv 1 \pmod{t_n}\\ g_nr_{n+1} &=g_n(3t_n-r_n) \equiv -1 \equiv -s_0\pmod{t_n}\\ g_nr_{n+1+1} &=g_n(4r_{n+1}-r_n)\equiv -4-1\equiv -s_1 \pmod{t_n}\\ g_nr_{n+1+k} &= g_n(4r_{n+k}-r_{n+k-1}) \equiv -4s_{k-1}+s_{k-2}\equiv -s_k \pmod{t_n}\\ \gcd(t_n,r_{n+1+k}) &= \gcd(t_n,g_nr_{n+1+k})\\ &= \gcd(t_n,g_nr_{n+1+k}\pmod{t_n})\\ &= \gcd(t_n,-s_k)\\ &= \gcd(t_n,s_k) \end{align*}

B. Partial classification via quadratic reciprocity
From the OEIS links (or perhaps provable directly via induction), we have \begin{align*} (r_n) &\subseteq \{x : x^2-3y^2=1\}\\ (s_n) &\subseteq \{x : 3y^2-x^2=2\}\\ (t_n) &\subseteq \{x : 3x^2-2 = y^2\} \end{align*} Therefore primes $p$ in $\mathbb R$ satisfies \begin{align*} -3y^2 &\equiv 1 \pmod p\\ -3 &\equiv (3y)^2 \pmod p \end{align*} which means $-3$ is a quadratic residue for $\mathbb R$. It can be shown that this is possible if and only if $p\equiv 1\pmod 3$, for example here. (Though not a proof.)

Similarly primes $p$ in $\mathbb S$ and primes $q$ in $\mathbb T$ satisfy \begin{align*} 3y^2 &\equiv 2 \pmod p & -2&\equiv y^2 \pmod q\\ 6 &\equiv (3y)^2 \pmod p \end{align*} Hence $6$ and $-2$ are quadratic residues in for $\mathbb {S,T}$ respectively. From the Wikipedia link again, we have $p\equiv 1, 5, 19, 23\pmod{24}$ and $q\equiv 1,3 \pmod 8$.

Extending to and checking primes $\pmod{24}$ using the 3 rules, we obtain: \begin{align*} \mathbb R&: p\equiv 7,13,1,19 \pmod{24}\\ \mathbb S&: p\equiv 5,23,1,19 \pmod{24}\\ \mathbb T&: p\equiv 11,17,1,19 \pmod{24} \end{align*} And indeed class $1\pmod{24}$ appears in all classes by inspection, although type $19$ does not seem to appear in $\mathbb R$.

• Thank you, this is very smart. Even though this is partial answer as it leaves the possibility for the existence of some primes that would never occur as factors in any of the three sequences, I will accept it. May I kindly ask you to clarify how the cycles terminate? I seems to me that it should be possible to show that it always eventually reaches some $\gcd (a_m,b_m)=1$ for some $m$, and some $a,b \in \{r,s,t\}$ with $a\neq b$. – René Gy Feb 24 '18 at 10:25
• Also, can you provide more details on how the congruences modulo $24$ are obtained? Thanks. – René Gy Feb 24 '18 at 10:28
• @RenéGy Hi, I have added the details for modulo $24$ in appendix B. For the termination, the current form of the algorithm would bring $\gcd(a_m,b_m)$ to $\gcd(a_m,c_0)=\gcd(a_m,1)$. Perhaps I should have change the description to $k\geq 1$ and terminate immediately if $k=0$, but since this seems to work I will leave it for now. – Yong Hao Ng Feb 24 '18 at 11:20
• @RenéGy Also it might be possible to show that all primes will occur: Let $p$ be a prime and investigate the iterations of $r_n$ and $t_n$. If one reaches $0\pmod p$ we are done. If both are never $0\pmod p$ perhaps we can conclude that $s_n$ does using the linear relation. I will add it in if I can solve that, though it might turn out to be not solvable (i.e. find a counter example $p$, which we can check in finite steps.) – Yong Hao Ng Feb 24 '18 at 11:24
• Thanks to your observation that no known member of $\mathbb {R}$ is $19 \pmod {24}$, I have just edited my question to include a conjectural table about the density of the primes in a given residue class modulo $24$ in $\mathbb {R}$ (resp. in $\mathbb {S}$, in $\mathbb {T}$). – René Gy Feb 25 '18 at 19:55