Some new primality criteria based on Lucas sequences.

Gaitanas Konstantinos

Department of Applied Mathematical and Physical Sciences

National Technical University of Athens

Heroon Polytechneiou Str., Zografou Campus, 15780 Athens, Greece

e-mail<EMAIL_ADDRESS>
Abstract: In this paper, we provide some novel results concerning the behavior
of $\frac{U_{kn}}{U_{k}}$ modulo ${U_{n}}$, where $(U_{n})_{n\in\mathbb{N}}$
is the Lucas sequence of the first kind. As a consequence, we obtain some
primality criteria which do not seem to appear in the literature.
Keywords: Lucas sequences, prime numbers.

##  1 Introduction

Let $a_{n}(P,Q)$ be numerical sequences, satisfying the recurrence relation

$\displaystyle a_{n+1}=P\cdot a_{n}-Q\cdot a_{n-1}\quad P,Q\in\mathbb{Z}.$

The two special cases with initial conditions $(a_{0},a_{1})=(0,1)$ and
$(a_{0},a_{1})=(2,P)$ are the _Lucas sequences_ of the first and second kind
and will be denoted by $U_{n}(P,Q)$ and $V_{n}(P,Q)$, respectively. Since the
Lucas sequences satisfy a linear recurrence relation with constant
coefficients, it is easy to obtain explicit expressions (Binet forms) from the
characteristic polynomial $p(x)=x^{2}-Px+Q$. If the discriminant of $p(x)$ is
non-zero and $\alpha,\beta$ are its roots, then

$\displaystyle U_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},\quad
V_{n}=\alpha^{n}+\beta^{n}.$

Many popular examples are recovered as particular instances of Lucas
sequences, which are important for their own sake. Probably the two most
popular are the Fibonacci and Lucas numbers (_“The two shining stars in the
vast array of integer sequences”[1]_) which are obtained from $U_{n}(1,-1)$
and $V_{n}(1,-1)$, respectively. Other well-known examples include the Pell,
Mersenne, Jacobsthal and Balancing numbers. For more material that might
satisfy the reader’s curiosity we refer to the book of Paulo Ribenboim _“My
Numbers, My Friends”_ [2]. The main purpose of this paper is to present some
congruence relations which hold among the terms of $(U_{n})_{n\in\mathbb{N}}$
and eventually provide some primality criteria which are aimed to serve mostly
for theoretical purposes. We emphasize that the congruences we obtain
throughout this paper seem to be of independent interest 111It is possible
that some of these congruences have already appeared somewhere in the vast
mathematical literature. For the convenience of the reader, we provide
detailed proofs to make the paper self-contained.

##  2 Notation and Preliminaries

This section is a quick-reference guide to the notation and background
information that will be assumed throughout this paper.
We denote by $\varphi(n)$ Euler’s totient function, which counts the positive
integers not greater than $n$, that are relatively prime to $n$. We will also
use without proof the fact that the number of positive integers $k$ less than
$n$ with $\gcd(n,k)=d$, is exactly $\varphi(\frac{n}{d})$. Legendre’s symbol
is defined as

$\displaystyle\left(\frac{a}{p}\right)=\begin{cases}1,&\text{if }a\text{ is a
quadratic residue modulo }p\text{ and }a\not\equiv 0\pmod{p},\\\ -1,&\text{if
}a\text{ is a quadratic nonresidue modulo }p,\\\ 0,&\text{if }a\equiv
0\pmod{p}.\end{cases}.$

In addition, we mention some well-known facts about Lucas sequences. For the
sake of brevity, we omit their proofs since they are obtained without much
effort and can be found in various mathematical contexts, such as [2].

######  Theorem 2.1.

Let $D=P^{2}-4Q$. The following hold true:

  1. 2.1.1.

$U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}$.

  2. 2.1.2.

$V_{n}=2U_{n+1}-PU_{n}$.

  3. 2.1.3.

$V_{n}^{2}-DU_{n}^{2}=4Q^{n}$.

Moreover, for the rest of the paper we will assume that $P$ and $Q$ are
coprime. In this way, we ensure that $(U_{n})$ is a _strong divisibility
sequence_ which means that $\gcd(U_{x},U_{y})=U_{\gcd(x,y)}$. This evidently
implies that if $y\mid x$, then $U_{y}\mid U_{x}$. This is something which
will be frequently used. As for other prerequisites, the reader is expected to
be familiar only with basic congruence rules and Bézout’s identity, which
states that if $\gcd(x,y)=d$, then there are $s,q\in\mathbb{Z}$ such that
$sx+qy=d$.

##  3 Two important lemmas.

In this section, we provide two lemmas which will be the key tools for the
proof of Theorem (4.1). We note that a version of the first lemma already
appears in [3], in the proof of Theorem 4.1.

######  Lemma 3.1.

Let $k\in\mathbb{N^{*}}$. The following holds true:

