\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage{caption} \captionsetup[table]{skip=10pt plus 0.01pt} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\ind}{ind} \usepackage[normalem]{ulem} \usepackage{longtable} \usepackage[shortlabels]{enumitem} \setlist[enumerate, 1]{1\textsuperscript{o}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Sextic Extension of the Lucas Functions } \vskip 1cm \large E.~L.~Roettger\\ Department of General Education \\ Mount Royal University\\ 4825 Mount Royal Gate SW\\ Calgary, AB T3E 6K6\\ Canada \\ \href{mailto:eroettger@mtroyal.ca}{\tt eroettger@mtroyal.ca} \\ \ \\ H.~C.~Williams \\ Department of Mathematics and Statistics \\ University of Calgary\\ 2500 University Drive NW\\ Calgary, AB T2N 1N4 \\ Canada \\ \href{mailto:williams@math.ucalgary.ca}{\tt williams@math.ucalgary.ca} \end{center} \vskip .2 in \begin{abstract} We develop a necessary and sufficient primality test for integers $N$ such that $N^6-1$ is divisible by a large power of $7$, based on the properties of two linear recurrence sequences of order $6$. These two sequences are analogous to the well-known Lucas sequences. In addition, we provide tables from which it is easy to compute the characteristic polynomial of the sequences. \end{abstract} \section{Introduction} Consider the sequence $(G_n)$, where $G_0=0$, $G_1=1$ and $G_{n+1}=G_n-7G_{n-1}$ for all $n\geq1$. In Table \ref{Tab:1} below we tabulate the first few terms of $(G_n)$, together with their prime factorizations. \begin{longtable}[H]{|r|l||r|l|} \hline $n$ & $G_n$ & $n$ & $G_n$ \\\hline 0& $ 0 $ & 13 & $ -93911$ \\\hline 1& $ 1 $ & 14 & $146329= 41\cdot 43 \cdot 83 $ \\\hline 2& $ 1 $ & 15 & $803706 = 2\cdot3\cdot29\cdot31\cdot149$ \\\hline 3& $-6= -2\cdot 3 $ & 16 & $-220597 = -13\cdot71\cdot239$ \\\hline 4& $ -13 $ & 17 & $-5846539$ \\ \hline 5& $29 $ & 18 & $-4302360 =-2^3\cdot3^2\cdot5\cdot19\cdot629$ \\\hline 6& $120=2^3\cdot3\cdot5$ & 19 & $36623413 = 113\cdot324101$ \\\hline 7& $ -83$ & 20 & $66739933 = 13\cdot29\cdot211\cdot839$ \\\hline 8& $-923= -13\cdot71$ & 21 & $-189623958 = -2\cdot3\cdot83\cdot503\cdot757$ \\\hline 9& $-342 = -2\cdot3^2\cdot19$ & 22 & $-656803489 = -8513\cdot77153$ \\\hline 10& $6119=29\cdot 211$ & 23 & $670564217 = 139\cdot4824203$ \\\hline 11& 8513 & 24 & $5268188640 = 2^5\cdot3\cdot5\cdot11\cdot13\cdot23 \cdot47\cdot71$\\ \hline 12 & $-34320=-2^4\cdot 3 \cdot 5\cdot 11\cdot 13 $ &25& $574239121 = 29\cdot449\cdot44101$ \\ \hline \caption{First few values of the sequence $(G_n)$ and their factorizations.} \label{Tab:1} \end{longtable} \medskip Notice that the terms with subscript divisible by 3 tend to have a lot of small prime factors belonging to no particular residue classes, but the other terms seem only to be divisible by primes that are congruent to $\pm1$ modulo 14. In fact, it can be shown that this is always the case for $(G_n)$. This explains why terms with index a multiple of 3 will tend to be highly composite; for all the primes $\not\equiv \pm1 \pmod{14}$, two thirds of them must wait until 3 divides $n$ in order to divide some $G_n$. If we let $q$ be a prime such that $q\equiv1 \pmod{3}$, it is well known that there exist integers $x$ and $y$ such that $4q=x^2+27y^2$. See, for example, Ireland and Rosen \cite[\S6 of Chapter 9]{IR82} or Cox \cite[Chapter 4]{Cox89}. Put $Q=q$ and $P=x$ and define the Lucas sequence $(U_n)$ by $U_0=0$, $U_1=1$ and $U_{n+1}=PU_n-QU_{n-1}$ for $n\geq0$. By a special case $(p=3)$ of Williams \cite[Corollary 11.2.4]{williams} we have the following result: \begin{theorem}\label{11.2.4} Let $q$ be a prime such that $q\equiv 1\pmod{3}$. Put $P=x$ and $Q=q$, where $4q=x^2+27y^2$. If $r$ is a prime such that $r \nmid 3qy$, $r \mid U_n$ and $3 \nmid n$, then $r$ must be a cubic residue of $q$. \end{theorem} We see, then, that for $q=7$ $(x=1$ and $y=1)$, it follows that $(U_n)=(G_n)$ and every prime divisor $r$ of $G_n$ when $3 \nmid n$ must be a cubic residue of $7$. Since the only cubic residues of $7$ are $\pm 1$, we must have $r\equiv \pm 1 \pmod{14}$. The Lucas sequences are examples of linear recurrence sequences of order $2$; the purpose of this paper is to find extensions of Lucas' sequences of order greater than $2$, which possess properties analogous to those that we have observed in $(G_n)$. We then use these sequences to develop primality tests for certain numbers of special form. \section{The Lucas sequences and their extensions} Let $P$ and $Q$ be coprime integers and $\alpha$, $\beta$ be the roots of the quadratic polynomial $f(x) = x^2-Px+Q$ with $\delta= \alpha -\beta$ and $D= \delta^2=P^2-4Q$. We define the Lucas sequences $(U_n)$ and $(V_n)$ as follows: \begin{align*} U_n=(\alpha^n-\beta^n)/\delta, && V_n=\alpha^n+\beta^n. \end{align*} Since both $U_n$ and $V_n$ are symmetric functions of the roots of a polynomial with integer coefficients they must both be integers for all non-negative integral values of $n$. Also, both $(U_n)$ and $(V_n)$ satisfy the following second-order linear recurrence: \[ X_{n+1}=PX_n-QX_{n-1}, \] with $U_0=0$, $U_1=1$ and $V_0=2$, $V_1=P$. The Lucas sequences have many interesting properties that have been applied to many problems; some books that include one or several sections devoted to these sequence, particularly as they apply to primality testing, are Bressoud and Wagon \cite{BW00}, Crandall and Pomerance \cite{CP05}, Ribenboim \cite{ribenboim} and Williams \cite{williams}. Lucas first applied these sequences to the problem of primality testing of Mersenne numbers; see \cite[\S 5.1 and 5.4]{williams}. Indeed, he was actually able to prove the well-known Lucas-Lehmer criterion for the primality of $M_n=2^n-1$. This test is both a necessary and sufficient condition for $M_n$ to be a prime number. Lucas also considered, for a fixed value of $A$, the more general $N_n=A2^n-1$, and provided a sufficiency test for $N_n$ to be a prime. For some commentary on this work, see Roettger, Williams and Guy \cite{RWG2015}. It was Lehmer \cite{Leh30} who essentially proved the following result: \begin{theorem}\label{Leh} Let $N_n=A2^n-1$, where $n>1$, $A$ is odd and $A<2^n$. If $P$ and $Q$ are selected such that the Jacobi symbols $(D/N_n)=(Q/N_n)=-1$, then $N_n$ is a prime if and only if $N_n \mid V_{(N_n+1)/2}$. \end{theorem} This result can be modified slightly, as follows. \begin{theorem}\label{A2} Let $N_n=A2^n-1$, where $n>1$, $A$ is odd and $A<2^n$. Let $q$ be a prime such that $q\equiv 1 \pmod{4}$ and the Legendre symbol $(N_n/q)=-1$. If $x$ and $y$ are integers such that $q=x^2+y^2$, put $P=2x$, $Q=q$; then $N_n$ is a prime if and only if $N_n \mid V_{(N_n+1)/2}$. \end{theorem} In the case that $N_n=A3^n-1$, results in Williams \cite{Prim_of} can be used to prove the following analogue of Theorem \ref{A2}. \begin{theorem}\label{A3} Let $N_n=A3^n-1$, where $n>1$, $3 \nmid A$ and $A<3^n$. Suppose $q$ is a prime congruent to $1$ modulo $3$ such that $N_n^{(q-1)/3}\not\equiv 1 \pmod{q}$ and $4q=x^2+27y^2$. Put $P=x$ and $Q=q$. If $\gcd(N_n, qy)=1$, then $N_n$ is a prime if and only if $V_{2\theta}\equiv -Q^\theta \pmod{N_n}$, where $\theta=(N_n +1)/3$. \end{theorem} We say that a sequence of integers $(X_n)$ is a \emph{divisibility sequence} if whenever $X_n\not=0$, we have $X_n \mid X_{mn}$ for all non-negative integers $n$ and $m$. For example, $(n)$ is trivially a divisibility sequence, but so are $(G_n)$ and the Mersenne sequence $(M_n)$. Lucas made much use of the fact that $(U_n)$ is always a divisibility sequence. Let the sequence $(X_n)$ be determined by an initial set of $h$ integer values \begin{equation}\label{X_0} X_0, X_1, X_2, \dots, X_{h-1} \end{equation} and the $h^{\rm th}$ order linear recurrence \begin{equation}\label{X_n+h} X_{n+h}=P_1X_{n+h-1}-P_2X_{n+h-2}+ \dots +(-1)^{h-1}P_hX_n, \end{equation} where $P_1$, $P_2$,\dots, $P_h$ are given fixed integers. Notice that the values for $X_n$ for all $n\geq 0$ are completely determined by (\ref{X_0}) and (\ref{X_n+h}). We define the \emph{characteristic polynomial} $f(x)$ of the \emph{linear recurrence sequence} $(X_n)$ to be \begin{equation}\label{char} f(x)= x^h-P_1x^{h-1}+P_2x^{h-2}-\dots+(-1)^hP_h. \end{equation} Lucas speculated that his sequences might be extended to those that satisfy a linear recurrence sequence of order greater than 2. Indeed, it is argued in Roettger, Williams and Guy \cite{RWG13} that the Lucas sequences are characterized by five basic properties: \begin{enumerate}[(1)] \item There are two sequences of integers (when $n\geq 0$). \item Both sequences satisfy the same linear recurrence relation. \item One of the two sequences is a divisibility sequence. \item There are addition formulas for the terms of the sequences. \item There are multiplication formulas for the terms of the sequences. \end{enumerate} Given what we know about Lucas' unsuccessful attempt to generalize his sequences, it seems that every sequence that he might have found acceptable as a proper generalization of $(U_n)$ and $(V_n)$ should possess these five properties. In \cite{RWG13} the authors proposed generalizing Lucas' sequence to \begin{align}\label{gen} U_n=\lambda^{n-1} \prod_{i=1}^{k}(1-\gamma_i^n)/(1-\gamma_i)&& \text{and} && V_n=\lambda^n \prod_{i=1}^{k} (1+\gamma_i^n), \end{align} where $\lambda$ and $\gamma_1,\gamma_2,\dots,\gamma_k$ are simply constrained to be distinct non- zero algebraic numbers such that $V_1\not=0$ and both $(U_n)$, $(V_n)$ are sequences of integers for $n\geq0$. Notice that, just as in the case of the Lucas sequences, we have $V_n=U_{2n}/U_n$. Under the above constraints it is easy to prove that if $k=1$, $P=\lambda (\gamma_1+1)$, $Q=\lambda^2\gamma_1$, then both $P$ and $Q$ must be integers because $V_1= \lambda(\gamma_1+1)$, $V_2=\lambda^2(1+ \gamma_1^2)$, $U_3= \lambda^2(1+\gamma_1+\gamma_1^2)$ are all integers. In this case, we see that in (\ref{gen}) $U_n=U_n(P, Q)$, $V_n=V_n(P, Q)$, where $\alpha=\lambda$ and $\beta=\lambda\gamma_1$. Thus, (\ref{gen}) represents a generalization of the Lucas functions. For a fixed value of $k$, conditions on $\lambda$ and $\gamma_1, \gamma_2,\dots,\gamma_k$ were derived in \cite{RWG13} to ensure that both $(U_n)$ and $(V_n)$ are sequences of integers that satisfy the same linear recurrence. For example, one of these conditions is that $Q=\lambda^2\gamma_1\gamma_2\cdots\gamma_k$ be a rational integer. It is also shown that under these same conditions $(U_n)$ is a divisibility sequence. In the case that $k=2$, we must have $T_1$, $T_2$ and $Q$ integers, where \begin{align*} T_1=\lambda(1+\gamma_1)(1+\gamma_2), && T_2=\lambda^2(\gamma_1+\gamma_2)(1+ \gamma_1\gamma_2)+2\lambda^2\gamma_1\gamma_2, && Q= \lambda^2\gamma_1\gamma_2. \end{align*} Thus, if we put $P_1=T_1$ and $P_2+2Q=T_2$, we must have $P_1$, $P_2$ and $Q$ integers. In this case we find that both $(U_n)$ and $(V_n)$ satisfy the same fourth-order linear recurrence: \begin{equation}\label{rec4} X_{n+4}=P_1X_{n+3} -(P_2+2Q)X_{n+2} +P_1QX_{n+1} -Q^2X_n, \end{equation} with initial conditions $U_0=0$, $U_1=1$, $U_2=P_1$, $U_3=P_1^2-P_2-3Q$, $V_0=4$, $V_1=P_1$, $V_2= P_1^2-2P_2-4Q$, $ V_3=P_1(P_1^2-3P_2-3Q)$. Indeed, it has been shown by Abrate et al.\ \cite{ABCM17} that if $(X_n)$ is a linear recurrence sequence of order four that is nondegenerate (no quotient of any two of the roots of the characteristic polynomial is a root of unity) and a divisibility sequence, then $(X_n)$ must satisfy a linear recurrence of the form (\ref{rec4}) for some integers $P_1$, $P_2$ and $Q$. The above sequences, denoted here by $(U_n)$ and $(V_n)$, were discussed in some detail by Williams and Guy in \cite{WG11} and in greater detail in \cite{RWG2015}. Suffice it to say here that they possess the five properties of the Lucas sequences mentioned above; furthermore, they also enjoy many of the arithmetic properties of the Lucas sequences. Thus, these are evidently the fourth-order analogs of the Lucas sequences. As in \cite[\S 7]{RWG2015}, let $q$ be a prime such that $q\equiv 1 \pmod{5}$ and define in (\ref{rec4}) \begin{align}\label{defP_1P_2Q} P_1=P(1,5,q), && P_2=P(2,5,q), && Q=q^3, \end{align} where the rational integers $P(i,5,q)$ are defined in \cite[(11.1.5)]{williams}. As indicated by the notation, the values of $P_1$, $P_2$ and $Q$ here depend only on the value of $q$. Notice that when $k=2$ in \cite[\S10.1]{williams}, the functions denoted by symbols $C_n$ and $V_{1,n}$ there are the same except possibly for sign; also $U_n= V_{1,n} =\pm C_n$. If we let $D$ here denote the discriminant of the characteristic polynomial of $(U_n)$, we have the following consequence of \cite[Corollary 11.2.5]{williams}: \begin{theorem}\label{11.2.5} Suppose $P_1$, $P_2$ and $Q$ are given by (\ref{defP_1P_2Q}). If $r$ is a prime such that $r \nmid 5qD$, $r\mid U_n$ and $5\nmid n$, then $r$ must be a quintic residue of $q$. \end{theorem} This result is for the extended Lucas sequence $(U_n)$ above exactly analogous to the case of the Lucas sequence of Theorem \ref{11.2.4}. In the case of $q=11$, we have $P_1=P(1,5,q)=-89$, $P_2=P(2,5,q)=1199$. The prime factorizations of the values of the corresponding $U_n$ for $n=0, 1,\dots, 30$ are provided in \cite[Table 11.2.1]{williams}. The behaviour of these factorizations is similar to the corresponding case of $(G_n)$, but more extreme because only two of the $10$ nonzero residues of $11$ are quintic resides of $11$. Let $\eta=\pm 1$. If $a$ is an odd integer, define $m(a)$ by $m(a)=(a-\eta)/5$ when $a\equiv \eta \pmod{5}$; otherwise put $m(a)=(a^2+1)/5$ . Also, as in \cite{RWG2015}, let $\gamma_n(5)$ denote the odd solution $x$ of $x^2+1\equiv 0 \pmod{5^n}$ such that $03$. Nevertheless, there is a special case when $k=3$ that does allow us to require only two sequences; this is the case when $\gamma_1\gamma_2\gamma_3=1$. Here we must have $\lambda$ an integer, denoted by $R$, and the resulting sequences $(U_n)$ and $(V_n-2R^n)$ satisfy the same linear recurrence of order $6$: \begin{multline} X_{n+6}=S_1X_{n+5}-(S_2+3R^2)X_{n+4}+(S_3+2R^2S_1)X_{n+3}-R^2(S_2+3R^2)X_{n+2}\label{rec6}\\ +R^4S_1X_{n+1}-R^6X_n, \end{multline} where $S_1$, $S_2$, and $S_3$ are integers such that \begin{equation}\label{S123} S_3=RS_1^2-2RS_2-4R^3. \end{equation} Let $G(x)$ be the characteristic polynomial of (\ref{rec6}). In this case it turns out that $\rho_1$, $\rho_2$, $\rho_3$, where $\rho_i=R(\gamma_i+\gamma_i^{-1})$ $(i=1, 2, 3)$, are the roots of the cubic polynomial \[ g(x)=x^3-S_1x^2+S_2x-S_3. \] If we put $W_n= V_n-2R^n$, it is shown in \cite{RWG13} that $(U_n)$ is a divisibility sequence and the two sequences $(U_n)$, $(W_n)$ also possess the five properties mentioned in the previous section and we call them the extended Lucas sequences for $k=3$. We find that \begin{gather} U_0=0, U_1=1, U_2=S_1+2R, U_3=S_1^2+RS_1-S_2-3R^2; \label{Us}\\ W_0=6, W_1=S_1, W_2=S_1^2-2S_2-6R^2;\nonumber\\ W_3=S_1^3-3S_1S_2+3RS_1^2-6RS_2-3R^2S_1-12R^3. \nonumber \end{gather} Furthermore, for every integer $n$ we have \begin{align}\label{U-n} U_{-n}=-U_n/R^{2n}&& \text{and}&&W_{-n}=W_n/R^{2n}. \end{align} Suppose we are given integral values for $S_1$ $(\not=-2R)$, $S_2$, and determine $S_3$ by (\ref{S123}). We know by \cite[Theorem 7.2]{RWG13} that if $(U_n)$, $(W_n)$ satisfy the linear recurrence (\ref{rec6}) with initial conditions given by (\ref{Us}) and subject to (\ref{U-n}) for $n=1$ and $2$, then there must exist algebraic numbers $\gamma_1$, $\gamma_2$, $\gamma_3$ with $\gamma_1\gamma_2\gamma_3 =1$ such that $U_n$ and $V_n=W_n+2R^n$ are given by (\ref{gen}). Some examples of the sixth-order LDS $(U_n)$ can be found in the {\it On-line Encyclopedia of Integer Sequences} (OEIS) \cite{Slo20}; in particular, we mention \seqnum{A180510} with $S_1=-1$, $S_2=-5$, $S_3=7$, $R=1$, and \seqnum{A005120} with $S_1=-3$, $S_2=2$, $S_3=1$, $R=1$. Others are \seqnum{A001351}, \seqnum{A001945} and \seqnum{A006235}. Many arithmetic properties of the extended Lucas sequences $(U_n)$, $(W_n)$ when $\gcd(S_1, S_2, R)=1$ are provided in \cite{RWG13, RW15}. These are very similar to corresponding results involving the standard Lucas sequences. If we put \[ \Delta=R^2(1-\gamma_1)^2(1-\gamma_2)^2(1-\gamma_3)^2, \] we find that $\Delta$ is the discriminant of $g(x)$ and we can write \[ \Delta=S_1^2-4S_2 +4RS_1-12R^2. \] Also, if \begin{equation} \Gamma=R^4(\gamma_1-\gamma_2)^2(\gamma_2-\gamma_3)^2(\gamma_3-\gamma_1)^2, \label{Gam} \end{equation} we have \[ \Gamma=S_2^2+10RS_1S_2-4RS_1^3-11R^2S_1^2+12R^3S_1+24R^2S_2+36R^4. \] Now assume that $\lambda_i$ $(i=1, 2,\dots, 6)$ are distinct algebraic integers such that \begin{equation}\label{disalg} \lambda_1\lambda_2= \lambda_3\lambda_4= \lambda_5\lambda_6 =R^2, \end{equation} where $R$ is a rational integer. Assume, in addition, that \begin{align} \lambda_1\lambda_3&=R\lambda_6,& \lambda_1\lambda_5&=R\lambda_4, & \lambda_2\lambda_4&=R\lambda_5,& \label{disalg2}\\ \lambda_2\lambda_6&=R\lambda_3,& \lambda_3\lambda_5&=R\lambda_2,& \lambda_4\lambda_6&=R\lambda_1.&\nonumber \end{align} \begin{proposition}\label{firstprop} Suppose that $\lambda_i$ $(i=1,2,\dots,6)$ satisfy the conditions (\ref{disalg}) and (\ref{disalg2}). If we put $\rho_1=\lambda_1+\lambda_2$, $\rho_2=\lambda_3+\lambda_4$, $\rho_3=\lambda_5+\lambda_6$, then $\rho_1$, $\rho_2$, $\rho_3$ are the roots of a cubic $g(x)=x^3-S_1x^2+S_2x-S_3$ with integral coefficients satisfying (\ref{S123}) if and only if $\mu = \lambda_1+\lambda_3+\lambda_5$, $\nu=\lambda_2+\lambda_4+\lambda_6$ are the roots of a quadratic polynomial $x^2-T_1x+T_2$ with integral coefficients. \end{proposition} \begin{proof} Follows easily from the following identities: \begin{align*} \rho_1+\rho_2+\rho_3& =\mu +\nu,& \rho_1\rho_2+\rho_2\rho_3+\rho_3\rho_1=R(\mu +\nu)+\mu\nu-3R^2 \\ &\text{and}& \rho_1\rho_2\rho_3= R(\mu +\nu)^2-2R^2 (\mu +\nu)-2R\mu\nu +2R^3. \end{align*} The latter two of these can be easily verified by appealing to (\ref{disalg}) and (\ref{disalg2}). \end{proof} We note that under the above conditions each $\lambda_i$ $(i=1, 2,\dots, 6)$ is a root of \begin{multline*} G(x)= x^6-S_1x^5+(S_2+3R^2)x^4-(S_3+2R^2S_1)x^3\\ +R^2(S_2+3R^2)x^2-R^4S_1x+R^6=0. \end{multline*} We next put $\mu_n= \lambda_1^n+\lambda_3^n+\lambda_5^n$, $\nu_n=\lambda_2^n+\lambda_4^n+\lambda_6^n$; since by (\ref{disalg}) and (\ref{disalg2}) we find that $\lambda_1\lambda_3\lambda_5 = \lambda_2\lambda_4\lambda_6=R^3$, \begin{align} (\lambda_1^n-R^n) (\lambda_3^n-R^n) (\lambda_5^n-R^n)&=R^{2n}(\mu_n- \nu_n),& \label{disalg3}\\ (\lambda_2^n-R^n) (\lambda_4^n-R^n) (\lambda_6^n-R^n)&=-R^{2n}(\mu_n- \nu_n).& \nonumber \end{align} Note that if we put $\delta= \mu_1- \nu_1$, then because the $\lambda_i$ $(i=1, 2,\dots, 6)$ are all distinct, we conclude from (\ref{disalg3}) and (\ref{disalg}) that $\delta \not=0$. In fact, $\Delta=\delta^2$ is the discriminant of $g(x)=x^3-S_1x^2+S_2x-S_3$. We now define \[ U_n=(\mu_n- \nu_n)/ (\mu_1- \nu_1); \] then \begin{align*} U_0&=0, U_1=1, U_2= \mu_1+\nu_1 +2R=S_1+2R,&\\ U_3&= (\mu_1+\nu_1)^2- \mu_1\nu_1=S_1^2+RS_1-S_2-3R^2.& \end{align*} Also, it is easy to see from (\ref{disalg}) that \begin{align*} \lambda_1^{-n}= \lambda_2^n/R^{2n}, && \lambda_3^{-n}= \lambda_4^n/R^{2n}, &&\lambda_5^{-n}= \lambda_6^n/R^{2n}; \end{align*} hence, by (\ref{disalg3}) we get $U_{-n}=-U_n/R^{2n}$. It follows that $(U_n)$ must be a sixth-order LDS with characteristic polynomial $G(x)$. If we put $\gamma_1= \lambda_1/R$, $\gamma_2= \lambda_3/R$, $\gamma_3= \lambda_5/R$, then by (\ref{disalg3}) we get $U_n$ and $V_n$ $(=\mu_n+\nu_n+2R^n)$ given by (\ref{gen}) with $\gamma_1\gamma_2\gamma_3=1$. Thus, if $W_n= V_n-2R^n= \mu_n+\nu_n$, we see that $(U_n)$ and $(W_n)$ are the extended Lucas sequences when $k=3$. We conclude this section with some number-theoretic properties of the $k=3$ extended Lucas sequence $ (U_n)$. Let $m$ be an integer. We define the \emph{ranks of apparition} $\psi_1$, $\psi_2$,$\dots$ of $m$ in $(U_n)$ as follows: let $\psi_1$ (if it exists) be the least positive value of $n$ such that $m \mid U_n$. For $i=1, 2, \dots$ define $\psi_{i+1}$ (if it exists) to be the least positive integer such that $m \mid U_n$ for $n= \psi_{i+1}$ and $\psi_j \nmid \psi_{i+1}$ for all $j$ such that $1\leq j\leq i$. From results in \cite[\S9]{RWG13} we have the following theorems. \begin{theorem}\label{ranks} Suppose that $r$ is a prime such that $r \nmid 6\Delta\Gamma R$ and let $\epsilon$ be the value of the Legendre symbol $(\Delta/r)$. If $r$ has more than one rank of apparition in $(U_n)$, then these ranks must all be divisors of $r-\epsilon$. Furthermore, if $r$ has a single rank of apparition in $(U_n)$, it must be a divisor of either $r-\epsilon$ or $r^2+\epsilon r+1$. \end{theorem} \begin{theorem}\label{ranks2} Suppose that $r$ is a prime such that $r \nmid 6\Delta\Gamma R$. If $r$ is a divisor of some term $U_n$ $(n\not=0)$ of the sequence $(U_n)$ then some rank of apparition of $r$ in $(U_n)$ must divide $n$. \end{theorem} \section{Some arithmetic properties of the $k=3$ extended Lucas sequences} \label{someproperties} For $n\geq1$, define $D_n=\gcd(W_n-6R^n, U_n)$; by \cite[Theorem 4]{RW15} we know that $(D_n)$ is a divisibility sequence. Let $\omega$ be the least positive value of $n$, if it exists, such that $m$ divides the term $D_n$ of the sequence $(D_n)$ we call $\omega$ the rank of apparition of $m$ in $(D_n)$. We next present some additional arithmetic results concerning $(D_n)$. \begin{theorem}\label{ranks3} (\cite[Theorem 14]{RW15}) If $r$ is a prime such that $r \nmid 2R$, there exists a rank of apparition $\omega$ of $r$ in $(D_n)$; furthermore, if $r$ divides any term $D_m$ of $(D_n)$, then $\omega$ must divide $m$. \end{theorem} \begin{theorem}\label{ranks4} Suppose that $r$ is a prime such that $r \nmid 2R$ and let $\epsilon$ be the value of the Legendre symbol $(\Delta|r)$. The rank of apparition of $r$ in $(D_n)$ is either a divisor of $r$, $r^2-1$ or of $r^2+\epsilon r+1$. \end{theorem} \begin{proof} Follows from the previous result and \cite[Theorems 9 and 13]{RW15}. \end{proof} We also have some results that can be applied to the problem of primality testing. \begin{lemma}\label{Ndiv} Let $N$ be a positive integer such that $\gcd(N, 2R)=1$ and $n$ be a positive integer such that $\gcd(N, n)=1$. If $m$ is a positive integer such that $N \mid U_{mn}/U_m$, then $\gcd(N, D_m)=1$. \end{lemma} \begin{proof} By \cite[Theorem 8]{RW15} we know that $\gcd(U_{mn}/U_m, D_m)$ must be a divisor of $2n^3$. The result now follows easily because\\ $\gcd(N,2n)=1$. \end{proof} We can now prove a theorem analogous to \cite[Theorem 2.4]{RWG2015}. \begin{theorem}\label{anal2.4} Let $N$ be a positive integer such that $\gcd(N, 2R)=1$. Suppose that $n$ is a positive integer such that $\gcd(N, n)=1$ and that for some positive integer $m$ we have $N \mid D_{mn}$ and $N \mid U_{mn}/U_m$. If $r$ is a prime divisor of $N$ and $\omega(r)$ is its rank of apparition in $(D_n)$, then $\omega(r) \mid mn$ and $\omega(r) \nmid m$. \end{theorem} \begin{proof} Clearly, by Theorem \ref{ranks3} we must have $\omega(r) \mid mn$, because $r \mid D_{mn}$. Also, by Lemma \ref{Ndiv}, we see that $r$ cannot divide $D_m$; hence, $\omega(r) \nmid m$. \end{proof} We next examine some values for $N$ to which these results can be applied. Let $p$ be an odd prime such that $p\equiv 1 \pmod{3}$ and let $\lambda_n(p)$ be the least value of $x$ such that \[ x^2+x+1 \equiv 0\pmod{p^n} \text{ and $11$. In what follows we will develop a technique that is sufficient for determining whether $N_n$ is a prime. We first observe that there are only two elements of $\Gamma_n(p)$ that are both bigger than $1$ and odd; denote them by $\beta_n(p)$ and $\beta_n^{*}(p)$ and note that $\beta_n(p)+\beta_n^{*}(p)= p^n\pm1$. If either $\beta_n(p)$ or $\beta_n^{*}(p)$ is a divisor of $N_n$, then since both exceed 1 and are less than $p^n$ $(< N_n)$, $N_n$ cannot be a prime. We now establish the lemma below. \begin{lemma}\label{beta1} Let odd $N_n$ be given by (\ref{OurN}), where $n>1$, $A<2p^n$, and $\beta_n(p)$, $\beta_n^{*}(p)$ do not divide $N_n$, and $N_n$ is not a perfect square. If $N_n$ has at least one prime divisor $t \equiv \gamma \pmod{p^n}$, where $\gamma \in \Gamma_n(p)$, then $N_n$ must be a prime. \end{lemma} \begin{proof} If $N_n$ is composite, then $N_n=tT$, where $T>1$. We have $\gamma T\equiv \gamma_n(p) \pmod{p^n}$; hence, $T\equiv \gamma^{*}\pmod{p^n}$, where $\gamma^{*} \in \Gamma_n(p)$. Thus, there exist integers $m_1$ and $m_2$ such that \begin{equation} Ap^n+ \gamma_n(p)=N_n=(m_1p^n+\gamma)(m_2p^n+\gamma^{*}).\label{m1m2} \end{equation} Since both $t$ and $T$ exceed 1 and neither $\gamma$ nor $\gamma^{*}$ divides $N_n$, we could only have $m_1$ or $m_2 = 0$ whenever the corresponding $\gamma$ or $\gamma^{*}$ is even, but this is impossible because both $t$ and $T$ are odd. It follows that $m_1m_2 \geq1$. If $m_1m_2\geq 2$, then by (\ref{m1m2}) we have $N_n \geq (p^n+1)(2p^n+1)>2p^{2n}+\gamma_n(p)$, which means that $A>2p^n$, a contradiction. Thus, we can only have $m_1 =m_2 = 1$. In this event both $\gamma$ and $\gamma^{*}$ must be even. If $\gamma = \gamma^{*}$, we see that $N_n$ a perfect integral square, which is not permitted. If $\gamma$ and $\gamma^{*}$ are distinct, then because $\gamma, \gamma^{*} \in \Gamma_n(p)$ and are both even, we have $\gamma + \gamma^{*} \geq p^n-1$ and therefore one of $\gamma$ or $\gamma^{*}$ must exceed or equal $(p^n-1)/2$. Also, since $p^n$ cannot divide $2^6$, we observe that $2\not\in \Gamma_n(p)$; thus, both $\gamma$ and $\gamma^{*}$ must be at least 4. We then have $\gamma \gamma^{*}\geq 2(p^n-1)> \gamma_n(p)$. By (\ref{m1m2}) we get $Ap^n> p^{2n}+p^n(p^n-1)= 2p^{2n}- p^n$, and consequently $A>2p^n-1$, which is also a contradiction. \end{proof} In general, the determination of whether or not a given integer is a perfect square can be done quite easily, but in the above case it is even easier because if $N_n$ is a perfect square, then $N_n=(p^n+\gamma)^2$, where $\gamma \in \Gamma_n(p)$ and $2 \mid \gamma$. As we must have $\gamma^2\equiv \gamma_n(p) \pmod{p^n}$ and $2\mid \gamma$, we can only have $\gamma= p^n-1$ when $\gamma_n(p)=1$. However, in this case we find that $N_n=(2p^n-1)^2$, which since $A<2p^n$, is impossible. Now it is easy to show that if $\gamma \in \Gamma_n(p)$ and $\gamma^2\not\equiv 1 \pmod{p^n}$, then $\gamma^2\equiv \lambda_n(p)$ or $\gamma^2\equiv p^n- \lambda_n(p)-1 \pmod{p^n}$. Thus, the only remaining possibilities for $\gamma_n(p)$ are either $\lambda_n(p)$ or $p^n- \lambda_n(p)-1$ and in either case $\gamma_n(p)^2+ \gamma_n(p)+1\equiv 0 \pmod{p^n}$. Also, for each of these possibilities the corresponding $\gamma$ is either $\gamma_n(p)+1$ or $p^n- \gamma_n(p)-1$. If we put $\kappa_n(p)=(\gamma_n(p)^2+ \gamma_n(p)+1)/p^n$, we see that $N_n=(p^n+\gamma)^2$ only if $A=p^n +2(\gamma_n(p)+1)+\kappa_n(p)$ or $A=4p^n -4(\gamma_n(p)+1)+\kappa_n(p)$. Thus, we can exclude the possibility that $N_n$ is a perfect square in Lemma \ref{beta1} if we assert that \begin{align} A&\not= p^n +2(\gamma_n(p)+1)+\kappa_n(p) \text{ when $2\mid A$ or} \label{avoidperfect}\\ A&\not= 4p^n -4(\gamma_n(p)+1)+\kappa_n(p) \text{ when $2\mid A$}.\nonumber \end{align} Notice that if \begin{align*} A&=p^n +2(\gamma_n(p)+1)+\kappa_n(p) \text{ or }\\ A&=4p^n -4(\gamma_n(p)+1)+\kappa_n(p), \end{align*} then $N_n$ is a perfect square and therefore cannot be a prime. With the above results we can now devise a sufficiency test for the primality of $N_n$. \begin{theorem}\label{prime1} Let odd $N_n$ be given by (\ref{OurN}), where $n>1$, $A<2p^n$, $A$ satisfies (\ref{avoidperfect}), and $\beta_n(p)$, $\beta_n^{*}(p)$ do not divide $N_n$. Suppose $\gcd(N_n, R)=1$ and $m$ is some positive integer such that $p^{n-1} \mid m$. If $N_n \mid D_{mp}$ and $N_n \mid U_{mp}/U_m$, then $N_n$ is a prime. \end{theorem} \begin{proof} Let $r$ be a prime divisor of $N_n$, and let $\omega(r)$ denote its rank of apparition in $(D_n)$. By Theorem \ref{anal2.4}, we must have $\omega(r) \mid mp$ and $\omega(r) \nmid m$; hence, $p^n \mid \omega(r)$. Since $\gcd(p, N_n)=1$, we see that $p\not=r$. Thus, by Theorem \ref{ranks4}, we must have $t \equiv \gamma \pmod{p^n}$, where $\gamma \in \Gamma_n(p)$; it follows by Lemma \ref{beta1} that $N_n$ is a prime. \end{proof} In order for Theorem \ref{prime1} to be practical, we need to study how to compute $W_{mn}$ and $U_{mn}/U_m$ modulo $N$ for a positive integer $N$ such that $\gcd(N, R)=1$. Let $e_i(x_1, x_2,\dots, x_6)$ denote the $i^{\rm th}$ elementary symmetric polynomial of $x_1$, $x_2$,$\dots$, $x_6$ and put $$A_i=e_i(\lambda_1^n, \lambda_2^n, \lambda_3^n,\dots, \lambda_6^n)$$ for $i=1, 2,\dots, 6$. If $\mu_n= \lambda_1^n+\lambda_3^n+\lambda_5^n$, $\nu_n=\lambda_2^n+\lambda_4^n+\lambda_6^n$ and (\ref{disalg}) and (\ref{disalg2}) hold, it is not difficult to show that \begin{align*} A_1&=\mu_n+\nu_n=W_n, A_2=R^n(\mu_n+\nu_n)+ \mu_n\nu_n, \\ A_3&=R^n(\mu_n+\nu_n)^2-2R^n\mu_n\nu_n+2R^{3n} \end{align*} and $A_4=R^{2n}A_2$, $A_5=R^{4n}A_1$, $A_6=R^{6n}$. Also, since \[ \mu_n+\nu_n=W_n\text{ and } \mu_n-\nu_n=\delta U_n, \] we find that $\mu_n\nu_n =(W_n^2-\Delta U_n^2)/4$; hence, \[ A_2=R^nW_n+(W_n^2-\Delta U_n^2)/4. \] In addition to this we note that since \[ \mu_{2n}+\nu_{2n}= (\mu_n+\nu_n)^2-2\mu_n\nu_n-2R^n(\mu_n+\nu_n) \] we get $W_{2n} =W_n^2-2\mu_n\nu_n-2R^nW_n$ and $2\mu_n\nu_n= W_n^2-W_{2n}-2R^nW_n$. If we substitute this latter formula into the formulas for $A_3$ above, we get \[ A_3=R^n(W_{2n}+2R^nW_n+2R^{2n}). \] Since $\lambda_i^n$ $(i=1, 2,\dots, 6)$ are the roots of $x^6-A_1x^5+A_2X^4-A_3x^3+A_4x^2-A_5x+A_6$, we see that for a fixed $n$ both $(W_h)$ and $(U_h)$ satisfy the linear recurrence \begin{multline} Z_{mn+6n}=A_1Z_{mn+5n}-A_2Z_{m+4n} +A_3Z_{mn+3n}\label{genrec} \\ - R^{2n}A_2Z_{mn+2n}+ R^{4n}A_1Z_{mn+n}-R^{6n}Z_{nm}, \end{multline} a generalization of (\ref{rec6}). Suppose that a given $N$ is such that $\gcd(N,2R)=1$. For positive integers $n$ and $m$ define \begin{align*} &X_n \equiv W_n/(2R^n), \tilde{D}_n\equiv \Delta U_n^2/(4R^{2n}), \\ &Y_{n,m}\equiv U_{mn}/(U_mR^{mn-m}) \pmod{N}. \end{align*} If we refer back to Theorem \ref{prime1}, we see that $N \mid D_{mp}$ and $N \mid U_{mp}/U_m$ if and only if $X_{mp}\equiv 3 \pmod{N}$ and $Y_{p,m}\equiv 0 \pmod{N}$. In view of (\ref{genrec}) we can use the arguments made by Roettger and Williams in \cite[\S 3]{RW2012}, to compute remote terms of both $(U_n)$ and $(W_n)$ modulo $N$. Indeed, there exist polynomials $F_m$, $G_m \in \mathbb{Z}[x,y]$ such that \begin{align*} X_{mn}=F_m(X_n, \tilde{D}_n) \text{ and } Y_{m, n}=G_m(X_n, \tilde{D}_n). \end{align*} We have $F_0(x,y)=3$, $F_1(x,y)=x$, $F_2(x,y)=x^2+y-2x$, $F_3(x,y)=x^3+3xy+3y-3x^2+3$ and $G_0(x,y)=0$, $G_1(x,y)=1$, $G_2(x,y)=2x+2$, $G_3(x,y)=3x^2+y$. Also, if we define the sextet $\mathcal{S}_m=\{F_m, F_{m+1}, F_{m+2}, G_m, G_{m+1}, G_{m+2} \}$, then given $\mathcal{S}_m$, we can compute $\mathcal{S}_{2m+1}$ or $\mathcal{S}_{2m}$ in 12 multiplications by using the formulas given in \cite{RW2012}. We remark here that there are some misprints in \cite[formulas (14) and (15)]{RW2012}. For our case they should read \begin{align*} & F_{2m+3}=F_{m+1}(F_{m+2}-x)+yG_{m+1}(G_{m+2}+1)+F_m,\\ & G_{2m+3}=F_{m+1}(G_{m+2}-1)+G_{m+1}(F_{m+2}+x)-G_m, \end{align*} respectively. If we put $x\equiv X_n$ and $y\equiv \tilde{D}_n \pmod{N}$, this allows us to compute $X_{mn}\equiv F_m(x,y)$, $Y_{m,n}\equiv G_m(x,y) \pmod{N}$ in $12k$ modular multiplications modulo $N$, where $k=\lceil \log N \rceil$. \section{Some results concerning Gaussian and Jacobi sums} In this section we will review some of the properties of some special sums that will be of importance in the sequel. We first consider two distinct odd primes $p$, $q$, where $q\equiv 1 \pmod{p}$. Let $\chi$ denote a primitive Dirichlet character of order $p$. If $t$ is a primitive root of $q$, we can define $\chi$ by $\chi (t^j)= \zeta_p^j$, where $\zeta_p$ is a fixed primitive $p^{\rm th}$ root of unity. It is well known, see, for example, Williams \cite[Chapter 11]{williams} or Berndt et al.\ \cite{BEW1998}, that if $\tau(\chi)$ denotes the Gauss sum \[ \tau(\chi) =\sum_{j=1}^{q-1} \chi(j)\zeta_q^j, \] where $\zeta_q$ is a primitive $q^{\rm th}$ root of unity, then \begin{equation}\label{tau1} \tau(\chi) \tau(\chi^{-1})=q. \end{equation} We also know that $(\tau(\chi))^p/q$ can be written as the sum $\sum_{i=0}^{p-1} b_i\zeta_p^j$, where $b_i \in \mathbb{Z}$ for $i=0, 1, 2,\dots, p-1$. In fact, we can write \begin{equation}\label{tau2} (\tau(\chi^j))^p/q =\sum_{i=0}^{p-1}b_i\zeta_p^{ij}, \;\;\; (j=1, 2,\dots, p-1). \end{equation} This is a consequence of the fact that if $\chi_1\chi_2\not= \chi_0$, the primitive Dirichlet character, then \begin{equation}\label{tau3} \tau(\chi_1) \tau(\chi_2)=J(\chi_1, \chi_2) \tau(\chi_1\chi_2), \end{equation} where $J(\chi_1, \chi_2)$ is the Jacobi sum. For much more information on Gaussian and Jacobi sums, see \cite{BEW1998}. From (\ref{tau3}) and (\ref{tau1}), we easily deduce that \begin{equation}\label{tau4} J(\chi^m, \chi^n) J(\chi^{-m}, \chi^{-n})=q \end{equation} and by \cite[Theorem 2.1.5]{BEW1998} we have \begin{equation}\label{tau5} J(\chi^n, \chi^m )=J(\chi^m, \chi^n )= J(\chi^{-m-n}, \chi^m)= J(\chi^{-m-n}, \chi^n). \end{equation} In \cite[\S 11.1]{williams} one method of computing non-negative integers $B(i, j)$ $(0\leq i, j\leq p-1)$ such that \begin{equation}\label{tau6} J(\chi, \chi^j)= \sum_{i=0}^{p-1}B(i, j)\zeta_p^i \end{equation} is discussed. There are other methods for computing the $B(j,1)$; for example, Whiteman \cite[(5.8)]{Whi52} has given a general method that involves computing Jacobsthal sums. In the case of $p=7$, several properties of these Dickson-Hurwitz sums $B(i, j)$ are provided in Leonard and Williams \cite{LW74, LW75}. This will be discussed further in \S 7 below. By using (\ref{tau4}) and \begin{equation}\label{tau7} (\tau(\chi))^p=q\prod_{i=1}^{p-2}J(\chi, \chi^i), \end{equation} a consequence of (\ref{tau1}) and (\ref{tau3}), we see that all $p$ values of the integers $b_i$ in (\ref{tau2}) can be computed in $O(p^3)$ arithmetic operations, once the $p^2$ values of $B(i, j)$ $(0\leq i, j\leq p-1)$ have been calculated. Notice that the values of all of these integers depend only on the preselected values of $p$ and $q$. Let $\mathbb{K} =\mathbb{Q}(\zeta_p)$ be the cyclotomic field formed by adjoining $\zeta_p$ to the rationals. These fields have been the objects of much study (see, for example, Washington \cite{Was82}), but we will only require a few simple results concerning them here. For $j$ not divisible by $p$, we define the automorphism $\sigma_j$ on $\mathbb{K}$ by $\sigma_j(\zeta_p) = \zeta_p^j$. Note that $\sigma_j (J(\chi^m, \chi^n) )= J(\chi^{jm}, \chi^{jn})$. Let $\mathfrak{q}$ be a prime ideal lying over the principal ideal $(q)$ in the ring $\mathcal{O}$ $(=\mathbb{Z} [\zeta_p])$ of algebraic integers in $\mathbb{K}$. Since $q\equiv 1 \pmod{p}$, we can write \cite[p.\ 65]{BEW1998} \[ q\mathcal{O}=\mathfrak{q}_1\mathfrak{q}_2\mathfrak{q}_3\cdots \mathfrak{q}_{p-1}, \] where the $\mathfrak{q}_j$ $(j=1, 2,\dots, p-1)$ are distinct prime ideals lying over $q$ in $\mathcal{O}$ and $\mathfrak{q}_j=\sigma_j(\mathfrak{q})$. With this information, we can use \cite[Theorem 2.1.14]{BEW1998} to find the prime ideal decomposition of $J(\chi^n, \chi^m)$ in $\mathbb{K}$. In the sequel we assume $p=7$ and denote $\zeta_7$ by $\zeta$ . For fixed $j$ such that $7\nmid j$ define \begin{equation}\label{tau8} \xi (\chi^j)= \tau(\chi^j)^7\tau(\chi^{5j})^7. \end{equation} By (\ref{tau7}) and (\ref{tau5}) we get \begin{align*} &\tau(\chi^j)^7=qJ(\chi^j, \chi^j)^2 J(\chi^j, \chi^{2j})^2 J(\chi^j, \chi^{3j}) \text{ and }\\ &\tau(\chi^{5j})^7=qJ(\chi^{5j}, \chi^{5j})^2 J(\chi^{5j}, \chi^{3j})^2 J(\chi^{5j}, \chi^j). \end{align*} Also, by (\ref{tau5}) we have \[ J(\chi^{-j}, \chi^{-2j}) = J(\chi^{3j}, \chi^{-2j}) = J(\chi^{3j}, \chi^{5j}); \] hence, by (\ref{tau4}) we get \[ \xi (\chi^j)= q^4 J(\chi^j, \chi^j)^2 J(\chi^{5j}, \chi^{5j})^2 J(\chi^j, \chi^{3j}) J(\chi^{5j}, \chi^j), \] which since $J(\chi^{5j}, \chi^j)= J(\chi^j, \chi^j)$, $J(\chi^j, \chi^{3j}) = J(\chi^{3j}, \chi^{3j})$ ( by (\ref{tau5})) means that we can write \begin{equation}\label{tau9} \xi (\chi^j)= q^4 J(\chi^j, \chi^j)^3 J(\chi^{5j}, \chi^{5j})^2 J(\chi^{3j}, \chi^{3j}). \end{equation} Thus, by (\ref{tau6}) there must exist, independent of $j$, rational integers $C_0$, $C_1$, $C_2,\dots, C_6$ such that if $h(x)= C_0+C_1 x+ C_2 x^2+ \dots +C_6 x^6$, then \begin{equation}\label{tau10} \xi (\chi^j)/q^4= J(\chi^j, \chi^j)^3(\sigma_5(J(\chi^j, \chi^j)))^2 \sigma_3(J(\chi^j, \chi^j)) =h(\zeta^j) \end{equation} for $j$ such that $7\nmid j$. \section{Some special extended Lucas sequences}\label{specialex} We now put $\lambda_1=h(\zeta^j)$, $\lambda_3= h(\zeta^{2j})$, $\lambda_5= h(\zeta^{4j})$, $\lambda_2= h(\zeta^{6j})$, $\lambda_4= h(\zeta^{5j})$, $\lambda_6= h(\zeta^{3j})$. We observe by (\ref{tau1}) and (\ref{tau8}) that if we put $R=q^3$, then \[ \lambda_1\lambda_2= \lambda_3\lambda_4= \lambda_5\lambda_6 =R^2. \] Since $\lambda_1=h(\zeta^j)$ and $\lambda_3= h(\zeta^{2j})$, we see by (\ref{tau1}) and (\ref{tau8}) that \begin{align*} q^8\lambda_1\lambda_3&= \xi(\chi^j)\xi(\chi^{2j})= \tau(\chi^j)^7\tau(\chi^{5j})^7\tau(\chi^{2j})^7\tau(\chi^{3j})^7\\ &= q^7\tau(\chi^j)^7\tau(\chi^{3j})^7=q^7\xi(\chi^{3j})=q^{11}h(\zeta^{3j})=q^{11}\lambda_6, \end{align*} and therefore $\lambda_1\lambda_3=R\lambda_6$. Similarly, we find that \begin{align*} \lambda_1\lambda_5=R\lambda_4,&& \lambda_2\lambda_4=R\lambda_5, && \lambda_2\lambda_6=R\lambda_3,&& \lambda_3\lambda_5=R\lambda_2, && \lambda_4\lambda_6=R\lambda_1. \end{align*} Thus, we see that $\lambda_1$, $\lambda_2$, $\lambda_3$, $\lambda_4$, $\lambda_5$, $\lambda_6$ satisfy (\ref{disalg}) and (\ref{disalg2}). We also have \begin{align*} \mu &=\lambda_1+\lambda_3+\lambda_5=3C_0+M_1\kappa+M_2\kappa^{*} \\ \nu &=\lambda_2+\lambda_4+\lambda_6=3C_0+M_1\kappa^{*}+M_2\kappa, \end{align*} where \begin{align*} \kappa &= \zeta^j+ \zeta^{2j}+ \zeta^{4j}, \\ \kappa^{*} &= \zeta^{3j}+ \zeta^{5j}+ \zeta^{6j},\\ M_1 &=C_1+C_2+C_4, \quad \text{and} \\ M_2 &=C_3+C_5+C_6. \end{align*} Since $\kappa+\kappa^{*}=-1$ and $\kappa\kappa^{*}= 2$, we deduce that $T_1= \mu+\nu$ and $T_2= \mu\nu$ are rational integers. Thus, by Proposition \ref{firstprop}, we find that if we put, $S_1=T_1$, $S_2=RT_1+T_2-3R^2$, and $S_3$ is given by (\ref{S123}), the corresponding sequences $(U_n)$, $(W_n)$ are particular instances of the $k=3$ extended Lucas sequences. By \cite[Theorem 2.1.4]{BEW1998}, we find that \begin{align} J(\chi,\chi)\mathcal{O} = \mathfrak{q}_1\mathfrak{q}_4\mathfrak{q}_5, && J(\chi^5,\chi^5)\mathcal{O} =\mathfrak{q}_4\mathfrak{q}_5\mathfrak{q}_6, && J(\chi^3, \chi^3)\mathcal{O} =\mathfrak{q}_1\mathfrak{q}_3\mathfrak{q}_5; \end{align} however, in this case $(p=7)$ the cyclotomic field $\mathbb{K}$ has class number one and is therefore a unique factorization domain; it follows that we can put $\mathfrak{q}_j =\pi_j\mathcal{O}$ $(j=1, 2,\dots, p-1)$, where $\pi_j$ is some prime divisor of $q$ in $\mathcal{O}$. Thus, we can write \begin{align*} J(\chi, \chi)= \pi_1\pi_4\pi_5, && J(\chi^5, \chi^5)=\pi_4\pi_5\pi_6, && J(\chi^3, \chi^3) =\pi_1\pi_3\pi_5, \end{align*} where $\pi_j= \sigma_j(\pi_1)$. It follows from (\ref{tau9}) and (\ref{tau10}) that $h(\zeta)$ is $\pi_1^4\pi_3\pi_4^5\pi_5^6\pi_6^2$. Suppose that $\gcd(S_1, S_2, R)>1$; then $q \mid S_1$ and $q \mid S_2$. Now since $h(\zeta)$ must be one of the six roots of (\ref{disalg3}), we find that $q$ must divide $h(\zeta)^6$, which means that $\pi_2$ must divide $h(\zeta)$, an impossibility. Thus, we must have $\gcd(S_1, S_2, R)=1$ here. In what follows we will develop some properties of these special extended Lucas sequences that result for the values of $S_1$, $S_2$ and $R$ given above. We first observe that $\delta= \mu-\nu =(M_1-M_2)(\kappa-\kappa^{*})$; hence, since $$(\kappa-\kappa^{*})^2=(\kappa+\kappa^{*})^2-4\kappa\kappa^{*}=-7,$$ we get $\Delta=-7(M_1-M_2)^2$. Thus, if $r$ is a prime such that $r \nmid \Delta$, then $\epsilon=(\Delta/r)=(-7/r)=(r/7)$. Suppose $r \equiv \eta \pmod{7}$, where $\eta=\pm1$; in this case we have $\epsilon=\eta$ and we put $m(r) =(r- \epsilon)/7$. If $r \not\equiv \pm 1 \pmod{7}$, then we have $7 \mid r^2+\epsilon r+1$, and in this case we put $m(r)= (r^2+\epsilon r+1)/7$. Now let $q$ be a fixed prime such $q\equiv 1 \pmod{7}$ and $r$ be an odd prime such that $r\not=7$, $q$. Also, let $\mathbb{F}_t$ denote the finite field containing $t =r^n$ elements, where $n=3(q-1)$. Since $\mathbb{F}_t^*$ is a cyclic group with generator $\gamma$, say, we can put $\zeta= \gamma^{(t-1)/7}$ and $\zeta_q= \gamma^{(t-1)/q}$ and repeat the arguments in the previous section concerning the Gauss and Jacobi sums in $\mathbb{F}_t$. We find that all the numbered results in that section hold in $\mathbb{F}_t$. Suppose we let $g$ denote a fixed primitive root of $q$ and put $\iota=\ind_g r$. Notice that $7 \nmid \iota$ if and only if $r^{(q-1)/7}\not\equiv 1 \pmod{q}$. We will now conduct our calculations in $\mathbb{F}_t$. We observe that by (\ref{tau6}) we have \begin{equation}\label{jacobi1} J(\chi^j, \chi^{sj})^r= J(\chi^{rj}, \chi^{rsj}), \end{equation} for $s$ such that $7\nmid s$. Also, from the definition of $\tau(\chi^j)$, we get \begin{equation}\label{jacobi2} \tau(\chi^j)^r=\sum_{i=0}^{q-1}\chi^{rj}(i) \zeta_7^{ri}= \zeta^{\iota rj} \tau(\chi^{rj}). \end{equation} If $m=(r- \epsilon)/7$, then by (\ref{jacobi2}) and (\ref{tau1}) we get \begin{equation}\label{jacobi3} \tau(\chi^j)^{7m}= \zeta^{\iota rj} \tau(\chi^j)^{-\epsilon} \tau(\chi^{rj})= \zeta^{\iota rj} \tau(\chi^j)^{-\epsilon} \tau(\chi^{\epsilon j})= \zeta^{\iota rj}q^{(1-\epsilon)/2}. \end{equation} It follows that since $q^{4m}\lambda_1^m = \tau(\chi^j)^{7m}\tau(\chi^{5j})^{7m}$, we can conclude from (\ref{jacobi3}) that \begin{equation}\label{jacobi4} \lambda_1^m= \zeta^{6\iota rj}q^{1-\epsilon-4m}= \zeta^{6\iota rj}q^{1-r+3m}= \zeta^{6\iota rj}R^m. \end{equation} We also find that \begin{gather} \lambda_2^m= \zeta^{\iota rj}R^m, \quad \lambda_3^m= \zeta^{5\iota rj}R^m, \quad \lambda_4^m= \zeta^{2\iota rj}R^m,\label{jacobi5}\\ \lambda_5^m= \zeta^{3\iota rj}R^m, \quad \lambda_6^m= \zeta^{4\iota rj}R^m.\nonumber \end{gather} If $m=(r^2+\epsilon r+1)/7$, we find by repeated application of (\ref{jacobi2}) that \[ \tau(\chi^j)^{7m}= \zeta^{\iota(1-r)j} \tau(\chi^j) \tau(\chi^{rj})^\epsilon \tau(\chi^{sj}), \] where $s=r^2$. Since by (\ref{tau1}) we have $\tau(\chi^{rj})^\epsilon= q^{(\epsilon-1)/2}\tau(\chi^{r\epsilon j})$, we get \[ \tau(\chi^j)^{7m}= \zeta^{\iota(1-r)j} q^{(\epsilon-1)/2}\tau(\chi^j)\tau(\chi^{r\epsilon j})\tau(\chi^{sj}). \] Now by (\ref{tau3}), we have \[ \tau(\chi^j)\tau(\chi^{sj})= J(\chi^j, \chi^{sj})\tau(\chi^{sj+j})= J(\chi^j, \chi^{sj})\tau(\chi^{-\epsilon rj}); \] hence, by (\ref{tau1}) we find that \[ \tau(\chi^j)^{7m}= \zeta^{\iota (1-r)j} q^{(\epsilon+1)/2} J(\chi^j, \chi^{sj}). \] By the reasoning used in the case where $m=(r- \epsilon)/7$, we discover that \[ \lambda_1^m= \zeta^{6\iota(1-r)j}q^{\epsilon+1-4m}J(\chi^j, \chi^{sj}) J(\chi^{5j}, \chi^{5sj}). \] We observe that $s=r^2\equiv 2$ or $4 \pmod{7}$. By (\ref{tau5}) and (\ref{tau4}) we find that in either case, we get \[ J(\chi^j, \chi^{sj}) J(\chi^{5j}, \chi^{5sj})=q. \] Thus, since $\epsilon+2-7m= (1-r)(1+r+\epsilon)$ we get \begin{equation}\label{jacobi6} \lambda_1^m= \zeta^{6\iota(1-r)j}q^{\epsilon+2-4m}= \zeta^{6\iota(1-r)j}q^{\epsilon+2-7m}q^{3m}= \zeta^{6\iota(1-r)j}R^m, \end{equation} and we also have \begin{gather} \lambda_2^m= \zeta^{\iota(1-r)j}R^m, \quad \lambda_3^m= \zeta^{5\iota(1-r)j}R^m, \quad \lambda_4^m= \zeta^{2\iota(1-r)j}R^m, \label{jacobi7}\\ \lambda_5^m= \zeta^{3\iota (1-r)j}R^m, \quad \lambda_6^m= \zeta^{4\iota(1-r)j}R^m. \nonumber \end{gather} Thus, in either case when $m=m(r)$, we have $\mu_{7m} =\nu_{7m}=3R^{7m}$. Also, if $r\equiv \pm 1 \pmod{7}$ and $7 \nmid \iota$ , then by (\ref{jacobi4}) and (\ref{jacobi5}) we have $\mu_m=KR^m$ and $\nu_m=K^{*}R^m$, where $K$, $K^{*}\in \mathbb{F}_t$, $K+K^{*}=-1$ and $KK^{*}=2$. If $r \not\equiv \pm 1 \pmod{7}$ and $7 \nmid \iota$, we also have $\mu_m=KR^m$ and $\nu_m=K^{*}R^m$, where $K$, $K^{*}\in \mathbb{F}_t$, $K+K^{*}=-1$ and $KK^{*}=2$. Since $(K-K^{*})^2=-7$, we must have $\mu_m\not= \nu_m$ for $r\not=7$, whenever $7 \nmid \iota$. Of course, if $7 \mid \iota$, then $\mu_m =\nu_m$. We are now able to prove the following important result concerning these special extended Lucas sequences. \begin{theorem}\label{D7m} Let $r$ be a prime such that $r \nmid q\Delta$ and let $m=m(r)$ be defined as above. If the sequences $(U_n)$, $(W_n)$ are the special extended Lucas sequences defined in this section, then $r \mid D_{7m}$ and $r \mid U_m$ if and only if $r^{(q-1)/7}\equiv 1 \pmod{q}$. \end{theorem} \begin{proof} This result follows easily from $\delta U_n =\mu_n-\nu_n$, $W_n= \mu_n+\nu_n$ and our above remarks. \end{proof} We are now able to present one of the main results of this paper. This result is the analogue of Theorems \ref{11.2.4} and \ref{11.2.5} above. \begin{theorem}\label{analogue1} Let $r$ be a prime such that $r \nmid 6q\Delta$. If $7\nmid n$ and $r \mid U_n$, then $r^{(q-1)/7}\equiv 1 \pmod{q}$. \end{theorem} \begin{proof} If $r \mid \Gamma$ where $\Gamma$ is given by equation (\ref{Gam}), we know by results in \cite[\S 9]{RWG13} that $r$ has a single rank of apparition $\psi$ in $(U_n)$ and $\psi \mid r\pm1$. Furthermore, it is easy to see from these results that if $r \mid U_n$, then $\psi \mid n$. If $r \nmid \Gamma$, by Theorem \ref{ranks2} we know that some rank of apparition $\psi$ of $r$ in $(U_n)$ must divide $n$. Hence, in either case, we have $7 \nmid \psi$. Also, if $r^{(q-1)/7}\not\equiv 1 \pmod{q}$, then by Theorem \ref{D7m} we have $r \nmid U_m$ and $r \mid U_{7m}$, where $m=m(r)$. If $r$ has a single rank of apparition in $(U_n)$, then it must be $\psi$ and also a divisor of $7m$, but since $7\nmid \psi$, we must have $\psi \mid m$, which is impossible because $(U_n)$ is a divisibility sequence and $r \nmid U_m$. Thus, if $r$ has more than one rank of apparition in $(U_n)$, by Theorem \ref{ranks} we can only have $\psi \mid r-\epsilon$, where $\epsilon=(r/7)$. If $r\equiv \pm 1 \pmod{7}$, then $m=(r-\epsilon)/7$ and since $7 \nmid \psi $ and $\psi \mid 7m$, we must have $\psi \mid m$, which we have already seen is a contradiction. If $r\not\equiv \pm 1 \pmod{7}$, then $m=(r^2+\epsilon r+1)/7$. By Theorems \ref{ranks2} and \ref{ranks}, this means that there must be some rank of apparition $\phi$ of $r$ in $(U_n)$ such that $\phi \mid 7m$ and $\phi \mid r-\epsilon$. Since $7m= (r-\epsilon)2+3\epsilon r$, this means that $\phi$ can only be $1$ or $3$. The former case is impossible because $U_1=1$. Thus, $\phi$ must be 3, but since $3 \mid m$, this is also impossible because $r \nmid U_m$. \end{proof} We next turn to the problem of finding an analogue to Theorems \ref{A2} and \ref{A3}. This is provided by the next results; however, we must first impose some conditions on \begin{equation}\label{N7} N_n= A7^n+ \gamma_n(7) \text{ $(n>1)$}, \end{equation} the number whose primality we wish to establish. By our results in \S \ref{someproperties}, we may insist that \begin{enumerate}[(i)] \item $\beta_n(7) \nmid N_n$ and $\beta_n^{*}(7) \nmid N_n$; \label{property1} \item $A\not= 7^n +2(\gamma_n(7)+1)+\kappa_n(7)$ when $2 \mid A$ \label{property2} or \\ $A\not= 4\cdot7^n -4(\gamma_n(7)+1)+\kappa_n(7)$ when $2 \nmid A$; \end{enumerate} otherwise, $N_n$ cannot be a prime. Let $\epsilon (N_n)$ be the value of the Legendre symbol $(N_n/7)=(\gamma_n(7)/7)$. If $\gamma_n(7) \equiv \pm 1 \pmod{7}$, then $\gamma_n(7)\equiv \epsilon (N_n) \pmod{7}$ and we put $m(N_n)= (N_n- \gamma_n(7))/7$. Since $N_n^3\equiv \epsilon (N_n) \pmod{7}$, we see that $7 \mid (N_n^2+\epsilon (N_n)N_n+1)$ when $\gamma_n(7) \not\equiv \pm1 \pmod{7}$, and we put $m(N_n)=(N_n^2+\epsilon(N_n)N_n+1)/7$. In either case $m(N_n)$ is an integer. Furthermore, when $\gamma_n(7) \not\equiv \pm1 \pmod{7}$, we must by definition of $\gamma_n(7)$ have $N_n^2+sN_n+1\equiv \gamma_n(7)^2+s\gamma_n(7) +1\equiv 0 \pmod{7^n}$ for some $s \in \{1, -1\}$; it follows that $s$ can only be $\epsilon(N_n)$, and therefore $7^n \mid 7m(N_n)$. \begin{theorem}\label{primeD7} Let $N_n$ be given by (\ref{N7}) such that $\gcd(N_n, 2q\Delta)=1$. Suppose further that $N_n$ satisfies the conditions \ref{property1} and \ref{property2}. If $A<2\cdot 7^n$, $m =m(N_n)$, and $N_n^{(q-1)/7}\not\equiv 1 \pmod{q}$, then $N_n$ is a prime if and only if $N_n \mid D_{7m}$ and $N_n \mid U_{7m}/U_m$. \end{theorem} \begin{proof} We have seen by Theorem \ref{prime1} that if $N_n \mid D_{7m}$ and $N_n \mid U_{7m}/U_m$, then $N_n$ is a prime. Also, by Theorem \ref{D7m}, we see that if $N_n$ is a prime, then $N_n \nmid U_m$, $N_n \mid U_{7m}$ and $N_n \mid W_{7n}-6R^{7n}$. It follows that $N_n \mid D_{7m}$ and $N_n \mid U_{7m}/U_m$. \end{proof} \begin{theorem}\label{niceprime} Let $N_n$ be given by (\ref{N7}) such that $\gcd(N_n, 2q\Delta)=1$. Suppose further that $N_n$ satisfies the conditions \ref{property1} and \ref{property2}. If $A<2\cdot7^n$, $m =m(N_n)$, and $N_n^{(q-1)/7}\not\equiv 1 \pmod{q}$, then $N_n$ is a prime if and only if \begin{align*} W_m\equiv -R^m &&\text{and}&& \Delta U_m^2\equiv -7R^{2m} \pmod{N_n}. \end{align*} \end{theorem} \begin{proof} Since $W_m= \mu_m +\nu_m$ and $\delta U_m=\mu_m-\nu_m$, we see by our remarks following (\ref{jacobi7}) that if $N_n$ is a prime, then $W_m\equiv -R^m \pmod{N_n}$ and $\Delta U_m^2\equiv -7R^{2m} \pmod{N_n}$. If $W_m\equiv -R^m \pmod{N_n}$ and $\Delta U_m^2\equiv -7R^{2m}\pmod{N_n}$, then because \begin{align*} F_7(-1/2,-7/4)=3&&\text{ and }&& G_7(-1/2,-7/4)=0, \end{align*} we must have $W_{7m}\equiv 6R^{7m} \pmod{N_n}$ and $N_n \mid U_{7m}/U_m$ by our results at the conclusion of \S \ref{someproperties} above. It follows from Theorem \ref{primeD7} that $N_n$ must be a prime. \end{proof} \section{Computation and an example} We will now discuss how to compute, given $q$, values for $S_1$ and $S_2$ for the special extended Lucas sequences introduced in the previous section. Since $\mu =\lambda_1+\lambda_3+\lambda_5=3C_0+M_1\kappa+M_2\kappa^{*}$ and $\nu=\lambda_2+\lambda_4+\lambda_6=3C_0+M_1\kappa^{*}+M_2\kappa$, where $\kappa+\kappa^{*}=-1$ and $\kappa \kappa^{*}= 2$, we see that $\mu+\nu = 6C_0-M_1-M_2$ and $\mu\nu =9C_0^2-3C_0(M_1+M_2) +2(M_1+M_2)^2-7M_1M_2$. It follows that \begin{align} &S_1= 6C_0-M_1-M_2,\label{S1S2}\\ & S_2=(3C_0+R)^2-(3C_0+R)(M_1+M_2)+ 2(M_1+M_2)^2 -7M_1M_2-4R^2. \nonumber \end{align} Since $M_1=C_1+C_2+C_4$ and $M_2=C_3+C_5+C_6$, where \[ h(\zeta^j)= C_0+C_1 \zeta^j + C_2 \zeta^{2j}+ \dots +C_6 \zeta^{6j} \] and by (\ref{tau10}) \begin{equation}\label{hzeta} h(\zeta^j)=J(\chi^j, \chi^j)^3(\sigma_5(J(\chi^j, \chi^j)))^2 \sigma_3(J(\chi^j, \chi^j)), \end{equation} we see that we need to determine $B(i, 1)$ $(0\leq i \leq6)$, where \[ J(\chi^j, \chi^j) = \sum_{i=0}^6B(i, 1)\zeta^{ij}, \] and then use (\ref{hzeta}) to compute the coefficients $C_i$ $(i=0, 1, 2,\dots, 6)$. We have already mentioned one method for computing $B(i, 1)$ $(0\leq i\leq 6)$, but in the case of $p=7$ we know by results of Leonard and Williams \cite{LW74, LW75} that there exist integers $x_1$, $x_2,\dots, x_6$, such that \begin{equation}\label{x1} x_1\equiv 1 \pmod{7}, \end{equation} \begin{equation}\label{x2} 72q=2x_1^2+42(x_2^2+x_3^2+x_4^2) +343(x_5^2+3x_6^2), \end{equation} \begin{equation} 12x_2^2-12x_4^2+147x_5^2-441x_6^2+56x_1x_6+24x_2x_3 -24x_2x_4+48x_3x_4+98x_5x_6=0,\label{x3} \end{equation} \begin{multline} 12x_3^2-12x_4^2+49x_5^2-147x_6^2+28x_1x_5+28x_1x_6+48x_2x_3\label{x4}\\ +24x_2x_4+24x_3x_4+490x_5x_6=0. \end{multline} Also, if there is a nontrivial ($x_5$ and $x_6$ not both zero) solution to (\ref{x1})-(\ref{x4}), we can put $B(0,1)=(q-2+x_1)/7$ and $B(i, 1)=a_i+ B(0,1)$, where \begin{align*} 12a_1&=-2x_1+6x_2+7x_5+21x_6,& 12a_2&=-2x_1+6x_3+7x_5-21x_6,&\\ 12a_3&=-2x_1+6x_4-14x_5,& 12a_4&=-2x_1-6x_4-14x_5,& \\ 12a_5&=-2x_1-6x_3+7x_5-21x_6,& 12a_6&=-2x_1-6x_2+7x_5+21x_6.& \end{align*} A table of nontrivial solutions of (\ref{x1})-(\ref{x4}) for all $q\equiv 1\pmod{7}$ and $q<1000$ appears in Williams \cite{Wil1974}. For example, if $q=29$ this table lists $x_1=1$, $x_2=-2$, $x_3=-3$, $x_4=-2$, $x_5=-1$, $x_6=1$ and we find that $a_1=0$, $a_2=-4$, $a_3=0$, $a_4=2$, $a_5=-1$, $a_6=2$. Thus, in this case, we get \begin{gather*} B(0,1)=4, B(1,1)=4, B(2,1)=0, B(3,1)=4, \\ B(4,1)=6, B(5,1)=3,B(6,1)=6. \end{gather*} Williams's technique for tabulating solutions of (\ref{x1})-(\ref{x4}) requires that we first have some prime factor $\lambda$ of $q$ in $\mathcal{O}$. From this is easy to find some associate $\pi_1$ of $\lambda$ such that $J(\chi,\chi)= \pi_1\pi_4\pi_5$, and we can then compute the values of $B(i, 1)$ $(0\leq i \leq 6)$. The main problem here is that of finding some $\lambda$ (Williams used an old table of Kummer), but since $\mathcal{O}$ here is norm-Euclidean, we have an efficient algorithm for computing $\lambda$ as the greatest common divisor of $q$ and $\zeta-g^h$, where $h=(q-1)/7$. This is all explained in great detail in the Master's thesis of Caranay \cite{Car09}. As mentioned earlier \cite[Table 2]{Wil1974} provides solutions to the quadratic partition described by equations (\ref{x1})-(\ref{x4}) for all primes $q<1000$ such that $q\equiv 1\pmod{7}$. By use of this table and methods mentioned above we used a computer to calculate the values of $S_1$ and $S_2$ for each value of $q<1000$. The values for $S_1$ and $S_2$ for each $q$ are given in the table below. \begin{longtable}[H]{|c||c|c|} \hline $q$ & $S_1$ & $S_2$ \\\hline 29&$ 14965 $ &$ -1017406826 $ \\\hline 43& $ 272957 $ &$ 21858615700$ \\\hline 71& $ -1040033$ & $326748793138 $ \\\hline 113&$ 2975587 $ &$ 731201875780 $ \\\hline 127&$ 3699863 $ &$ -97933301720 $ \\\hline 197&$ -4964135 $ & $ -144000965801744 $ \\\hline 211& $ -26590621 $ &$ 179982347982148 $ \\\hline 239&$ -40502099 $ &$ 526271548075978 $ \\\hline 281&$ 29450665 $ &$ -606639016188536 $ \\\hline 337&$ -80516773 $ &$ -201075257844008 $ \\\hline 379&$ -107119195 $ &$ -5558958106936166 $ \\\hline 421&$206278211 $ & $ 10161855131659180 $ \\\hline 449&$ 213162529 $ &$ 6646761776500900 $ \\\hline 463&$ 111923783 $ &$ -13852858246492778 $ \\\hline 491&$ 95772025 $ &$ -25034062770947666 $ \\\hline 547&$ 918783725$ &$ 281059458133383676 $ \\\hline 617&$ -548612555 $ &$ 40672461475028416 $ \\\hline 631&$ 485050586 $ &$4945779937081660 $ \\\hline 659&$ -498921389 $ &$ -313908392056365122 $ \\\hline 673& $ 89928278 $ &$ -145075204278786308 $ \\\hline 701& $ -386848421$ &$-422179587542810582 $ \\\hline 743&$ 918668743 $ & $ 100597296170580172 $ \\\hline 757&$ -848906535 $ &$ -647877968552066604 $ \\\hline 827& $ -762742499 $ & $-1133671841709810608 $ \\\hline 883&$ -1331064561$ &$ -1555728581709172068 $ \\\hline 911&$ 1688430505 $ &$ 401503472607970444 $ \\\hline 953& $ 95807830 $ &$ -2154081956136898244 $ \\\hline 967& $ -2183072893$ &$ -504443123489474738 $ \\\hline \caption{Values of $S_1$ and $S_2$ for each value of $q < 1000$} \label{Tab:2}\\ \end{longtable} We next tabulate $S_3=RS_1^2-RS_2-4R^3$, where $R=q^3$ and the factorization of the corresponding $\Delta$, as this is useful in applying the theorems in the previous section. \begin{longtable}[H]{|c||c|c|c|} \hline $q$ & $S_3$ & $\Delta$ \\\hline 29& $ -2939567318323 $ & $-7^7\cdot41^2$ \\\hline 43&$ 437514319995271$&$-7^{11}$\\\hline 71& $ -30146872474620481 $& $-7^7\cdot1987^2$ \\\hline 113&$ -1350685445842116019 $& $-7^7\cdot1511^2$ \\\hline 127&$ -5937522515922653501 $& $-7^7\cdot2689^2$ \\\hline 197&$ 602743276360621183481 $& $-7^7\cdot83^2\cdot211^2$ \\\hline 211&$ -55305165497468656769 $& $-7^7\cdot50147^2$ \\\hline 239&$ -2151851544923374759681 $& $-7^7\cdot77237^2$ \\\hline 281&$ 2471371627931491315493 $& $-7^{11}$ \\\hline 337&$ 39263510618353883256277 $& $-7^7\cdot 165719^2$ \\\hline 379& $ 584554850719077350566147 $& $-7^7\cdot 174859^2$ \\\hline 421& $ -3333118453246404690503 $ &$-7^7\cdot 13^6\cdot 29^2$ \\\hline 449&$ -57018536315736139357387 $& $-7^7\cdot 71^2\cdot 743^2$ \\\hline 463& $ 82195167713946458240623 $& $-7^7\cdot 84211^2$ \\\hline 491& $ 378058321944546499176803 $ & $-7^7\cdot 84211^2$ \\\hline 547& $ 28624865948434380013954111 $& $-7^3\cdot 233617^2$ \\\hline 617& $ -247393375351235843201779 $& $-7^7\cdot113^2\cdot9941^2$ \\\hline 631& $ -6809300717975886628419368 $&$-2^6\cdot 7^7\cdot 32159^2$ \\\hline 659&$ 157152662797406306447103779 $& $-7^7\cdot41^2\cdot43^2\cdot 139^2$ \\\hline 673& $ -22381922654581541570716952 $& $-2^6\cdot 7^7 \cdot 29^2\cdot 3067^2$ \\\hline 701& $ 178907359849478481497829701 $& $-7^7\cdot13^2\cdot29191^2$ \\\hline 743& $ -12390466262878082841792637 $& $-7^7\cdot127^2\cdot2297^2$ \\\hline 757& $ 548179848685234385157559841 $& $-3^6\cdot7^7\cdot29^2\cdot911^2$ \\\hline 827& $ 887703610865697016843379663 $& $-7^7\cdot251^2\cdot2939^2$ \\\hline 883&$ 2056619378829343807794316247 $& $-3^6\cdot7^7\cdot113^2\cdot421^2$ \\\hline 911& $ -180474348382301748119990917 $& $-7^7\cdot785779^2$ \\\hline 953& $ 1143201683997473973148592744 $& $-2^6\cdot7^7\cdot71^2\cdot349^2$ \\\hline 967& $ 2264337669042185334071959087 $& $-7^7\cdot41^2\cdot 211^2\cdot421^2$ \\\hline \caption{Values of $S_3$ and $\Delta$} \label{Tab:3}\\ \end{longtable} The following two tables provide the values of the first $26$ terms of $(U_n)$ when $q=29$ and display how $(U_n)$ is analogous to the $(G_n)$ given in Table \ref{Tab:1}. Notice for $(U_n)$ the terms with subscripts divisible by $7$ tend to have many small factors belonging to no particular residue class, while the other terms satisfy Theorem \ref{analogue1}. \begin{longtable}[H]{|c||c|} \hline $n$ & $U_n$ \\\hline 0 &$ 0 $ \\\hline 1&$ 1 $ \\\hline 2&$ 63743 $ \\\hline 3&$ -178130527 $ \\\hline 4&$ -7682842247401$ \\\hline 5&$ 866655108578870099$ \\\hline 6&$ -7573915228698089372963 $\\\hline 7&$ -683990034828872027465015352$ \\\hline 8&$ -2397639392414777704627533089857$ \\\hline 9&$ -22408683611098412939809100875710563$ \\\hline 10&$ 998749219544949068374614639693399640597 $\\\hline 11&$ 86083430660651144394984616218844903262150707$ \\\hline 12&$ -744603639251416281181958726630900817210441654623$ \\\hline 13&$ 79150400226551999271197866188077762985564696853513043$ \\\hline 14&$ 29653983243922868455568386718402751132322685325618307$\\ &$67808 $\\\hline 15& $-56676326670255388502887663794303837738540570772571178$\\ &$015273923$ \\\hline 16&$ -13610155256109531810220048395596475833684665289317389$\\ &$49569426882481$ \\\hline 17&$ 900974591404181669530727185663463044965078113607329644$\\ &$8298340027827709 $\\\hline 18&$ -44081029228187672762622309308338538206556842394109679$\\ &$6845879096253052642797$ \\\hline 19&$ -88341509291730841034147800488133592750487607564356661$\\ &$92525146740054105545398437$ \\\hline 20&$ 366474365369871419422551402809377272895434714580280084$\\ &$50692950563198615258480194601$ \\\hline 21&$ 138353761716273184823923842079896157272158666142471016$\\ &$8014981086555139364346950488151000$ \\\hline 22&$ 3965553744824580859985495851105644891184644442145565571$\\ &$25010278958585288647718193415730375899$\\\hline 23& $ 5218445524433921420812498124122521433963031486363152233$\\ &$362945200754150357516907879932060934212437$ \\\hline 24& $ -176249448788214627969811858494667349579382590158574984$\\ &$2201032900330349269812604886510037926577766168223$ \\\hline 25&$ 67573954867428616031053487528800010803524068434362518$\\ &$8770153722669664064432521414254825560912252408993951 $\\\hline \caption{$U_n$ values for $q=29$} \label{Tab:4}\\ \end{longtable} \begin{longtable}[H]{|c||c|} \hline $n$ & $U_n$ \\\hline 0 & $ 0 $ \\\hline 1& $ 1 $ \\\hline 2& $63743$ \\\hline 3& $41^2\cdot105967$ \\\hline 4& $-63743\cdot120528407$ \\\hline 5&$18080861\cdot47932181359$\\\hline 6& $-41^2\cdot1217 \cdot63743 \cdot105967 \cdot548099 $\\\hline 7& $-2^3\cdot3^3 \cdot7^3 \cdot13 \cdot83 \cdot113 \cdot127 \cdot181 \cdot4327 \cdot22637 \cdot33629 $\\\hline 8& $- 63743 \cdot 2023951 \cdot 120528407 \cdot154192040407 $\\\hline 9&$-41^2 \cdot105967 \cdot352043 \cdot8608823 \cdot41508639603521 $\\\hline 10& $ 63743 \cdot199289 \cdot18080861 \cdot47932181359 \cdot90718179089 $\\\hline 11& $307 \cdot190553764987279 \cdot1471511488046122134363179119 $\\\hline 12& $-41^2 \cdot1217 \cdot1931 \cdot63743 \cdot105967 \cdot528611 \cdot548099 \cdot120528407 $\\ &$ \cdot799092083 $\\\hline 13& $911\cdot86882985978652029935453201084607862772299337929213 $ \\\hline 14& $2^6 \cdot3^3 \cdot7^3 \cdot13^3 \cdot43 \cdot83 \cdot113 \cdot127 \cdot181 \cdot461 \cdot827 \cdot1093 \cdot4327 $\\ &$ \cdot7043 \cdot8807 \cdot22637 \cdot33629 \cdot45263 \cdot63743 $ \\\hline 15& $-41^2 \cdot1259 \cdot4409 \cdot10499 \cdot33391 \cdot105967 \cdot18080861 $\\ &$ \cdot47932181359 \cdot188657402425248539369 $ \\\hline 16& $- 63743 \cdot2023951 \cdot3655681 \cdot120528407 \cdot154192040407 $\\ &$ \cdot 270791233327 \cdot573424602581099359 $ \\\hline 17& $13124329444423469738970728321$\\ &$\cdot686491904382212805092780937851068123618429$ \\\hline 18& $-41^2 \cdot1217 \cdot63743 \cdot105967 \cdot352043 \cdot548099 \cdot8608823 $\\ &$ \cdot41508639603521 \cdot462650775088987947659434651 $ \\\hline 19& $- 3191 \cdot290737 \cdot19018201 \cdot500689256569970800812621056$\\ &$004942512904540952190695696247656811 $ \\\hline 20& $ 63743 \cdot199289 \cdot18080861 \cdot120528407 \cdot 47932181359 $\\ &$ \cdot90718179089 \cdot304437209057964355560522708661126019 $ \\\hline 21& $2^3 \cdot3^6 \cdot5^3 \cdot7^3 \cdot13 \cdot41^2 \cdot43 \cdot83 \cdot113 \cdot127 \cdot181 \cdot379 \cdot4409 $\\ &$ \cdot4327 \cdot11801 \cdot12263 \cdot22637 \cdot33629 \cdot46831 \cdot85639 \cdot105967 $\\ &$\cdot116423 \cdot887492677 \cdot780831241 $ \\\hline 22& $307^3 \cdot190553764987279 \cdot1471511488046122134363179119 $\\ & $ \cdot63743 \cdot97789\cdot7841244907646133326488341710420059 $ \\\hline 23& $25179078774401811394677769123622574703\cdot207253234766$\\ &$445419497519285309564717099931568281243272800379 $ \\\hline 24& $-41^2 \cdot1217 \cdot1931\cdot 3191 \cdot63743 \cdot105967 \cdot528611 \cdot548099 $\\ &$\cdot 2023951\cdot 2425751 \cdot120528407 \cdot799092083 \cdot154192040407 $\\ &$\cdot 97986814723666418151903673$ \\\hline 25& $349^3\cdot 2801\cdot 18080861\cdot47932181359\cdot 617499370923509368494901 $\\ &$ \cdot 10604913411071362611895961734179080975557912513809901 $ \\\hline \caption{$U_n$ values factored for $q=29$} \label{Tab:5}\\ \end{longtable} Note that in this example each prime divisor $r$ of $U_n$ when $ 7 \nmid n$ is such that $r\equiv \pm1$, $\pm 17 \pmod{58}$. This is because $\pm1$ and $\pm17$ are the only values of $x \pmod{29}$ such that $x^4= x^{(29-1)/7}\equiv 1 \pmod{29}$. \begin{thebibliography}{10} \bibitem{ABCM17} M.~Abrate, S.~Barbero, U.~Cerutti, and N.~Murru, Linear divisibility sequences and {S}alem numbers, {\em Pub. Math. Debrecen} {\bf 91} (2017), 247--259. \bibitem{BEW1998} Bruce~C. Berndt, Ronald~J. Evans, and Kenneth~S. Williams, {\em Gauss and {J}acobi {S}ums}, John Wiley and Sons, 1998. \bibitem{BW00} David Bressoud and Stan Wagon, {\em {A} {C}ourse in {C}omputational {N}umber {T}heory}, Key College Publishing, 2000. \bibitem{Car09} Perlas Caranay, {O}n {R}esidue {S}ymbols and {K}ummer's {R}eciprocity {L}aw of {D}egree {S}even, Master's thesis, University of Calgary, 2009. \bibitem{Cox89} David~A. Cox, {\em {P}rimes of the {F}orm $x^2+ny^2$}, John Wiley and Sons, 1989. \bibitem{CP05} R.~Crandal and C.~Pomerance, {\em {P}rime {N}umbers: {A} {C}omputational {P}erspective, second edition}, Springer-Verlag, 2005. \bibitem{IR82} K.~Ireland and M.~Rosen, {\em {A} {C}lassical {I}ntroduction to {M}odern {N}umber {T}heory}, Springer-Verlag, 1982. \bibitem{Leh30} D.~H. Lehmer, An extended theory of {L}ucas' functions, {\em Ann. of Math.} {\bf 31} (1930), 419--448. \bibitem{LW74} P.~A. Leonard and K.~S. Williams, A {D}iophantine system of {D}ickson, {\em Rend. Accad.Naz. Lincei.} {\bf 56} (1974), 145--150. \bibitem{LW75} P.~A. Leonard and K.~S. Williams, The cyclotomic numbers of order seven, {\em Proc. Amer. Math. Soc.} {\bf 51} (1975), 295--300. \bibitem{ribenboim} P.~Ribenboim, {\em The {B}ook of {P}rime {N}umber {R}ecords}, Springer-Verlag, 2 edition, 1989. \bibitem{RW2012} E.~L. Roettger and H.~C. Williams, Public-key cryptography based on a cubic extension of the {L}ucas functions, {\em Fund. Inform.} {\bf 114} (2012), 325--344. \bibitem{RW15} E.~L. Roettger and H.~C. Williams, Some arithmetic properties of certain sequences, {\em J. Integer Sequences} {\bf 18} (2015), \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Roettger/roettger4.html}{Article 15.6.2}. \bibitem{RWG13} E.~L. Roettger, H.~C. Williams, and R.~K. Guy, Some extensions of the {L}ucas functions, in {\em {N}umber {T}heory and {R}elated {F}ields: {I}n {M}emory of {A}lf van der {P}oorten}, Vol.~43, pp.~271--311, Springer, 2013. \bibitem{RWG2015} E.~L. Roettger, H.~C. Williams, and R.~K. Guy, Some primality tests that eluded {L}ucas, {\em Des. Codes Cryptogr.} {\bf 77} (2015), 515--539. \bibitem{Slo20} N.~J.~A. Sloane et al., {T}he {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2020. \newblock Available at \url{https://oeis.org}. \bibitem{Was82} Lawrence~C. Washington, {\em {I}ntroduction to {C}yclotomic {F}ields}, Springer-Verlag, 1982. \bibitem{Whi52} A.~L. Whiteman, {C}yclotomy of {J}acobsthal sums, {\em Amer. J. Math} {\bf 74} (1952), 89--99. \bibitem{Prim_of} H.~C. Williams, The primality of {$N=2A3^n-1$}, {\em Can. Math. Bull.} {\bf 15} (1972), 585--589. \bibitem{williams} H.~C. Williams, {\em {{\'{E}}}douard {L}ucas and {P}rimality {T}esting}, Wiley-Interscience, 1998. \bibitem{WG11} H.~C. Williams and R.~K. Guy, Some fourth order linear divisibility sequences, {\em Internat. J. Number Theory} {\bf 7} (2011), 1255--1277. \bibitem{Wil1974} K.~S. Williams, A quadratic partition of primes $\equiv 1 \pmod{7}$, {\em Math. Comp} {\bf 28} (1974), 1133--1136. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B37; Secondary 11Y11, 11B50. \noindent \emph{Keywords: } linear recurrence, Lucas function, primality testing. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001351}, \seqnum{A001945}, \seqnum{A005120}, \seqnum{A006235}, \seqnum{A180510}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received February 27 2020; revised versions received March 2 2020; May 5 2020; May 6 2020. Published in {\it Journal of Integer Sequences}, May 6 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}