\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\def\amod#1 #2{#1\ ({\rm mod}\ #2)}
\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 Further Generalization of a Congruence of \\
\vskip .1in
Wolstenholme
}
\vskip 1cm
\large
Christian Ballot \\
L.M.N.O., CNRS UMR 6139\\
Universit\'e de Caen \\
F-14032 Caen Cedex \\
France \\
\href{mailto:christian.ballot@unicaen.fr}{\tt christian.ballot@unicaen.fr}\\
\end{center}
\vskip .2 in
\begin{abstract}
Given a pair $(U_t)$ and $(V_t)$ of Lucas sequences, Kimball and Webb
showed that $\sum_{01$, we have
\begin{equation}\label{eq:hao}
\sum_{t=1}^{m-1}\frac{V_t}{U_t}\equiv\ \frac{(m^2-1)D}{6}\cdot\frac{U_m}{V_m}\pmod{w_m^2},
\end{equation}
where $m$ is an integer $\ge5$, $D$ is the discriminant of the characteristic polynomial
associated with the pair of Lucas sequences $U$ and $V$, and $w_m$ is the largest
factor of $U_m$ which is prime to the product $U_2U_3\cdots U_{m-1}$.
\footnote{The only case of the Kimball and Webb congruence
not implied by (\ref{eq:hao}) is when $p$ is $5$ of rank $4$.
However, defining $w_4$ as the largest factor of $U_4$ prime to $3U_2U_3$
would have been sufficient to cover this missing case.}
\medskip
We recall that given a pair of integers $P$ and $Q$, $Q$ nonzero, the two Lucas
sequences $U=(U_t)_{t\ge0}$ and $V=(V_t)_{t\ge0}$ are second order integral linear
recurrences $(X_t)$ that both satisfy the recursion
\begin{equation}\label{eq:recursion}
X_{t+2}=PX_{t+1}-QX_t,\quad\text{ for all }t.
\end{equation} Their two initial terms then fully defines them. We have $U_0=0$ and $U_1=1$,
whereas $V_0=2$ and $V_1=P$. We write $U(P,Q)$ and $V(P,Q)$ when the dependence
on $P$ and $Q$ needs to be reminded. If the zeros of their characteristic polynomial $x^2-Px+Q$
are distinct, say $\alpha$ and $\beta$, then the $t$-th terms of the $U$ and $V$
sequences are given by the so-called Binet formulas, i.e.,
\begin{equation}\label{eq:Binet1}
U_t=\frac{\alpha^t-\beta^t}{\alpha-\beta}\;\text{ and }\;V_t=\alpha^t+\beta^t.
\end{equation} In case $x^2-Px+Q$ has a double zero $\alpha$, then the Binet formulas become
\begin{equation}\label{eq:Binet2}
U_t=t\alpha^{t-1}\;\text{ and }\;V_t=2\alpha^t.
\end{equation}
The rank of appearance $\rho(m)$, or $\rho_U(m)$, of an integer $m$ is the least
positive index $t$ such that $m$ divides $U_t$. It is known to exist for all $m$
prime to $Q$. The rank of a prime $p$ not dividing $Q$ is either equal to $p$,
or is a divisor of $p\pm1$. For $(P,Q)=(2,1)$, $1$ is a double zero of $x^2-Px+Q$.
Thus, $U_t=t$ and $V_t=2$. Applying the theorem of
Kimball and Webb to this particular pair of Lucas sequences yields congruence (\ref{eq:1862}).
\medskip
We restate the main theorem of Kimball and Webb \cite{KW2}, but in a slightly
generalized form, as it appeared in Chapter 3 of the paper \cite{Ba}.
\begin{theorem} \label{thm:KW} Let $p$ be a prime at least $5$ which is not a factor of $Q$.
Assume the rank $\rho$ of $p$ is maximal. Let $k$ be an integer. Then the
sum
$$
\sum_{t\in I_{p,k}}\frac{V_t}{U_t}\text{ is congruent to } \amod{0} {p^2},$$
where $I_{p,k}$ is the set of integers in the interval
$\big(k\rho,(k+1)\rho\big)$.
\end{theorem}
The purpose of the present paper is to prove a common generalization, Theorem
\ref{thm:wol} stated hereunder, to both the Leudesdorf and the Kimball-Webb congruences,
i.e., a common generalization to Theorems \ref{thm:Leud} and \ref{thm:KW}.
\begin{theorem} \label{thm:wol} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences. Let $m$ be an integer of maximal rank with respect to $U(P,Q)$.
Then, for all integers $k$, we have that
$$
S_{m,k}(P,Q)=\sum_{t\in I_{m,k}}\frac{V_t}{U_t}\;\text{ is congruent to }\;0\pmod
{h_m\cdot m^2/\gcd(m,3)},
$$ where $I_{m,k}$ is the set of integers in the interval
$\big(k\rho(m),(k+1)\rho(m)\big)$ that are not multiples of any rank $\rho(p)$
for all primes $p$ dividing $m$, and where
$$
h_m=\begin{cases} 1/2,& \text{ if }m=2^a,\,a\ge1,\text{ and }\nu_2(P)=1;\\
\;2^\sigma,& \text{ if }2||m\;\text{ and }4\mid P;\\
\;2^\tau,& \text{ if }2||m,\;P\text{ is odd and }Q\equiv\amod{1} {4};\\
\;8,& \text{ if }4||m,\;P\text{ is odd and }Q\equiv\amod{3} {4};\\
\;1,& \text{ otherwise,}\end{cases}
$$ with $\sigma=\nu_2(P)-2\ge0$ and $\tau=\nu_2(P^2-Q)-1\ge1$,
$\nu_2(P)$ and $\nu_2(P^2-Q)$ being respectively the $2$-adic valuations of $P$
and $P^2-Q$.
In particular, $S_{m,k}\equiv \amod{0} {m^2/\gcd(m,3)}$ if $m$ is not
a power of $2$ or if $\nu_2(P)\not=1$.
\end{theorem}
\begin{example}\label{exa:only}\quad {\rm Say $(P,Q)=(1,-1)$, i.e., $U=F$ and $V=L$ are the sequences
of Fibonacci and Lucas numbers. We will see that $35$ and $500$
are two integers of maximal rank with respect to $F$. Thus, putting $k=0$ in Theorem
\ref{thm:wol}, we find that
$\bullet$ If $m=35$, then $\rho(35)=40$. Hence,
$$
\sum_{\substack{t=1\\5\,\nmid\, t,\;8\,\nmid\, t}}^{40}\frac{L_t}{F_t}\equiv\ 0\pmod{35^2},
$$ where the above sum, $S_{m,0}(1,-1)$, contains $40-(8+5)+1=28$ terms.
\medskip
$\bullet$ If $m=500=4\cdot5^3$, then
$$\sum \frac{L_t}{F_t}\equiv\ 0\pmod{8m^2=2,000,000},$$
where the sum is over all
$t$'s between $1$ and $\rho(m)=6\cdot5^3=750$ that are prime to $15$, and, thus,
contains $750-(250+150)+50=400$ terms.}
\end{example}
Section 2 of this paper is a short preliminary section where the
relevant definitions, and in particular that of a general integer having maximal rank
with respect to a Lucas sequence $U(P,Q)$, followed by a few remarks and comments, are
given. Section 3 contains the main theorems
and their proofs. Theorem \ref{thm:wol1}, generalizes
the theorem of Kimball and Webb to prime powers. Theorem \ref{thm:wol2}, which may be
viewed as our chief result, is proved via induction on the number of distinct prime factors
of an integer $m$ of maximal rank and so Theorem \ref{thm:wol1} serves as a basis
for that proof
by induction. Theorem \ref{thm:wol2} is already a generalization of both Theorems
\ref{thm:Leud} and \ref{thm:KW}. So we could have ended the paper there. However,
it would not have been complete. We wanted a theorem that fully respected the
definition we took of an integer of maximal rank. The remaining cases are thus
treated in Section 4, but their proofs hinge heavily on the proof of Theorem
\ref{thm:wol2} and are established through a series of lemmas, which, combined with
Theorem \ref{thm:wol2}, yield Theorem \ref{thm:wol}.
\medskip
The proofs of the paper are all elementary, but assume familiarity with classical
properties of Lucas sequences. We refer to Lucas' original work \cite{Lu1} and
Chapters 17 and 18 of \cite{Lu2}, to \cite{Car}, \cite{Rib}, to Chapter 4 of \cite{Wi}, and to
Chapter 2 of \cite{Ba}, for properties of Lucas sequences used herein.
\medskip
The letter $p$ invariably denotes a prime number. If $m$ is an integer, then
$\rho(m)$, or $\rho_U(m)$, denotes its rank in $U$. The letter $D$ stands
for the discriminant $P^2-4Q$ of $x^2-Px+Q$. If $t$ is a rational number,
then $\nu_p(t)$ denotes its $p$-adic valuation. Alternately, as we did
in Theorem \ref{thm:wol}, we write $p^a||t$ to mean that $p^a$ divides
$t$, but $p^{a+1}$ does not divide $t$. These divisions take place in the ring
$A_p$. More generally, the congruences in Theorems \ref{thm:Leud}, \ref{thm:KW}
and \ref{thm:wol} and congruences that appear in this paper take place in the ring
$A_m$, where $A_m$ is the subring of the rationals which, when expressed in
lowest terms, have a denominator prime to $m$. That is, $s\equiv \amod{t} {m}$
means that $s$ and $t$ are in $A_m$ and that $s-t\in mA_m$. Note that $A_m=A_{m^2}
=A_{p_1\cdots p_r}$, if $p_1$, \dots, $p_r$ are the prime factors of $m$.
We will use the well-known
fact \cite{Ja} that $\mathbb{Z}/p^a$ is isomorphic to $A_p/p^a$, $a\ge1$, where the
isomorphism is derived from the identity embedding of $\mathbb{Z}$ into $A_p$.
\section{Preliminaries}
Throughout the paper, we assume that $U=U(P,Q)$ and $V=V(P,Q)$ denote an arbitrary
pair of Lucas sequences.
\medskip
Recall that if $m$ is an integer prime to $Q$, then $m\mid U_t$ iff
$\rho(m)\mid t$. Also, if $p$ is a prime that does not divide $Q$, then $\rho(p)\mid
p-(D|p)$, where $(D|p)$ is $0$,
if $p\mid D$; $1$, if $D$ is a nonzero square (mod $p$)
and $-1$, otherwise.
\medskip
We recall a few classical Lucas identities valid
for all integers $s$ and $t$.
\begin{equation}
\label{eq:w1}
2U_{s+t}=U_sV_t+U_tV_s,
\end{equation}
\begin{equation}
\label{eq:w2}
2V_{s+t}=V_sV_t+DU_sU_t,
\end{equation}
\begin{equation}
\label{eq:w3}
V_t^2-DU_t^2=4Q^t.
\end{equation}
\medskip
It is easy to deduce
from (\ref{eq:w1}) and the relations $Q^tV_{-t}=V_t$, $Q^tU_{-t}=-U_t$ that
\begin{equation}
\label{eq:w1+}
2Q^tU_{s-t}=U_sV_t-U_tV_s.
\end{equation}
\begin{remark}
\label{rem:rootD}
Suppose $p$ is an odd prime not dividing $Q$.
If $t$ is not a multiple of $\rho(p)$, then from (\ref{eq:w3})
we have that the square of the ratio $V_t/U_t$ is well-defined and not
congruent to $\amod{D} {p}$.
\end{remark}
Our intention is to first generalize Theorem \ref{thm:KW} to prime powers,
possibly including the primes $2$ and $3$.
Recall that the rank of a prime $p$ is said to be {\it maximal} if it
is $p+1$, $p$ or $p-1$. We wish our generalized theorems to apply to all
positive integers $m$ having a certain maximal rank property.
\begin{definition} \label{def:maxrk} {\rm (Maximal Rank)\quad
Let $p$ be a prime not dividing $Q$ and $a$ be an integer $\ge1$. We say
that the rank of $p^a$ is {\it maximal} whenever $\rho(p)$ is maximal
and $\rho(p^a)=p^{a-1}\rho(p)$. An integer $m\ge1$ prime to $Q$ is said
to have {\it maximal} rank whenever each prime power dividing $m$ has maximal rank
and the ranks of any two prime powers dividing $m$ are coprime.}
\end{definition}
If $m$ is a prime $p$, then Definition \ref{def:maxrk} only requires
that $\rho(p)$ be $p$ or $p\pm1$. However, if $m=p^a$, with $a\ge2$,
has maximal rank, then clearly we also must have $p^1||U_{\rho(p)}$.
Note that if $m$ has maximal rank with respect to $U(P,Q)$, then
any divisor $n$ of $m$ has maximal rank with respect to $U(P,Q)$.
\medskip
\begin{remark} \label{rem:simpler} \quad {\rm It may be useful to observe that
if $m$ is the product of prime powers which all have maximal rank
with respect to some $U(P,Q)$ and $m$ is either odd, or $m$ and $P$
are both even, then $m$ has maximal rank if and only if
$\gcd\big(\rho(p),\rho(q)\big)=1$,
for any two prime factors $p$ and $q$ of $m$.}
\end{remark}
\begin{proof} Suppose $\gcd\big(\rho(p),\rho(q)\big)=1$. We only need to
verify that $\rho(p^a)$ and $\rho(q^b)$ are coprime, where $p^a||m$ and
$q^b||m$. If $p$ and $q$ are odd, one
of them, say $q$, must have rank equal to $q$, since $p\pm1$ and $q\pm1$
are both even. Thus, $\rho(q^b)=q^b$. So $q\nmid\rho(p)$ and $q\not= p$
yields that $\gcd\big(\rho(p^a),\rho(q^b)\big)=1$.
If $p$ is $2$ and $q$ is odd, then, assuming $P$ is even, we have
$\rho(p)=2$ since $U_2=P$, and thence $\rho(q)=q$. Therefore, $\rho(2^a)=2^a$ and
$\rho(q^b)=q^b$. The converse is immediate.
\end{proof}
The upcoming remark essentially says that if $p$ has maximal rank,
the condition $p^2\nmid U_{\rho(p)}$ suffices for all $p^a$, $a\ge1$,
to have maximal rank. Note that if $U$ is the Fibonacci sequence, then
the search for a Wall-Sun-Sun prime, i.e., a prime $p$ such that $p^2$
divides $U_{\rho(p)}$, has gathered attention, but to this date
none is known to exist and there does not exist any below $2\times10^{14}$
\cite{MR}.
\begin{remark} \label{rem:admiss}\quad {\rm Let $p\nmid Q$ be a prime of
maximal rank such that $p^2\nmid U_{\rho(p)}$. Additionally,
we assume $P$ is even, if $p$ is $2$. Then $p^a$ has
maximal rank for all $a\ge1$.}
\end{remark}
\begin{proof} By Theorem 9 of \cite{Ba}, the rank of $p^a$ is equal to $p^{a-1}\rho(p)$,
if $p$ is odd. Suppose $p=2$. Since $U_1=1$, $U_2=P$ and $P$ is even,
we have $\rho(2)=2$. By hypothesis, $4\nmid U_{\rho(2)}$, i.e., $4\nmid P$, and $Q$ is odd.
Therefore, $8\mid D=
P^2-4Q$. By identity (\ref{eq:w3}), $\nu_2(V_t)=1$ for all integers $t$'s.
Thus, the $2$-adic valuation of $U_{2t}=U_tV_t$ is one more than that of $U_t$.
So by induction we obtain that $\rho(2^a)=2^{a-1}\rho(2)=2^a$.
\end{proof}
With the help of Lemma \ref{lem:evencase}, we give
the full list of integers of maximal rank with respect to the Fibonacci
sequence.
\begin{example} \label{example:Fib}\quad {\rm An integer $m\ge1$ has maximal rank with
respect to the Fibonacci sequence $F=U(1,-1)$ iff it has the form
$$
2^a\;5^b\;p^c,
$$ where $p$ is a prime $\amod{3} {4}$ of rank $\rho(p)=p\pm1$, not
a Wall-Sun-Sun prime in case $c\ge2$, and where $a\in\{0,1,2\}$, $b\ge0$, $c\ge0$ with
$$
\left.\begin{array}{cl}\bullet\; c=0,\;\;\; & \text{ if }a=2;\\
\bullet\;3\nmid\rho(p),& \text{ if }a=1\text{ and }c\ge1;\\
\bullet\;5\nmid\rho(p),& \text{ if }b\ge1\text{ and }c\ge1.\end{array}\right.
$$
Artin's conjecture states that an integer $a$, not a square, with $|a|\ge2$, is
a primitive root modulo infinitely many primes. In fact, it has been
conditionally proved that such primes have a positive density {\rm\cite{Ho}}.
Similarly here, since $Q$ is not a square, it is expected that a positive
proportion of the primes $\amod{3} {4}$ have maximal ranks in $F$. In fact,
$3$, $7$, $11$, $19$, $23$, $31$ and $43$ all have maximal ranks,
$47$ being the smallest prime $\amod{3} {4}$ with rank less than $p-1$. For all primes
$p$ that are $\amod{1} {4}$, we have that $p\mid U_{(p-1)/2}$ or $p\mid U_{(p+1)/2}$.}
\end{example}
\begin{definition} \label{def:Im} {\rm ($I_{m,k}$ and $S_{m,k}$)\quad
Given an integer $m\ge1$ and an integer $k$, we define
$I_{m,k}$ as the set of integers that lie in the interval
$\big[k\rho(m),(k+1)\rho(m)\big]$ and are not
a multiple of any $\rho(p)$, for all primes $p$ dividing $m$.
Then $S_{m,k}$ will denote the sum of all
$V_t/U_t$ in $A_m$ as $t$ varies through $I_{m,k}$.
We write $I_{m,k}(P,Q)$ or $S_{m,k}(P,Q)$ if the dependence
on $(P,Q)$ needs to be specified. }
\end{definition}
In coining the two definitions \ref{def:maxrk} and \ref{def:Im}, we had
two constraints in our mind. In Leudesdorf's Theorem \ref{thm:Leud}, the sum
involved is $S_{m,0}(2,1)$. That sum goes up to $m$, which is viewed
as the rank of $m$ in $U_t=t$. Thus, if we wanted a theorem that
generalizes Theorem \ref{thm:Leud}, then $I_{m,0}$ had to go up to $\rho(m)$.
Actually, considering sums that go up to the least common multiple of the ranks of the prime powers
dividing an integer $m$ would also reduce to the right sums when $U_t=t$.
However, generally these sums are not $\amod{0} {m^2}$.\footnote{For instance,
$3$ and $7$ have maximal ranks in the Fibonacci sequence and the least
common multiple of their ranks is $8$. But $\sum_{t=1}^8L_t/F_t$, ($4\nmid t$),
is $\amod{0} {21}$, $\amod{6} {9}$ and $\amod{14} {49}$.}
Also we wanted the arguments used in proving Theorem \ref{thm:KW}
to remain valid, which meant that $S_{m,k}$ should have about $m$
terms. These observations guided us in defining the notion of maximal rank.
\begin{lemma} \label{lem:distinct} Let $k$ be an integer. Let $m$ be
an integer $\ge1$ prime to $Q$. If $m$ is odd, then all ratios $V_t/U_t$
are distinct (mod $m$) as $t$ varies through $I_{m,k}$.
If $m$ is even and $2||P$,
then all ratios $V_t/(2U_t)$ are distinct (mod $m$) as
$t$ varies through $I_{m,k}$.
\end{lemma}
\begin{proof} Assume first $m$ is odd. If $s$ and $t$ are distinct integers in $I_{m,k}$,
then $U_{s-t}$ is not divisible by $m$. Thus, dividing (\ref{eq:w1+}) through by $U_sU_t$,
we get that
\begin{equation}
\label{eq:distinct}
\frac{V_t}{U_t}-\frac{V_s}{U_s}=2Q^t\frac{U_{s-t}}{U_sU_t}.
\end{equation}
Since the right-hand term of (\ref{eq:distinct}) is not $\amod{0} {m}$,
all ratios $V_t/U_t$ are pairwise incongruent modulo $m$ as
$t$ varies through $I_{m,k}$. For the case $m$ even, note that $P=2P'$ with $P'$ odd.
Since $D=4(P'^2-Q)$, $8$ divides $D$. We have $V_t^2-DU_t^2=4Q^t$, so each $V_t$
is even and the ratios $V_t/(2U_t)$ do
belong to the ring $A_m$ for $t\in I_{m,k}$. The reasoning is then similar to that of $m$ odd.
\end{proof}
\section{Main Theorems and Proofs.}
\begin{theorem} \label{thm:wol1} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences. Let $p$ be a prime number. Suppose $p^a$ has maximal rank with
respect to $U(P,Q)$, where $P$ is even and not divisible by $4$ in case $p$ is $2$.
Then for all integers $k$
$$
S_{p^a,k}=\sum_{t\in I_{p^a,k}}\frac{V_t}{U_t}\;\text{ is congruent to
} \amod{0} {p^{c}},
$$ where
$$
c=\begin{cases} 2a,& \text{ if }p\ge5;\\
2a-1,& \text{ if }p=2\text{ or }3.\end{cases}
$$
\end{theorem}
\begin{proof} Fix an integer $k$. Note that $I_{p^a,k}$ contains
$p^{a-1}\rho(p)-p^{a-1}=p^{a-1}\big(\rho(p)-1\big)$ integers. By convention, all
unmarked sums appearing in the proof are taken over the set $I_{p^a,k}$,
and thus contain $p^{a-1}\big(\rho(p)-1\big)$ terms.
Denote $(2k+1)p^{a-1}\rho(p)$ by $b$. Since the rank of $p^a$ is $p^{a-1}\rho(p)$,
we have that $p^a$ divides $U_{p^{a-1}\rho(p)}$ and that $U_b$ is at least divisible by $p^a$.
By (\ref{eq:w1}),
$$
2S_{p^a,k}=\sum\bigg(\frac{V_t}{U_t}+\frac{V_{b-t}}{U_{b-t}}\bigg)=
2\sum\frac{U_b}{U_tU_{b-t}}.$$
{\bf Suppose $p$ is odd}. Hence, it suffices to show that $\sum2/(U_tU_{b-t})$ is
divisible by
$p^d$, where $d=a$ if $p>3$, and $d=a-1$ if $p=3$. By (\ref{eq:w3}) with $t=b$,
$\gcd(U_b,V_b)$ divides $2Q^{\lfloor b/2\rfloor}$, so
that $p$ does not divide $V_b$. Thus, it also suffices to show that
$$
S_1:=\sum\frac{2V_b}{U_tU_{b-t}}
$$ is divisible by $p^d$. Now, by (\ref{eq:w2}), $S_1$ is equal to
$$
\sum\frac{V_tV_{b-t}}{U_tU_{b-t}}\;+\;Dp^{a-1}\big(\rho(p)-1\big).
$$ But
$$\sum\frac{V_tV_{b-t}}{U_tU_{b-t}}=
\sum\frac{U_tU_{b-t}V_tV_{b-t}}{(U_tU_{b-t})^2}=
\frac12\sum\frac{(U_tV_{b-t}+U_{b-t}V_t)^2}{(U_tU_{b-t})^2}
-\sum\bigg(\frac{V_t}{U_t}\bigg)^2.
$$
In the above final expression, the numerators of the terms in the first sum are
all equal to $4U_b^2$ by (\ref{eq:w1}). Since $p^a$ divides $U_b$, we have that
$p^d$ divides $S_1$, if and only if, $p^d$ divides
$$S_2:= Dp^{a-1}\big(\rho(p)-1\big)-S_3,$$
where $S_3:=\sum(V_t/U_t)^2$.
If $\rho(p)$ is $p+1$, then $S_2$ is congruent to $\amod{-S_3} {p^a}$.
But since by Lemma \ref{lem:distinct} the $p^a$ rational numbers $V_t/U_t$ that appear in $S_3$
are all distinct $\amod{0} {p^a}$, we have that
$$
S_3\equiv \ \sum_{t=1}^{p^a}t^2=\frac{p^a(p^a+1)(2p^a+1)}{2\cdot3}\pmod{p^a},
$$ which yields that
$$
S_3\equiv \amod{0} {p^d}.
$$
If $\rho(p)$ is $p$, then $p$ divides $D$. Thus, again,
$S_2\equiv \amod{-S_3} {p^a}$.
Since $p$ has odd rank, say by Theorem 10 in \cite{Ba}, no term of the $V$ sequence is divisible by $p$.
Thus, the $p^a-p^{a-1}$ ratios $V_t/U_t$ that appear in $S_3$,
being all distinct (mod $p^a$),
are all the invertible elements of the ring $A_p/p^a$. As they form a cyclic multiplicative
group generated by, say, $g$, we have
$$
S_3\equiv\sum_{k=0}^{\varphi(p^a)-1}g^{2k}=\frac{g^{2\varphi(p^a)}-1}{g^2-1}\pmod{p^a},
$$ where $\varphi$ denotes Euler's totient function. For odd primes $p$, any
primitive root (mod $p^a$) reduces to a primitive root (mod $p$). Therefore, the order
of $\amod{g} {p}$ is $p-1$ and,
thus $p\mid g^2-1$ iff $p-1\mid 2$, i.e., iff $p=3$.
But if $p=3$ and $a\ge2$, then $g$ being a primitive root (mod $9$),
the quantity $g^2-1$ is divisible
by $3$, but not by $9$.
If $p=3$ and $a=1$, then $d=0$. Therefore, for all cases, we have
$$
S_3\equiv\ 0\pmod {p^d}.
$$
If $\rho(p)$ is $p-1$, then the set $I_{p^a,k}$ is made up of $p^{a-1}$ integer intervals
of length $p-2$. Indeed, integers in $I_{p^a,k}$ are not divisible by $\rho(p)$, i.e., by
$p-1$. As $t$ varies through each such interval all $V_t/U_t$ are distinct
(mod $p$),
and are not equal to any of the two square roots of $\amod{D} {p}$ by
Remark \ref{rem:rootD}.
Thus, the summands $(V_t/U_t)^2$ in $S_3$ take the value $0$ once and every nonzero
quadratic residue (mod $p$) twice,
except $D$, on each interval of length $p-2$ of $I_{p^a,k}$. Thus, as $t$ runs through
$I_{p^a,k}$ and since all $V_t/U_t$ are distinct (mod $p^a$),
none of the summands $(V_t/U_t)^2$
of $S_3$ is equal to any of the residues $D$, $D+p$, $D+2p, \hdots,
D+(p^{a-1}-1)p$ (mod $p^a$).
Thus,
$$
S_3\equiv \sum_{i=1}^{p^a}i^2-2\sum_{j=1}^{p^{a-1}}(D+jp)\equiv\ 0-2p^{a-1}D\pmod{p^d}.
$$
Therefore, $S_2=Dp^{a-1}(p-2)-S_3\equiv\ -2Dp^{a-1}+2p^{a-1}D=\amod{0} {p^d}$.
\medskip
{\bf Suppose $p=2$}. The symbols $S_1$, $S_2$ and $S_3$ refer to the same sums
we had defined in the case where $p$ was odd.
Since $P$ is even and $U_2=P$, $\rho(2)=2$ and $b=(2k+1)2^a$. As seen in proving Remark \ref{rem:admiss}, $\nu_2(U_{2^a})=a$ and so we also have $\nu_2(U_b)=a$.
Therefore, as $S_{2^a,k}=\sum\frac{U_b}{U_tU_{b-t}}$, we have
$$
\nu_2(S_{2^a,k})=a+\nu_2\bigg(\sum\frac1{U_tU_{b-t}}\bigg)
=a+\nu_2\bigg(\sum\frac{2V_b}{U_tU_{b-t}}\bigg)-2,
$$ since, as shown in Remark \ref{rem:admiss},
$\nu_2(V_b)=1$. Thus, we need to show that $\nu_2(S_1)\ge a+1$.
In fact, we will see that $\nu_2(S_1)=a+1$ so that $\nu_2(S_{2^a,k})$ is
exactly $2a-1$ for all integers $k$. Because $\frac12(4U_b^2)$ is divisible
by $2^{2a+1}$, which is $>2^{a+1}$, $\nu_2(S_1)=a+1$ iff $\nu_2(S_2)=a+1$.
Since
$D=4(P'^2-Q)$, where $P=2P'$ and $P'$ is odd, $8\mid D$. Therefore,
$\nu_2(S_2)$ is $a+1$ iff $\nu_2(S_3)=a+1$. But $S_3=4S_4$, where
$S_4=\sum\frac{V_t^2}{4U_t^2}$. The $2^{a-1}$ terms $V_t/2U_t$
are all distinct (mod ${2^a}$), by Lemma \ref{lem:distinct}, and each
such term is a unit of the ring $A_2$, by the proof of Remark \ref{rem:admiss}.
Therefore,
$$
S_4\equiv\sum_{t=1}^{2^{a-1}}(2t-1)^2\pmod{2^a}.
$$ But $\sum_{t=1}^N(2t-1)^2=4(N-1)N(N+1)/3-N$ so $2^{a-1}|| S_4$.
Since $S_3=4S_4$, we have $\nu_2(S_3)=a+1$ as required.
\end{proof}
\begin{remark} \label{rem:exact} {\rm Under the hypotheses of Theorem \ref{thm:wol1},
we have actually shown that the sums $S_{2^a,k}$ have $2$-adic valuation
exactly equal to $2a-1$, for all integers $k$.}
\end{remark}
We are ready to move on to our main result.
\begin{theorem} \label{thm:wol2} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences. Let $m$ be an integer of maximal rank with respect to $U(P,Q)$.
If $m$ is even, then we make the additional hypothesis that $P$ is even and
not divisible by $4$. Then for all integers $k$
$$
S_{m,k}(P,Q)=\sum_{t\in I_{m,k}}\frac{V_t}{U_t}\;\text{ is congruent to }\;0\pmod {m^2/d_m},
$$ where $I_{m,k}$ is the set of integers in the interval
$\big(k\rho(m),(k+1)\rho(m)\big)$ that are not multiples of any rank $\rho(p)$ for all primes $p$
dividing $m$, and where
$$
d_m=\begin{cases}\; 2,& \text{ if }m=2^a,\,a\ge1;\\
\;3,& \text{ if }3\mid m;\\
\;1,& \text{ otherwise.}\end{cases}
$$
\end{theorem}
\begin{proof} We proceed by induction on $\omega(m)$, where $\omega$ denotes
the distinct prime factors counting function. More precisely, our inductive hypothesis
at level $i$, $i\ge1$, says that for all integers $k$, all integers $m\ge1$ with
$\omega(m)=i$ and all Lucas sequences $U=U(P,Q)$ with respect to which $m$ satisfies
the hypotheses of Theorem \ref{thm:wol2}, the sum $S_{m,k}(P,Q)$ is congruent
to $\amod{0} {m^2/d_m}$.
\medskip
The case $i=1$ was established in Theorem \ref{thm:wol1}, so we
assume that $i\ge2$ and that the result holds for integers having
$i-1$ distinct prime factors. To prove the inductive hypothesis at
level $i$, we establish two properties (\ref{eq:one}) and (\ref{eq:two})
which together clearly suffice to prove the inductive step. The first
property says that
\begin{equation}\label{eq:one}
\text{if }m=p^an, \text{ then }n^2/d_n\text{ divides }S_{m,k},
\end{equation} where $p$ is a prime that does not divide $n$ and $a\ge1$.
Note that (\ref{eq:one}) is sufficient to prove the inductive step
if $m$ is odd, but not if $m$ is even, unless we know the theorem
holds for even integers at level $i=2$.
Thus, in addition, we prove that
\begin{equation}\label{eq:two}
\text{ if }m=2^aq^b, \text{ then }2^{2a} \text{ divides }S_{m,k},
\end{equation} where $q$ is an odd prime, $a$ and $b\ge1$.
\medskip
We begin by establishing (\ref{eq:one}) inductively. To this end, we note that
$$
S_{m,k}=S^*-S^{**},
$$
where
\begin{equation}\label{eq:fund}
S^*=\sum_{j=0}^{\rho(p^a)-1}\quad\sum_{\substack{t=k\rho(m)+j\rho(n)\\
\rho(q)\,\nmid\, t\text{ if }q\mid n}}^
{k\rho(m)+(j+1)\rho(n)}\frac{V_t}{U_t}\qquad\text{ and }\qquad
S^{**}=\sum_{\substack{t=k\rho(m)\\\rho(p)\,\mid\, t\\\rho(q)\,\nmid\, t,\,
\forall q\mid n}}^{(k+1)\rho(m)}\frac{V_t}{U_t},
\end{equation} and the letter $q$ stands for a prime.
Moreover, we have
\begin{equation}\label{eq:imp}
S^*=\sum_{j=0}^{\rho(p^a)-1}\;S_{n, j+k\rho(p^a)}.
\end{equation}
Each inner sum $S_{n, j+k\rho(p^a)}$ in $S^*$ is, by the inductive hypothesis,
divisible by $n^2/d_n$, so we are left with showing that $S^{**}$ is also
divisible by $n^2/d_n$. But
\begin{equation}\label{eq:s**}
S^{**}=\sum_{\substack{t=k\rho(n)p^{a-1}\\\rho(q)\,\nmid\, t,\,\forall q\mid n}}^{(k+1)\rho(n)p^{a-1}}
\frac{V_{\rho(p)t}}{U_{\rho(p)t}}=U_{\rho(p)}^{-1}\sum_{j=kp^{a-1}}^{(k+1)p^{a-1}-1}S_{n,j}
\big(V_{\rho(p)},Q^{\rho(p)}\big).
\end{equation}
In (\ref{eq:s**}), the sum $S_{n,j}\big(V_{\rho(p)},Q^{\rho(p)}\big)$ is associated with
the pair of Lucas sequences attached to the recursion $x^2-V_{\rho(p)}x+Q^{\rho(p)}$.
Indeed, we have
\begin{equation}\label{eq:change}V_{\rho(p)t}(P,Q)=V_t(P',Q') \;\text{ and }\;
U_{\rho(p)t}(P,Q)=U_t(P',Q')\cdot U_{\rho(p)}(P,Q),
\end{equation}
where $P'=V_{\rho(p)}(P,Q)$ and $Q'=Q^{\rho(p)}$. Identities (\ref{eq:change}) may be derived
from the Binet formulas for $U_t$ and $V_t$ whether the discriminant $P^2-4Q$
is zero or nonzero.
For instance, suppose $x^2-Px+Q=(x-\alpha)^2$. Then $U_t(P,Q)=t\alpha^{t-1}$
and denoting $\rho(p)$ by $\rho$ we have
\begin{eqnarray*}
U_{\rho t}(P,Q) & = & \rho t\alpha^{\rho t-1}=\rho t\alpha^{\rho(t-1)+(\rho-1)}\\
& = & \rho\alpha^{\rho-1}\cdot t(\alpha^\rho)^{t-1}\\
& = & U_{\rho}(P,Q)\cdot U_t(P',Q').
\end{eqnarray*}
By the inductive hypothesis $n^2/d_n$ divides each sum $S_{n,j}(P',Q')$,
for all $j$'s, provided we check, on the one hand, that $n$ has
maximal rank with respect to $U'=U(P',Q')$ and, on the other, in case $n$ is even,
that $\nu_2(P')=1$.
\medskip
Since $m$ is prime to $Q$, $n$ is prime to $Q'$. Let $q$ be a prime factor
of $n$, $\rho(q)$ be its rank in $U=U(P,Q)$ and $\rho'(q)$
its rank in $U'=U(P',Q')$, where as above $\rho(p)$ is the rank
of $p$ in $U$. By hypothesis, $\rho(q)$ and $\rho(p)$ are coprime
so that $q\nmid U_{\rho(p)}$. Thus, as $U_{\rho(p)t}=U_{\rho(p)}
\cdot U'_t$, we have that $q\mid U'_t$ iff $q\mid U_{\rho(p)t}$ iff
$\rho(q)\mid\rho(p)t$ iff $\rho(q)\mid t$. Thus, $\rho(q)=\rho'(q)$.
We conclude that the rank of $q$ in $U'$ is maximal. Similarly, since
$\rho(q^s)=q^{s-1}\rho(q)$ is also prime to $\rho(p)$, the ranks of
$q^s$ in $U$ and in $U'$ are identical for all $s\ge2$. Therefore,
if $q^\alpha||m$, then, as $\rho(q^\alpha)$ exists and is equal to
$q^{\alpha-1}\rho(q)$, we have $\rho'(q^\alpha)=q^{\alpha-1}\rho'(q)$.
That is, $q^\alpha$ has maximal rank in $U'$. Moreover, distinct
prime factors of $n$ have coprime ranks in $U'$.
Suppose $n$ is even. Then $m$
is even. Hence, $Q$ is odd and $\nu_2(P)=1$, which, as proved in
Remark \ref{rem:admiss}, implies that $\nu_2(V_t)=1$ for all integers $t$.
But $P'=V_{\rho(p)}$.
Thus, since each prime factor
$q$ of $n$ is prime to $U_{\rho(p)}$, we deduce that $S^{**}$ is divisible by
$n^2/d_n$. We have proved (\ref{eq:one}).
To prove (\ref{eq:two}), we assume $i=2$ and `recycle' the proof of (\ref{eq:one}).
So given $m=2^aq^b$ we have, by (\ref{eq:one}), that $2^{2a-1}q^{2b}/d_q=
m^2/(2d_m)$ divides $S_{m,k}$. Reexamining the proof of (\ref{eq:one}) with $p=q$,
we will show that in fact $2^{2a}$ divides $S_{m,k}$. By Remark \ref{rem:exact},
each of the $\rho(q^b)$ sums $S_{2^a,j+k\rho(q^b)}$ in (\ref{eq:imp}) is divisible
by $2^{2a-1}$, but not by $2^{2a}$. But, by (\ref{eq:s**}), we see that
$S^{**}$ is also the sum of $q^{b-1}$ sums each of which is exactly divisible
by $2^{2a-1}$. Therefore, $S_{m,k}$ is the sum of $\rho(q^b)+q^{b-1}$ terms
each divisible exactly by $2^{2a-1}$. Thus, it suffices to check that
$\rho(q^b)+q^{b-1}$ is even. But $\rho(2)=2$, and so $\rho(q)$ must be odd.
As the rank of $q$ is maximal, it must be that $\rho(q)=q$. Hence,
$\rho(q^b)+q^{b-1}=q^{b-1}(q+1)$.
\end{proof}
\section{The Remaining Cases}
Theorem \ref{thm:wol2} clearly contains Theorem \ref{thm:KW}, but it
also implies Theorem \ref{thm:Leud}. Indeed, for $(P,Q)=(2,1)$,
we have $U_t=t$ and $V_t=2$, for all $t$'s. In particular, $\nu_2(P)=1$
and all integers $m\ge1$ have maximal rank.
Say, for instance, that $3\mid m$. Then, by Theorem \ref{thm:wol2},
$\sum_{t\in I_{m,0}}2/t\equiv\ \amod{0} {m^2/3}$, which implies
$$\sum_{\substack{t=1\\\gcd(t,m)=1}}^m1/t\equiv\ 0
\pmod {m^2/\gcd(m,6)},$$ as $\gcd(t,m)=1$ iff $\rho(p)=p\nmid m$ for all primes $p$
dividing $m$.
\medskip
But Theorem \ref{thm:wol2} does not apply to even integers having maximal
rank in $U(P,Q)$, if either $4\mid P$, or $P$ is odd. The next lemmas treat
those missing cases, and, combined with Theorem \ref{thm:wol2}, they yield
Theorem \ref{thm:wol} stated in the introduction.
The first lemma fully describes when powers of $2$ have maximal rank.
\begin{lemma}\label{lem:evencase} Assume $Q$ is odd. Then $2^a$, $a\ge1$,
has maximal rank in $U(P,Q)$ if and only if
$$
\begin{cases}\; a=1,& \text{ if }4\mid P,\text{ or if }P\text{ is odd and }
Q\equiv \amod{1} {4};\\
\;a=1\text{ or }2,& \text{ if }P\text{ is odd and }Q\equiv\amod{3} {4};\\
\;a\ge1,& \text{ if }P\equiv \amod{2} {4}.\end{cases}
$$
\end{lemma}
\begin{proof} Since $U_2=P$ and $U_3=P^2-Q$, either $P$ is even and $\rho(2)=2$,
or $P$ is odd and $\rho(2)=3$. Thus, $2^a$ has maximal rank for $a=1$.
If $4\mid P$, or if $P$ is odd and $Q\equiv\amod{1} {4}$, then $\rho(4)=\rho(2)$.
By (\ref{eq:w3}), if $U_t$ is even, then $V_t$ is even. Since $U_{2t}=U_tV_t$,
we have $\nu_2(U_{2t})\ge1+\nu_2(U_t)$. Therefore, since $\rho(4)=\rho(2)$,
$\rho(2^a)<2^{a-1}\rho(2)$ for all $a\ge2$.
If $P$ is odd and $Q\equiv \amod{3} {4}$,
then $\rho(2)=3$ and $\rho(4)=6$. Thus,
$4$ has maximal rank. However, $U_6=U_2U_3(P^2-3Q)$ and $4\mid P^2-3Q$, so
$8\mid U_6$. Hence, $\rho(8)=\rho(4)$ and $\rho(2^a)<2^{a-1}\rho(2)$, for all
$a\ge3$.
The case $P\equiv \amod{2} {4}$ was taken care of in Remark \ref{rem:admiss}.
\end{proof}
\begin{lemma} \label{lem:wol3} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences, where $P$ is divisible by $4$ and $Q$ is odd.
Let $m$ be an even integer of maximal rank with respect to $U(P,Q)$.
Then for all integers $k$
$$
S_{m,k}(P,Q)\equiv\ 0\pmod {2^\sigma m^2/\gcd(m,3)},
$$ where $\sigma=\nu_2(P)-2$.
\end{lemma}
\begin{proof} By Lemma \ref{lem:evencase}, $m$ is not divisible by $4$. So we write $m=2n$ with
$n$ odd. Since $\rho(2)=2$, all odd prime factors $p$ of $m$ satisfy $\rho(p)=p$.
As in proving Theorem \ref{thm:wol2}, we carry an induction
on $i=\omega(m)$, where the inductive hypothesis at level $i$
assumes the lemma to hold for all integers $m$ with $\omega(m)=i$,
all pairs $(P',Q')$, $4\mid P'$ and $Q'$ odd, with respect to
which $m$ has maximal rank in $U(P',Q')$ and all integers $k$.
If $i=1$, that is, if $m=2$, then $S_{2,k}=V_{2k+1}/U_{2k+1}$.
An easy induction using (\ref{eq:recursion}) yields that $\nu_2(V_{2t})=1$
and $\nu_2(V_{2t+1})=\nu_2(P)$, for all integers $t$. Hence, $2^{\nu_2(P)}||S_{2,k}$. But
$2^{\nu_2(P)}=2^\sigma m^2$.
Assume that $i\ge2$ and that the inductive hypothesis holds at level $i-1$.
We decompose $S_{m,k}$ into the difference of $S^*$ and $S^{**}$
as we did in the proof of Theorem \ref{thm:wol2} by choosing a prime
$p$ that divides $m$. If $p$ is $2$, then, by Theorem \ref{thm:wol2},
both the inner sums $S_{n,j+2k}(P,Q)$ of $S^*$ in (\ref{eq:imp}) and the
inner sums $S_{n,j}(P',Q')$ of $S^{**}$ in (\ref{eq:s**}) are divisible
by $n^2/d_n$, where $d_n=\gcd(n,3)$. But $\gcd(n,3)=\gcd(m,3)$
so $n^2/\gcd(m,3)$ divides $S_{m,k}$. It remains
to see that $2^{\nu_2(P)}$ divides $S_{m,k}$. If $p$ is odd, then
put $\ell=m/p^a$, where $a=\nu_p(m)$. The inner sums $S_{\ell,j+k\rho(p)}(P,Q)$
of $S^*$ are now divisible by $2^\sigma\ell^2/\gcd(\ell,3)$, and by $2^{\nu_2(P)}$ in particular,
by the inductive hypothesis. The inner sums $S_{\ell,j}(P',Q')$ are
divisible by $2^{\nu_2(P')}$ by the inductive hypothesis, which is applicable since
$4\mid P'$ and $Q'$ is odd. But $P'=V_{\rho(p)}=V_p$ and $\nu_2(V_p)=\nu_2(P)$, since
$p$ is odd. Hence, $S_{m,k}$ is divisible by $2^\sigma m^2/\gcd(m,3)$.
\end{proof}
\begin{lemma} \label{lem:wol4} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences, where $P$ is odd and $Q$ is congruent
to $\amod{1} {4}$. Let $m$ be an even integer of maximal rank with respect
to $U(P,Q)$. Then for all integers $k$
$$
S_{m,k}(P,Q)\equiv\ 0\pmod {2^\tau m^2/\gcd(m,3)},
$$ where $\tau=\nu_2(P^2-Q)-1\ge1$.
\end{lemma}
\begin{proof} One may carry a successful induction that closely follows
that of the proof of Lemma \ref{lem:wol3}. Note that $4\nmid m$ and
that $\rho(2)=3$. If $m=p^a\ell$, $\ell$ even, then by induction the sums
$S_{\ell,j}(P',Q')$ in $S^{**}$ are divisible by $2^\tau\ell^2/\gcd(\ell,3)$.
Indeed, $2\mid V_t$ iff $3\mid t$. Thus, since
$P'=V_{\rho(p)}$ and $\rho(2)\nmid\rho(p)$, $P'$ is odd.
Moreover, $Q'=Q^{\rho(p)}\equiv \amod{1} {4}$. If $m=2n$, then,
by Theorem \ref{thm:wol2} applied to the inner sums in both $S^*$ and $S^{**}$,
$n^2/d_n$ divides $S_{m,k}$, where $d_n$ was defined in Theorem \ref{thm:wol2}.
For the base step of the induction, note that if
$\omega(m)=1$, then $m=2$. So $I_{2,k}=\{3k+1,3k+2\}$ and $S_{2,k}=
2U_{6k+3}/U_{3k+1}U_{3k+2}$. Therefore,
we have $\nu_2(S_{2,k})=\nu_2\big(2U_3\big)=2+\tau$. Indeed,
$U_{3(2k+1)}=U_3\cdot U'_{2k+1}$, where $U'=U(V_3,Q^3)$, and
$U'_t\pmod2=0,1,0,1,0,1,\cdots$ ($t\ge0$), since $V_3$ is even.
\end{proof}
\begin{lemma} \label{lem:wol5} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences, where $P$ is odd and $Q$ is congruent
to $\amod{3} {4}$. Let $m$ be an even integer not divisible by $4$ of maximal
rank with respect to $U(P,Q)$. Then for all integers $k$
$$
S_{m,k}(P,Q)\equiv\ 0\pmod {m^2/\gcd(m,3)}.
$$
\end{lemma}
\begin{proof} An induction very similar to those used in proving
Lemmas \ref{lem:wol3} and \ref{lem:wol4} works fine. Note however
that besides Theorem \ref{thm:wol2}, Lemma \ref{lem:wol4} also
comes into play. Indeed, if $m=p^a\ell$, $p$ an odd prime not
dividing $\ell$, then the sums $S_{\ell,j}$ in $S^{**}$
are associated with a Lucas sequence $U(P',Q')$, where $P'$ is odd,
but $Q'=Q^{\rho(p)}$ is congruent to $\amod{1} {4}$, if $\rho(p)$ is even.
The base step of the induction corresponds to $m=2$ and, as in the
proof of Lemma \ref{lem:wol4}, we have $\nu_2(S_{2,k})=\nu_2(2U_3)$.
However, $U_3=P^2-Q$ is even, but not divisible by $4$.
\end{proof}
\begin{lemma} \label{lem:wol6} Let $U(P,Q)$ and $V(P,Q)$ be a pair
of Lucas sequences, where $P$ is odd and $Q$ is congruent
to $\amod{3} {4}$. Let $m$ be an integer divisible by $4$ of maximal rank with respect
to $U(P,Q)$. Then for all integers $k$
$$
S_{m,k}(P,Q)\equiv\ 0\pmod {8m^2}.\footnote{Thus, $2^7$ divides $S_{m,k}$.
Unless we refine further the hypotheses on $P$ and $Q$, the exponent $7$
is optimal. For instance, $S_{4,0}(1,-1)=\frac{128}{15}$.}
$$
\end{lemma}
\begin{proof} A proof by induction on $i=\omega(m)$ of the same model
as in the three previous lemmas works fine. The rank of $4$ is $6$.
Since the rank of $3$ must be $2$, $3$ or $4$, and none of these
is prime to $6$, $3\nmid m$.
Writing $m$ as $4n$ with $n$ odd, we find that $n^2$ divides
$S_{m,k}$ by Theorem \ref{thm:wol2}. Thus, we are left with seeing
that $2^7$ divides $S_{m,k}$. Write $m$ as
$p^a\ell$, where $p$ is a prime $\ge5$ and $p\nmid\ell$.
We have that $4\mid\ell$ and that
the inner sums $S_{\ell,j+k\rho(p^a)}$ in $S^*$ are divisible by
$8\ell^2$ and by $2^7$ in particular, using the inductive hypothesis. How about the
inner sums $S_{\ell,j}(P',Q')$ of $S^{**}$? Note that $\rho(2)$
is $3$. So $m$ being of maximal rank, $3\nmid\rho(p)$. But
$2\mid V_t$ iff $3\mid t$. So $P'=V_{\rho(p)}$ is odd. In fact,
as $\rho(4)=6$, $\rho(p)$ must also be odd, that is to say, $\rho(p)=p$.
Thus, $Q'=Q^{\rho(p)}\equiv \amod{3} {4}$. The inductive hypothesis yields
that $S^{**}$ is divisible by $2^7$.
We have not checked the initial step of the induction, i.e., the case
$m=4$. Note that $I_{4,k}=\{6k+1,6k+2,6k+4,6k+5\}$. Combining, on one
hand, the first and fourth terms of $S_{4,k}$, and, on the other hand,
the middle ones, yields
$$
S_{4,k}=\frac{2U_{12k+6}}{U_{6k+1}U_{6k+5}}+\frac{2U_{12k+6}}{U_{6k+2}U_{6k+4}}.
$$
Hence, $\nu_2(S_{4,k})=\nu_2(2U_6)+\nu_2(U_{6k+2}U_{6k+4}+U_{6k+1}U_{6k+5})$.
But $U_6=U_2U_3(P^2-3Q)=P(P^2-Q)(P^2-3Q)$, so that
\begin{equation}\label{eq:1st}
\nu_2(2U_6)=2+\nu_2(P^2-3Q)\ge\begin{cases}\;5,\quad\text{ if }Q\equiv \amod{3} {8};\\
\;4,\quad\text{ if }Q\equiv\amod{7} {8} .\end{cases}
\end{equation}
Since $\rho(8)=6$, we have $U_{t+6}\equiv \amod{U_7U_t} {8}$ for all $t\ge0$.
Indeed, the congruence holds for $t=0$ and $t=1$, and, by (\ref{eq:recursion}),
it must hold for all $t$'s. Thus,
$$
U_{6k+2}U_{6k+4}+U_{6k+1}U_{6k+5}\equiv
\amod{U_7^{2k}(U_2U_4+U_1U_5)} {8}.
$$
A direct calculation gives $U_2U_4+U_1U_5=2P^4-5P^2Q+Q^2\equiv
\amod{3(Q+1)} {8}$.
Therefore,
$$
\nu_2(U_{6k+2}U_{6k+4}+U_{6k+1}U_{6k+5})\ge
\begin{cases}\; 2,\quad\text{ if }Q\equiv \amod{3} {8};\\
\; 3,\quad\text{ if }Q\equiv \amod{7} {8},\end{cases}
$$
which, combined with (\ref{eq:1st}), yields that
$\nu_2(S_{4,k})\ge7$ for all integers $k$.
\end{proof}
\section{Acknowledgments}
We thank the two referees for time spent reading this paper and
writing up comments and suggestions. One of the referees pointed out reference
\cite{Pan}.
\begin{thebibliography}{99}
\bibitem{Ba} Christian Ballot, Lucas sequences with cyclotomic root field,
submitted preprint, 120 pages.
\bibitem{Car} R. D. Carmichael, On the numerical factors of the
arithmetic forms $\alpha^n\pm\beta^n$, {\it Ann. of Math.\/}, {\bf 15},
(1913--14), 30--48, 49--70.
\bibitem{Cho} S. Chowla, Leudesdorf's generalization of Wolstenholme's theorem,
{\it J. London Math. Soc.\/}, {\bf 9} (1934), 246.
\bibitem{HW} G. H. Hardy and E. M. Wright, {\it An Introduction to the
Theory of Numbers}, Clarendon Press, 1960.
\bibitem{Ho} C. Hooley, On Artin's conjecture, {\it J. reine angew.
Math.\/} {\bf 225} (1967), 209--220.
\bibitem{Ja} G. J. Janusz, {\it Algebraic Number Fields}, Academic
Press, 1973.
\bibitem{KW1} William Kimball and William Webb, A congruence for
Fibonomial coefficients modulo $p^3$, {\it Fibonacci Quart.\/}, {\bf
33} (1995), 290--297.
\bibitem{KW2} William Kimball and William Webb, Some generalizations of
Wolstenholme's theorem, in {\it Applications of Fibonacci Numbers}
Vol.\ 8, Kluwer, 1999,
pp.\ 213--218.
\bibitem{Leu} C. Leudesdorf, Some results in the elementary theory of
numbers, {\it Proc. London Math. Soc.\/}, {\bf 20} (1889), 199--212.
\bibitem{Lu1} \'Edouard Lucas, Th\'eorie des fonctions simplement
p\'eriodiques, {\it Amer. J. Math.\/}, {\bf 1} (1878), 184--240,
289--321.
\bibitem{Lu2} \'Edouard Lucas, {\it Th\'eorie des Nombres}, Librairie
scientifique et technique Albert Blanchard, 1961.
\bibitem{MR} Richard J. McIntosh and Eric L. Roettger, A search for
Fibonacci-Wieferich and Wolstenholme primes, {\it Math. Comp.\/}, {\bf
76} (2007), 2087--2094.
\bibitem{Pan} Hao Pan, A generalization of Wolstenholme's harmonic
series congruence, {\it Rocky Mountain J. Math.\/}, {\bf 38} (2008),
1263--1269.
\bibitem{Rib} Paulo Ribenboim, The Fibonacci numbers and the Artic
Ocean, Proceedings of the 2nd Gauss Symposium. Conference A: {\it
Mathematics and Theoretical Physics\/}, de Gruyter, 1995, pp. 41--83.
\bibitem{Wi} Hugh C. Williams, {\it \'Edouard Lucas and Primality
Testing}, Wiley, 1998.
\bibitem{Wo} Joseph Wolstenholme, On certain properties of prime
numbers, {\it Quarterly J. Pure Applied Math.\/}, {\bf 5}
(1862), 35--39.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11A07.
\noindent \emph{Keywords: }
Lucas sequence, rank of appearance, congruence, Wolstenholme,
Leudesdorf.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 6 2012;
revised version received October 8 2012.
Published in {\it Journal of Integer Sequences}, October 8 2012.
Minor typographical corrections, November 24 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}