$\frac{U_{kn}}{U_{k}}\equiv\begin{cases}n\cdot
Q^{\frac{k(n-1)}{2}}\pmod{U_{k}},&\text{if}\quad n\equiv 1\pmod{2},\\\
nU_{k+1}\cdot Q^{\frac{k(n-2)}{2}}\pmod{U_{k}},&\text{if}\quad n\equiv
0\pmod{2}.\\\ \end{cases}$ (1)

###### Proof.

We prove this by applying induction on $n$. We note that (1) obviously holds
true for $n=0$ and $n=1$. Suppose that it holds true for every natural number
not greater than $n$, with $n\geq 2$. From (2.1.1) for $m=kn$ and $n=k$, we
obtain

$\frac{U_{k(n+1)}}{U_{k}}=\frac{U_{kn}}{U_{k}}V_{k}-Q^{k}\frac{U_{k(n-1)}}{U_{k}}.$
(2)

Assume that $n+1$ is odd. Then $n$ is even and $n-1$ is also odd. Hence, using
the induction hypothesis the last equation yields

$\displaystyle\frac{U_{k(n+1)}}{U_{k}}\equiv
nU_{k+1}Q^{\frac{k(n-2)}{2}}V_{k}-Q^{k}(n-1)Q^{\frac{k(n-2)}{2}}\pmod{U_{k}}.$

From (2.1.2), $V_{k}\equiv 2U_{k+1}\pmod{U_{k}}$. Thus,
$nU_{k+1}V_{k}\equiv\frac{n}{2}\cdot
2U_{k+1}V_{k}\equiv\frac{n}{2}V_{k}^{2}\equiv 2nQ^{k}\pmod{U_{k}}$. The last
congruence holds, since from (2.1.3), $V_{k}^{2}\equiv 4Q^{k}\pmod{U_{k}}$. It
follows that

$\displaystyle\frac{U_{k(n+1)}}{U_{k}}\equiv
2nQ^{k}Q^{\frac{k(n-2)}{2}}-(n-1)Q^{\frac{k(n-2)}{2}}Q^{k}\equiv(n+1)Q^{\frac{kn}{2}}\pmod{U_{k}}$

which proves the claim if $n+1$ is odd.
If $n+1$ is even, then $n$ is odd and $n-1$ is even. From the induction
hypothesis, (2) yields

$\displaystyle\frac{U_{k(n+1)}}{U_{k}}\equiv n\cdot
Q^{\frac{k(n-1)}{2}}V_{k}-Q^{k}(n-1)U_{k+1}Q^{\frac{k(n-3)}{2}}\pmod{U_{k}}.$

But $V_{k}\equiv 2U_{k+1}\pmod{U_{k}}$. Therefore,

$\displaystyle\frac{U_{k(n+1)}}{U_{k}}\equiv 2n\cdot
Q^{\frac{k(n-1)}{2}}U_{k+1}-Q^{k}(n-1)U_{k+1}Q^{\frac{k(n-3)}{2}}\equiv(n+1)U_{k+1}Q^{\frac{k(n-1)}{2}}\pmod{U_{k}}$

which proves the claim if $n+1$ is even. ∎

We use similar arguments to obtain our second result.

######  Lemma 3.2.

Let $k\in\mathbb{N}$. The following holds true:

$U_{kn+1}\equiv\begin{cases}U_{k+1}Q^{\frac{k(n-1)}{2}}\pmod{U_{k}},&\text{if}\quad
n\equiv 1\pmod{2},\\\ Q^{\frac{kn}{2}}\pmod{U_{k}},&\text{if}\quad n\equiv
0\pmod{2}.\\\ \end{cases}$ (3)

###### Proof.

We prove this again by applying induction on $n$. It is evident that (3) holds
true for $n=0$ and $n=1$. Suppose that it holds true for every natural number
not greater than $n$, with $n\geq 2$. From (2.1.1) for $m=kn$ and $n=k+1$, we
obtain

$U_{k(n+1)+1}=U_{kn}V_{k+1}-Q^{k+1}U_{k(n-1)-1}\equiv-Q^{k+1}U_{k(n-1)-1}\mod{U_{k}}$
(4)

since $U_{k}\mid U_{kn}$. From definition,
$U_{k(n-1)+1}=PU_{k(n-1)}-QU_{k(n-1)-1}$. But $U_{k}\mid U_{k(n-1)}$, which
implies that $-QU_{k(n-1)-1}\equiv U_{k(n-1)+1}\pmod{U_{k}}$. Therefore, from
(4) we deduce that

$U_{k(n+1)+1}\equiv Q^{k}U_{k(n-1)+1}\pmod{U_{k}}.$ (5)

Assume that $n+1$ is even. Then $n-1$ is also even and from the induction
hypothesis the last congruence yields $U_{k(n+1)+1}\equiv
Q^{k}Q^{\frac{k(n-1)}{2}}\equiv Q^{\frac{k(n+1)}{2}}\pmod{U_{k}}$.
If $n+1$ is odd, then $n-1$ is also odd. From the induction hypothesis and (5)
we deduce that $U_{k(n+1)+1}\equiv Q^{k}U_{k+1}Q^{\frac{k(n-2)}{2}}\equiv
U_{k+1}Q^{\frac{kn}{2}}\pmod{U_{k}}$. This completes the proof. ∎

For the sake of brevity, it will be convenient to present the previous results
without taking into consideration the parity of $n$. Therefore, we introduce a
function $a(x)$ defined as 222One may take for example
$a(x)=\cos^{2}(\frac{\pi x}{2})$.

$\displaystyle a(x)=\begin{cases}0,&\text{if}\quad x\equiv 1\pmod{2},\\\
1,&\text{if}\quad x\equiv 0\pmod{2}.\\\ \end{cases}$

In this way, we obtain the following Corollary.

######  Corollary 3.3.

The following hold true:

$\frac{U_{kn}}{U_{k}}\equiv n\left(U_{k+1}\right)^{a(n)}\cdot
Q^{\frac{k(n-a(n)-1)}{2}}\pmod{U_{k}}.$ (6)
$U_{kn+1}\equiv\left(U_{k+1}\right)^{1-a(n)}\cdot
Q^{\frac{k(n+a(n)-1)}{2}}\pmod{U_{k}}.$ (7)

The previous Corollary is interesting on its own; we briefly describe two
applications:
From (6) we easily obtain that

$\displaystyle U_{kn}=U_{k}\cdot n\left(U_{k+1}\right)^{a(n)}\cdot
Q^{\frac{k(n-a(n)-1)}{2}}\pmod{U_{k}^{2}}.$

From this, it is straightforward to see that if $n^{i}\mid U_{k}$, then
$n^{i+1}\mid U_{kn}$. This result has already appeared several times in the
literature (for example, in §3 of [2], _“The law of repetition”_), especially
when $n$ is a prime number.
In addition, from the identity $U_{m+n}=U_{m+1}U_{n}-QU_{m}U_{n-1}$ for $m=kn$
and $n=r$ , we obtain that $U_{kn+r}=U_{kn+1}U_{r}-QU_{kn}U_{r-1}$. From (7)
and the fact that $U_{k}\mid U_{kn}$, we deduce the more general congruence:

$\displaystyle U_{kn+r}\equiv U_{r}\left(U_{k+1}\right)^{1-a(n)}\cdot
Q^{\frac{k(n+a(n)-1)}{2}}\pmod{U_{k}}.$

##  4 Main results.

In this section, we state our main results and provide some key proof
techniques and insights. We recall that the Lucas sequence of the first kind
is a strong divisibility sequence, which means that
$\gcd(U_{n},U_{k})=U_{\gcd(n,k)}$.

######  Theorem 4.1.

Let $k\in\mathbb{N}^{*}$ and $\gcd(n,k)=d$. Then

$\displaystyle\frac{U_{kn}}{U_{k}}\equiv\begin{cases}dU_{d+1}\cdot\frac{U_{n}}{U_{d}}\cdot
Q^{\frac{kn-k-n}{2}}\pmod{U_{n}},&\text{if}\quad n,k\quad\text{are even
and}\quad\frac{n}{d},\frac{k}{d}\quad\text{are odd},\\\
d\cdot\frac{U_{n}}{U_{d}}\cdot Q^{\frac{kn-
k-n+d}{2}}\pmod{U_{n}},&\text{otherwise}.\\\ \end{cases}$

###### Proof.

Suppose that

$\frac{U_{kn}}{U_{k}}=r+M\cdot U_{n}$ (8)

where $0\leq r\leq U_{n}-1$ and $M\in\mathbb{N}$. This is equivalent to
$U_{kn}=rU_{k}+MU_{n}U_{k}$. Since $U_{n}\mid U_{kn}$ and $U_{n}\mid
kMU_{n}U_{k}$, we obtain $U_{n}\mid rU_{k}$. But $\gcd(U_{n},U_{k})=U_{d}$,
which implies that $\gcd(\frac{U_{n}}{U_{d}},\frac{U_{k}}{U_{d}})=1$. Thus,
$\frac{U_{n}}{U_{d}}\mid r$, so $r=c\cdot\frac{U_{n}}{U_{d}}$ for some
$c\in\mathbb{N}$. Hence,

$\frac{U_{kn}}{U_{k}}=c\cdot\frac{U_{n}}{U_{d}}+MU_{n}.$ (9)

From (7) for $k=d$ and $n=\frac{k}{d}$, we obtain

$U_{k+1}\equiv(U_{d+1})^{1-a(k/d)}\cdot
Q^{\frac{d(k/d+a(k/d)-1)}{2}}\pmod{U_{k}}.$ (10)

Thus, (6) implies that

$\frac{U_{kn}}{U_{k}}\equiv n(U_{d+1})^{a(n)(1-a(k/d))}\cdot
Q^{\frac{da(n)a(k/d)-da(n)+kn-k}{2}}\pmod{U_{k}}.$ (11)

Also from (6), for $k=d$ and $n=\frac{n}{d}$, we obtain

$\frac{U_{n}}{U_{d}}\equiv\frac{n}{d}(U_{d+1})^{a(n/d)}\cdot
Q^{\frac{d(n/d-a(n/d)-1)}{2}}\pmod{U_{d}}.$ (12)

Since $n\equiv k\equiv 0\pmod{d}$, then $U_{n}\equiv U_{k}\equiv
0\pmod{U_{d}}$. Thus, (9), (11) and (12) imply that

$\displaystyle n(U_{d+1})^{a(n)(1-a(k/d))}\cdot
Q^{\frac{da(n)a(k/d)-da(n)+kn-k}{2}}\equiv c\frac{n}{d}(U_{d+1})^{a(n/d)}\cdot
Q^{\frac{d(n/d-a(n/d)-1)}{2}}\pmod{U_{d}}.$

Furthermore, we observe 333 From definition, $U_{d+1}=P\cdot U_{d}-Q\cdot
U_{d-1}$. If $\delta\mid U_{d}$ and $\delta\mid Q$, then $\delta\mid U_{d+1}$.
Since $\gcd(d,d+1)=1$, then $\gcd(U_{d},U_{d+1})=1$, which implies that
$\delta=1$. that $\gcd(Q,U_{d})=1$ and $\gcd(U_{d},U_{d+1})=1$. As a
consequence, we can rewrite the previous congruence in the form:

$n(U_{d+1})^{a(n)(1-a(k/d))-a(n/d)}\cdot
Q^{\frac{da(n)a(k/d)-da(n)+da(n/d)+kn-k-n+d}{2}}\equiv
c\frac{n}{d}\pmod{U_{d}}.$ (13)

Moving forward, we multiply both sides of (9) by $\frac{U_{k}}{U_{n}}$. This
yields

$\displaystyle\frac{U_{kn}}{U_{n}}=c\frac{U_{k}}{U_{d}}+MU_{k}.$

Following the same steps, (by exchanging the roles of $k$ and $n$) we conclude
that

$\frac{U_{kn}}{U_{n}}\equiv k(U_{d+1})^{a(k)(1-a(n/d))}\cdot
Q^{\frac{da(k)a(n/d)-da(k)+kn-n}{2}}\pmod{U_{d}}.$ (14)

and

$\frac{U_{k}}{U_{d}}\equiv\frac{k}{d}(U_{d+1})^{a(k/d)}\cdot
Q^{\frac{d(k/d-a(k/d)-1)}{2}}\pmod{U_{d}}.$ (15)

Again, since $\gcd(Q,U_{d})=\gcd(U_{d},U_{d+1})=1$, we deduce that

$k(U_{d+1})^{a(k)(1-a(n/d))-a(k/d)}\cdot
Q^{\frac{da(k)a(n/d)-da(k)+da(k/d)+kn-k-n+d}{2}}\equiv
c\frac{k}{d}\pmod{U_{d}}.$ (16)

The previous results indicate that the rest of the proof falls naturally into
four cases:

######  Case 1.

_The number $n$ is odd._
This implies that $d$ is odd (and so is $\frac{n}{d}$). Hence, $k$ and
$\frac{k}{d}$ have the same parity. Therefore,

$\displaystyle a(n)(1-a(k/d))-a(n/d)=0,$ $\displaystyle
da(n)a(k/d)-da(n)+da(n/d)=0,$ $\displaystyle
a(k)(1-a(n/d))-a(k/d)=a(k)-a(k/d)=0,$ $\displaystyle
da(k)a(n/d)-da(k)+da(k/d)=d(-a(k)+a(k/d))=0.$

######  Case 2.a.

_The number $n$ is even and $k$ is odd._
This implies that $d$ and $\frac{k}{d}$ are odd but $\frac{n}{d}$ is even.
Therefore,

$\displaystyle a(n)(1-a(k/d))-a(n/d)=a(n)-a(n/d)=0,$ $\displaystyle
da(n)a(k/d)-da(n)+da(n/d)=-d(a(n)-a(n/d))=0,$ $\displaystyle
a(k)(1-a(n/d))-a(k/d)=0,$ $\displaystyle da(k)a(n/d)-da(k)+da(k/d)=0.$

######  Case 2.b.

_Both $n$ and $k$ are even and $\frac{n}{d},\frac{k}{d}$ have different
parity._
Since $\frac{n}{d},\frac{k}{d}$ have different parity, then $a(n/d)+a(k/d)=1$.
Therefore,

$\displaystyle a(n)(1-a(k/d))-a(n/d)=1-\left(a(k/d)+a(n/d)\right)=0,$
$\displaystyle da(n)a(k/d)-da(n)+da(n/d)=d(a(k/d)+a(n/d)-1)=0,$ $\displaystyle
a(k)(1-a(n/d))-a(k/d)=1-\left(a(n/d)+a(k/d)\right)=0,$ $\displaystyle
da(k)a(n/d)-da(k)+da(k/d)=d(a(n/d)-1+a(k/d))=0.$

In all these cases, we get

$k\cdot Q^{\frac{kn-k-n+d}{2}}\equiv c\frac{k}{d}\pmod{U_{d}}.$ (17)

and

$n\cdot Q^{\frac{kn-k-n+d}{2}}\equiv c\frac{n}{d}\pmod{U_{d}}.$ (18)

For the convenience of notation, we let $Q^{\frac{kn-k-n+d}{2}}=x$.
Congruences (17) and (18) imply that
$\frac{k}{d}(dx-c)\equiv\frac{n}{d}(dx-c)\equiv 0\pmod{U_{d}}$. We claim that
$dx-c\equiv 0\pmod{U_{d}}$. Indeed, since $\gcd(\frac{n}{d},\frac{k}{d})=1$,
Bezout’s identity implies that there are $s,q\in\mathbb{Z}$ such that
$s\cdot\frac{n}{d}+q\cdot\frac{k}{d}=1$. Therefore,

$\displaystyle s\cdot\frac{n}{d}(dx-c)+q\cdot\frac{k}{d}(dx-c)=dx-c.$

Thus, $dx-c\equiv 0\pmod{U_{d}}$. Consequently, $U_{n}\frac{dx-c}{U_{d}}$ is
an integer multiple of $U_{n}$ which is equivalent to
$c\frac{U_{n}}{U_{d}}\equiv dx\frac{U_{n}}{U_{d}}\pmod{U_{n}}$. Since
$\frac{U_{kn}}{U_{k}}\equiv c\frac{U_{n}}{U_{d}}\pmod{U_{n}}$, it follows that

$\displaystyle\frac{U_{kn}}{U_{k}}\equiv d\cdot\frac{U_{n}}{U_{d}}\cdot
Q^{\frac{kn-k-n+d}{2}}\pmod{U_{n}}.$

######  Case 2.c.

_Both $n$ and $k$ are even and $\frac{n}{d},\frac{k}{d}$ are odd444There is no
other case to consider, since $\frac{n}{d},\frac{k}{d}$ cannot be both even
since they are coprime.._
In this case, we observe that

$\displaystyle a(n)(1-a(k/d))-a(n/d)=1,$ $\displaystyle
da(n)a(k/d)-da(n)+da(n/d)=da(k/d)-d+da(n/d)=-d,$ $\displaystyle
a(k)(1-a(n/d))-a(k/d)=1,$ $\displaystyle da(k)a(n/d)-da(k)+da(k/d)=-d.$

Hence, from (13) and (16) we deduce that

$\displaystyle kU_{d+1}\cdot Q^{\frac{kn-k-n}{2}}\equiv
c\frac{k}{d}\pmod{U_{d}}.$

and

$\displaystyle nU_{d+1}\cdot Q^{\frac{kn-k-n}{2}}\equiv
c\frac{n}{d}\pmod{U_{d}}.$

Let $U_{d+1}\cdot Q^{\frac{kn-k-n}{2}}=y$. Using the same technique as before,
we obtain that $U_{n}\frac{dy-c}{U_{d}}$ is an integer multiple of $U_{n}$,
which implies $\frac{U_{kn}}{U_{k}}\equiv c\frac{U_{n}}{U_{d}}\equiv
dy\frac{U_{n}}{U_{d}}\pmod{U_{n}}$. It follows that

$\displaystyle\frac{U_{kn}}{U_{k}}\equiv dU_{d+1}\cdot\frac{U_{n}}{U_{d}}\cdot
Q^{\frac{kn-k-n}{2}}\pmod{U_{n}}.$

This completes the proof. ∎

We observe that if $Q=\pm 1$, we can simplify the shape of the congruences
which appear in Corollary (3.3) and Theorem(4.1). There is a plethora of
examples of Lucas sequences $U_{n}(P,\pm 1)$. In order to limit the length of
this paper, we chose the Fibonacci sequence $(F_{n})_{n}$ which is obtained
from $U_{n}(1,-1)$ and the Mersenne numbers, which are numbers of the form
$U_{n}(3,2)=2^{n}-1$ to demonstrate the application of our results.

######  Theorem 4.2.

The following hold true:

$\displaystyle
F_{kn+1}\equiv\begin{cases}F_{k+1}(-1)^{\frac{k(n-1)}{2}}\pmod{F_{k}},&\text{if}\quad
n\equiv 1\pmod{2},\\\ (-1)^{\frac{kn}{2}}\pmod{F_{k}},&\text{if}\quad n\equiv
0\pmod{2}.\\\ \end{cases}$ (19)
$\displaystyle\frac{F_{kn}}{F_{k}}\equiv\begin{cases}n\cdot(-1)^{\frac{k(n-1)}{2}}\pmod{F_{k}},&\text{if}\quad
n\equiv 1\pmod{2},\\\
nF_{k+1}\cdot(-1)^{\frac{k(n-2)}{2}}\pmod{F_{k}},&\text{if}\quad n\equiv
0\pmod{2}.\\\ \end{cases}$ (20)
$\displaystyle\frac{F_{kn}}{F_{k}}\equiv\begin{cases}d\cdot\frac{F_{n}}{F_{d}}\cdot
F_{d+1}(-1)^{\frac{kn-k-n}{2}}\pmod{F_{n}},&\text{if}\quad n,k\quad\text{are
even and}\quad\frac{n}{d},\frac{k}{d}\quad\text{are odd},\\\
d\cdot\frac{F_{n}}{F_{d}}\cdot(-1)^{\frac{kn-
k-n+d}{2}}\pmod{F_{n}},&\text{otherwise}.\end{cases}$ (21)
$\displaystyle\frac{2^{kn}-1}{2^{k}-1}\equiv
d\cdot\frac{2^{n}-1}{2^{d}-1}\pmod{2^{n}-1}.$ (22)

###### Proof.

The first three parts follow immediately from Corollary (3.3) and Theorem(4.1)
if we substitute $Q=-1$. In order to prove (22), we substitute $Q=2$ into
Theorem (4.1) and treat separately the two cases:
_If $n,k$ are even and $\frac{n}{d},\frac{k}{d}$ are odd_:
It is evident that $d$ and $\frac{n}{d}+\frac{k}{d}$ are even. Thus,

$\displaystyle\frac{kn-
k-n}{2}=d\cdot\frac{(d\cdot\frac{n}{d}\frac{k}{d}-(\frac{k}{d}+\frac{n}{d}))}{2}\equiv
0\pmod{d}.$

This implies that $2^{\frac{kn-k-n}{2}}\equiv 1\pmod{2^{d}-1}$. Furthermore,
$U_{d+1}=2^{d+1}-1\equiv 1\pmod{2^{d}-1}$. We conclude that

$\displaystyle\frac{2^{kn}-1}{2^{k}-1}\equiv
d(2^{d+1}-1)\frac{2^{n}-1}{2^{d}-1}2^{\frac{kn-k-n}{2}}\equiv
d\cdot\frac{2^{n}-1}{2^{d}-1}\pmod{2^{n}-1}.$

_Otherwise_ :
Observe that

$\displaystyle\frac{kn-
k-n+d}{2}=d\cdot\frac{d\frac{n}{d}\frac{k}{d}-\frac{k}{d}-\frac{n}{d}+1}{2}.$

If $d$ is odd, then obviously
$d\cdot\frac{d\frac{n}{d}\frac{k}{d}-\frac{k}{d}-\frac{n}{d}+1}{2}\equiv
0\pmod{d}$.
If $d$ is even, then both $n$ and $k$ must be even and
$\frac{k}{d},\frac{n}{d}$ must have different parity. (We already considered
above the case where both are odd.) Therefore,
$d\frac{n}{d}\frac{k}{d}-\frac{k}{d}-\frac{n}{d}+1\equiv 0\pmod{2}$, which
implies that
$d\cdot\frac{d\frac{n}{d}\frac{k}{d}-\frac{k}{d}-\frac{n}{d}+1}{2}\equiv
0\pmod{d}$. In any case, $2^{\frac{kn-k-n+d}{2}}\equiv 1\pmod{2^{d}-1}$ holds
true. It follows that

$\displaystyle\frac{2^{kn}-1}{2^{k}-1}\equiv
d\cdot\frac{2^{n}-1}{2^{d}-1}2^{\frac{kn-k-n+d}{2}}\equiv
d\cdot\frac{2^{n}-1}{2^{d}-1}\pmod{2^{n}-1}.$

This completes the proof. ∎

We would like to note that the behavior of $\frac{F_{kn}}{F_{k}}$ and
$F_{kn+1}$ modulo $F_{k}$ goes back at least as far as [4], where the author
obtains that $\frac{F_{kn}}{F_{k}}\equiv n(F_{k+1})^{n-1}\pmod{F_{k}}$ and
$F_{kn+1}\equiv(F_{k+1})^{n}\pmod{F_{k}}$. Since $n(F_{k+1})^{n-1}$ and
$(F_{k+1})^{n}$ are much larger than the moduli we obtained, we consider (19)
and (20) to be much more illuminating.

###  4.1 Criteria of Primality.

######  Theorem 4.3.

The congruence

$\displaystyle\sum_{k=1}^{n-1}\frac{2^{kn}-1}{2^{k}-1}\equiv 0\pmod{2^{n}-1}$

holds true, if and only if $n$ is prime.

###### Proof.

From (22), we observe that

$\displaystyle\sum_{k=1}^{n-1}\frac{2^{kn}-1}{2^{k}-1}\equiv\sum_{\begin{subarray}{c}\gcd(n,k)=d\\\
1\leq k<n\end{subarray}}d\cdot\frac{2^{n}-1}{2^{d}-1}\pmod{2^{n}-1}.$

The number of positive integers $k$ less than $n$ with $\gcd(n,k)=d$, is
exactly $\varphi(\frac{n}{d})$. Thus,

$\sum_{k=1}^{n-1}\frac{2^{kn}-1}{2^{k}-1}\equiv(2^{n}-1)\sum_{\begin{subarray}{c}d\mid
n\\\ 1\leq
d<n\end{subarray}}\frac{d\cdot\varphi(\frac{n}{d})}{2^{d}-1}\pmod{2^{n}-1}.$
(23)

It suffices to prove that the last sum is an integer if and only if $n$ is
prime.
If $n$ is prime, there is only one divisor $d<n$ of $n$, namely $d=1$ and the
sum is equal to $\frac{1\cdot\varphi(n)}{2^{1}-1}=n-1$.
If $n$ is composite, we denote by $D$ the largest proper divisor of $n$. From
Theorem (4.4), we know that $2^{D}-1$ has a primitive prime divisor $p$,
unless $D=6$. It is relatively easy to show that $n=12$ is the only number
with $D=6$, and $\sum_{k=1}^{11}\frac{2^{k\cdot 12}-1}{2^{k}-1}\equiv
3354\not\equiv 0\pmod{2^{12}-1}$. Therefore, we suppose that $D\neq 6$. We
denote by $L$ the least common multiple of all the elements of
$\\{2^{d}-1,1\leq d<n\\}$ and $d_{1},d_{2},\ldots,D$ all the proper divisors
of $n$. Hence,

$\sum_{\begin{subarray}{c}d\mid n\\\ 1\leq
d<n\end{subarray}}\frac{d\cdot\varphi(\frac{n}{d})}{2^{d}-1}=\frac{d_{1}\varphi(\frac{n}{d_{1}})\left(\frac{L}{2^{d_{1}}-1}\right)+d_{2}\varphi(\frac{n}{d_{2}})\left(\frac{L}{2^{d_{2}}-1}\right)+\ldots+D\varphi(\frac{n}{D})\left(\frac{L}{2^{D}-1}\right)}{L}.$
(24)

We briefly show that $p\nmid D\varphi(\frac{n}{D})$. From Fermat’s little
theorem we know that $p\mid 2^{p-1}-1$, which implies that $p>D$. Hence,
$p\nmid D$. Furthermore, since $D$ is the largest proper divisor of $n$, then
$\frac{n}{D}$ is the least prime divisor of $n$. This implies that
$\varphi(\frac{n}{D})=\frac{n}{D}-1$ and $\frac{n}{D}\leq D$. Thus,
$\varphi(\frac{n}{D})<D<p$, which shows that $p\nmid\varphi(\frac{n}{D})$. By
this reasoning, the sum in (24) is not an integer, since the denominator and
every summand in the numerator is divisible by $p$, except
$D\varphi(\frac{n}{D})\left(\frac{L}{2^{D}-1}\right)$. This completes the
proof. ∎

Before proceeding any further, we would like to mention two well-known
theorems which will be needed in the proof of our last main result. In 1913,
Carmichael [5] showed that almost all terms of a Lucas sequence of the first
kind have a _primitive prime divisor_. In particular he proved the following
Theorem:

######  Theorem 4.4.

Suppose that $P^{2}-4Q>0$. If $n\neq 1,2,6$, $U_{n}$ has a prime divisor $p$,
such that $p\nmid U_{m}$, for every $m<n$. The only exception is
$U_{12}(1,-1)=F_{12}=144$.

We will also make use of the following theorem which can be found in various
contexts, such as [2]:

######  Theorem 4.5.

If $p$ is an odd prime, $p\neq 5$, then $p\mid
F_{p-\left(\frac{5}{p}\right)}$, where $\left(\frac{a}{p}\right)$ denotes the
Legendre symbol.

Roughly speaking, this theorem shows that if $p$ is the primitive prime
divisor of $F_{n}$, then $p\geq n-1$. To see why this is true, observe that
$\left(\frac{5}{p}\right)=\pm 1$ if $p\neq 5$, and
$\left(\frac{5}{p}\right)=0$ if $p=5$.

######  Theorem 4.6.

Suppose that $n\equiv 1\pmod{4}$ and $n\not\in\\{9,25\\}$. Then

$\sum_{k=1}^{n-1}\frac{F_{kn}}{F_{k}}\equiv 0\pmod{F_{n}}$ (25)

holds true, if and only if $n$ is prime.

###### Proof.

This theorem may be proved in much the same way as Theorem(4.3). From (21), we
get

$\displaystyle\sum_{k=1}^{n-1}\frac{F_{kn}}{F_{k}}\equiv
F_{n}\cdot\sum_{\begin{subarray}{c}\gcd(n,k)=d\\\ 1\leq
d<n\end{subarray}}\frac{d}{F_{d}}(-1)^{\frac{kn-k-n+d}{2}}\pmod{F_{n}}.$

It will be convenient to substitute $-1$ with $i^{2}$, the imaginary unit. In
this way, we may write $(-1)^{\frac{kn-k-n+d}{2}}=i^{d-1}(i^{n-1})^{(k-1)}$.
Consequently, it suffices to prove that

$\displaystyle\sum_{\begin{subarray}{c}\gcd(n,k)=d\\\ 1\leq
d<n\end{subarray}}\frac{d}{F_{d}}i^{d-1}(i^{n-1})^{(k-1)}=\sum_{\begin{subarray}{c}d\mid
n\\\ 1\leq
d<n\end{subarray}}\frac{di^{d-1}}{F_{d}}\sum_{\begin{subarray}{c}\gcd(n,k)=d\end{subarray}}(i^{n-1})^{(k-1)}$

is an integer if and only if $n$ is prime. If $n\equiv 1\pmod{4}$, then
$i^{n-1}=1$, which implies that
$\sum_{\begin{subarray}{c}\gcd(n,k)=d\end{subarray}}(i^{n-1})^{(k-1)}$ is
equal to $\varphi(\frac{n}{d})$. It is evident that if $n$ is prime, the sum
is an integer, namely $\varphi(n)=n-1$. Suppose that $n$ is composite, $D$ is
its largest proper divisor and $p$ is the primitive prime divisor of $F_{D}$
555Since $n$ is odd, we do not need to consider the exceptions mentioned in
Theorem (4.4).. As is clear from the previous arguments, it will be enough to
show that

$\displaystyle p\nmid Di^{D-1}\varphi\left(\frac{n}{D}\right).$

Recall that from Theorem (4.5), we know that $p\geq D-1$. Thus, if $p\mid D$,
then $p=D$. This implies that $p\mid F_{p}$, which is possible only if
$p=D=5$. The only composite number congruent to $1$ modulo $4$, having $D=5$,
is $25$. From hypothesis $n\neq 25$, thus, $p\nmid D$.
Suppose that $p\mid\varphi(\frac{n}{D})$. Then,

$\displaystyle p\leq\varphi\left(\frac{n}{D}\right)=\frac{n}{D}-1\leq D-1\leq
p.$

This shows that $p=D-1$ and $\frac{n}{D}-1=D-1$. The last equality implies
that $n=D^{2}$, which is possible only if $D$ is prime. Hence, $p,D$ are
consecutive primes which yields $p=2,D=3,n=9$. From hypothesis $n\neq 9$,
thus, $p\nmid\varphi(\frac{n}{D})$. This completes the proof. ∎

######  Remark 1.

We pause now to record an observation that follows readily from the
computations made above; if $n\equiv 3\pmod{4}$, then (25) holds true,
regardless of whether $n$ is prime. To see this, observe that $i^{n-1}=-1$,
thus

$\displaystyle\sum_{\begin{subarray}{c}\gcd(n,k)=d\end{subarray}}(i^{n-1})^{(k-1)}=-\sum_{\gcd(n,k)=d}(-1)^{d\cdot\frac{k}{d}}=-\sum_{\gcd(\frac{n}{d},\frac{k}{d})=1}(-1)^{\frac{k}{d}}.$

The last equality holds, since $d$ is odd. In addition, we note that
$\frac{k}{d}$ denotes a number which is coprime to $\frac{n}{d}$. If
$\gcd(\frac{k}{d},\frac{n}{d})=1$, then
$\gcd(\frac{n}{d}-\frac{k}{d},\frac{n}{d})=1$. But $\frac{n}{d}-\frac{k}{d}$
and $\frac{k}{d}$ have opposite parity since their sum is $\frac{n}{d}\equiv
1\pmod{2}$, which means that
$(-1)^{\frac{n}{d}-\frac{k}{d}}+(-1)^{\frac{k}{d}}=0$. Hence, for every $d$ we
have a sum of pairs which vanishes, and the result follows.

## References

  * [1]  Thomas Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, New York, 2001.
  * [2]  Ribenboim, P., My Numbers, My Friends: Popular Lectures on Number Theory (Springer, Berlin, 2000).https://doi.org/10.1007/b98892
  * [3]  Williams, H.C., Guy, R.K. Some fourth-order linear divisibility sequences, International Journal of Number Theory Vol. 07, No. 05, pp. 1255-1277 (2011). https://doi.org/10.1142/S1793042111004587.
  * [4]  Mansur S. Boase, A Result About the Primes Dividing Fibonacci Numbers, The Fibonacci Quarterly, 39.5 (2001) 386.
  * [5]  Carmichael, R. D. (1913). On the Numerical Factors of the Arithmetic Forms $\alpha^{n}\pm\beta^{n}$. Annals of Mathematics, 15(1/4), 30–48. https://doi.org/10.2307/1967797