\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage{microtype} 
\usepackage{cite} 
\usepackage{enumitem}

\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{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\usepackage{dsfont}
\usepackage{comment}

\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}{\underline{#1}}}

\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}
\newtheorem{notation}[theorem]{Notation}

\def\A{\alpha}
\def\B{\beta}
\def\ord{{\operatorname{ord}}}
\newcommand\modd[2]{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\legendre}[2]{\displaystyle \Bigg(\frac{#1}{#2}\Bigg)}

\begin{document}
\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On the Period mod $m$ of \\
\vskip .02in
Polynomially-Recursive Sequences: \\
\vskip .1in
a Case Study}
\vskip 1cm 
\large
Cyril Banderier\\
Laboratoire d'Informatique de Paris Nord\\ 
Universit\'e de Paris Nord\\
93430 Villetaneuse\\
France\\
\href{mailto:Cyril.Banderier@lipn.univ-paris13.fr}{\tt Cyril.Banderier@lipn.univ-paris13.fr}\\
\ \\
Florian Luca\\
School of Mathematics\\
University of the Witwatersrand\\
Wits 2050, Johannesburg\\
South Africa\\ 
\href{mailto:florian.luca@wits.ac.za}{\tt florian.luca@wits.ac.za}\\
and\\
Research Group of Algebraic Structures and Applications\\ 
King Abdulaziz University\\ 
21589 Jeddah\\
Saudi Arabia\\
and\\
Centro de Ciencias Matem\'aticas\\
Universidad Nacional Aut\'onoma de M\'exico (UNAM)\\
58089 Morelia\\ 
Mexico\\
\end{center}


\begin{abstract}
Polynomially-recursive sequences have a periodic behavior mod $m$,  
when the leading coefficient of the corresponding recurrence is invertible mod $m$. 
In this paper, we analyze the period mod $m$ of a class of second-order polynomially-recursive sequences.
Starting with a problem originally coming from an enumeration of avoiding pattern permutations,
we give a generalization which appears to be linked with nice elementary number theory notions (the Carmichael function, algebraic integers, quadratic residues, Wieferich primes).
\end{abstract}

\section{Introduction}
\label{sec:introduction}

In his analysis of sorting algorithms, Knuth introduced the notion of forbidden pattern 
in permutations, which later became a field of research per se~\cite{Knuth98}. 
By studying the basis of such forbidden patterns for 
permutations reachable with $k$ right-jumps from the identity permutation, 
the authors of~\cite{BanderierBarilMoreiraDosSantos17} discovered that the permutations of size $n$ in this basis 
were enumerated by the sequence of integers $(b_n)_{n\ge 0}$ given by $b_0=1,~b_1=0$, \begin{equation}\label{rec}
b_{n+2}=2n b_{n+1}+(1+n-n^2)b_n\qquad {\text{\rm for~all}}\quad n\ge 0.
\end{equation}
This is sequence \seqnum{A265165} 
in the OEIS\footnote{OEIS stands for the On-Line Encyclopedia of Integer Sequences; see \href{https://oeis.org}{https://oeis.org}.}.
It starts as follows:  1, 0, 1, 2, 7, 32, 179, 1182, 8993, 77440, 744425, 7901410, 91774375\dots \ .

\smallskip
Such a sequence defined 
by a recurrence with polynomial coefficients in $n$ is called \mbox{{\em P-recursive}} (for {\em polynomially recursive}).
Some authors also call such sequences {\em holonomic}, or {\em D-finite}
(see, e.g., \cite{Stanley99,FlajoletSedgewick09,Gessel90,PetkovsekWilfZeilberger96}).   
The D-finite (for {\em differentially finite}) terminology comes from the fact that a sequence $(f_n)_{n\ge 0}$ satisfies a linear recurrence with polynomial coefficients in $n$ 
if and only if its generating function $F(z)=\sum_{n\geq 0} f_n z^n$ satisfies a linear differential equation with polynomial coefficients in $z$. 
Accordingly, P-recursive sequences and D-finite functions satisfy many closure properties: this contributes
to make them  ubiquitous in combinatorics, number theory, analysis of algorithms, computer algebra, mathematical physics, etc.
It is not always the case that such sequences have a closed form. 
In our case, the generating function of $(b_n)_{n\ge 0}$ has in fact a nice closed form involving the golden ratio. Indeed, putting 
\begin{equation*}
\A:=\frac{1+{\sqrt{5}}}{2}
\text{\quad and \quad} \B:=\frac{1-{\sqrt{5}}}{2}
\end{equation*}
for the two roots of the quadratic equation $x^2-x-1=0$, it was shown in \cite{BanderierBarilMoreiraDosSantos17} 
that the exponential generating function of $(b_n)_{n\ge 0}$, namely 
\begin{equation}
\label{eq:B}
B(x)=\sum_{n\ge 0} b_n\frac{x^n}{n!},\qquad {\text{satisfies}}\quad 
B(x)= \frac{\beta}{\beta-\alpha} (1-x)^{\alpha}+ \frac{\alpha}{\alpha-\beta} (1-x)^{\beta}.
\end{equation}

It should be stressed here that our sequence $(b_n)_{n\ge 0}$ 
is an instance of a noteworthy phenomenon:
it is one of the rare combinatorial sequences exhibiting an irrational exponent in its asymptotics: 
\begin{equation*}
\frac{b_n}{n!}\sim \frac{\A}{ \sqrt{5} \Gamma(\A-1)} {n^{\A-2}}(1+o(1))\qquad {\text{\rm as}}\quad n\to\infty,
\end{equation*}
where $\Gamma(z)=\int_0^{+\infty} t^{z-1}\exp(-t)dt$ is the Euler gamma function. 
We refer to the wonderful book of Flajolet and Sedgewick~\cite{FlajoletSedgewick09} 
for a few other examples of such a phenomenon in analytic combinatorics, 
and to~\cite[Section 4]{BanderierBarilMoreiraDosSantos17} 
for further comments on the links between G-functions 
and (ir)rational exponents in the asymptotics of the coefficients.

P-recursive sequences are also of interest in number theory, where
there is a vast literature analyzing the modular congruences of famous sequences,
e.g., for the binomial coefficients, or the Fibonacci, Catalan, Motzkin, Ap\'ery numbers, see~\cite{Gessel84,DeutschSagan06, XinXu11, RowlandZeilberger14, KauersKrattenthalerMueller11}.
For example, the Ap\'ery numbers satisfy $A(p^e q) = A(p^{e-1} q) \bmod p^{3e}$, 
in which the exponent $3e$ in the modulus grows faster than the exponent $e$ in the function argument. 
This phenomenon is sometimes called ``supercongruence'', and finds its roots in seminal works by Kummer and Ramanujan 
(see~\cite{GuoZudilin19,OsburnSchneider09,Straub19} for more recent advances on this topic).
Accordingly, many articles consider sequences modulo $m=2^r$, or $m=3^r$, or variants of power of a prime number.

We now restate an important result which holds for any $m$ (not necessarily the power of a prime number).

\begin{theorem}[Congruences and periods for P-recursive sequences~{\cite[Theorem 7]{BanderierBarilMoreiraDosSantos17}}]\qquad\newline \label{thm:congru}
Consider any P-recurrence of order $r$: 
\begin{equation*}
P_0(n) u_n = \sum_{i=1}^r P_i(n) u_{n-i}\,,
\end{equation*}
where the polynomials $P_0(n),\dots, P_r(n)$ belong to ${\mathbb Z}[n]$,
and where the polynomial $P_0(n)$ is invertible $\bmod\ m$. 
Then the sequence $(u_n \bmod m)_{n\geq 0}$ is eventually periodic\footnote{
An eventually periodic sequence of period $p$ is a sequence for which $u_{n+p} = u_n$ for all $n\geq n^*$ ($n^*$ is called the preperiod). 
Some authors use the terminology ``ultimately periodic'' instead. In the sequel, as the context is clear, 
we will often omit the word ``eventually''.}. In particular, sequences such that $P_0(n)=1$ are periodic $\bmod\ m$.
Additionally, the preperiod and the period~$p$ are bounded by $m^{2r+1}$, 
therefore one can  efficiently compute them via the Knuth--Floyd cycle-finding algorithm (the tortoise and the hare algorithm).
\end{theorem}


\smallskip

N.B.: It is not always the case that P-recursive sequences are periodic mod $p$. E.g.,
it was proven in~\cite{KlazarLuca05} 
that Motzkin numbers are not periodic mod $m$,
and it seems that
\begin{equation*}
(n+3) (n+2) u_n=8 (n-1)(n-2) u(n-2)+(7 n^2+7 n-2) u(n-1)\,, \quad u_0=0, u_1=1\,,
\end{equation*}
is also not periodic mod $m$, for any $m>2$
(this P-recursive sequence counts a famous class of permutations, namely, the Baxter permutations).
This is coherent with Theorem~\ref{thm:congru},
as the leading term in the recurrence (the factor $(n+3)(n+2)$) is not invertible mod $m$, for infinitely many $n$.

\bigskip

For our sequence $(b_n)_{n\ge 1}$ (defined by recurrence~\eqref{rec}),
this theorem explains the periodic behavior of $b_n \bmod m$. Thanks to the bounds mentioned in Theorem~\ref{thm:congru},
we can get $b_n \bmod m$, by brute-force computation, for any given $m$.
For example $b_n \bmod 15$ is periodic of period~$12$ (after a preperiod $n^*=9$):
\begin{equation*}
(b_n \bmod 15)_{n\ge 9}= (10, 5, 10, 10, 0, 10, 5, 10, 5, 5, 0, 5)^\infty.
\end{equation*}
The period can be quite large, for example $b_n \bmod  3617$ has period $26158144$.
More generally, for every positive integer $m$, the sequence $(b_n \bmod m )_{n\ge 1}$ is eventually periodic, for some period $p$ depending on $m$, as defined in the footnote on the previous page.
For each $m$, let $T_m$ be the smallest possible period~$p$. In this paper, we study some properties of $(T_m)_{m\ge 2}$. 

This is sequence \seqnum{A306699} in the OEIS;
here are its first few values $T_2,\dots,T_{100}$:\\ {\footnotesize
2, 12, 8, 1, 12, 84, 8, 36, 2, 1, 24, 104, 84, 12, 16, 544, 36, 1, 8, 84, 2, 1012, 24, 1, 104, 108, 168, 1, 12, 1, 32, 12, 544, 84, 72, 2664, 2, 312, 8, 1, 84, 3612, 8, 36, 1012, 4324, 48, 588, 2, 1632, 104, 5512, 108, 1, 168, 12, 2, 1, 24, 1, 2, 252, 64, 104, 12, 2948, 544, 3036, 84, 1, 72, 10512, 2664, 12, 8, 84, 312, 1, 16, 324, 2, 13612, 168, 544, 3612, 12, 8, 1, 36, 2184, 2024, 12, 4324, 1, 96, 18624, 588, 36, 8.}\\
\noindent Do you detect some nice patterns in this sequence? 
This is what we tackle in the next section.

\section{Periodicity mod \texorpdfstring{$m$}{m} and links with number theory}\label{Sec2}

Our main result is the following.

\begin{theorem}\label{theo2}
Let $(b_n)_{n\ge 0}$ be the sequence defined by the recurrence of Formula~\ref{rec}. The period $T_m$ of this sequence $b_n$ mod $m$ satisfies:
\begin{enumerate}[label=(\textit{\alph*}),ref=Part (\alph*)]
\item \label{part_a}
 If $m=p_1^{e_1}\cdots p_k^{e_k}$ (where $p_1,\dots,p_k$ are distinct primes), then\footnote{As usual, $\lcm$ stands for the {\em least common multiple}.} 
\begin{equation*}
T_m=\lcm(T_{p_1^{e_1}},\dots,T_{p_k^{e_k}}).
\end{equation*}
\item  \label{part_b}
We have $T_m=1$ if and only if $m$ is the product of primes $p\equiv \modd{0,1,4} {5}$.
\item  \label{part_c}
For every prime $p$, we have\footnote{We denote by $\ord_p(5)$ the \textit{order} of $5$ modulo~$p$, i.e., the smallest $k>0$ such that $5^k \equiv \modd{1}{p}$.\label{footnote_order}} $T_p\mid 2p\, \ord_5(p)$.
\item  \label{part_d}
If $T_m>1$ then $2\mid T_m$ if $m$ is even, and $4 \mid T_m$ if $m$ is odd.
\item  \label{part_e}
For $m\geq 3$, we have $T_m=2$ if and only if $m$ is even and $\frac{m}{2}$ is the product of primes $p\equiv \modd{0,1,4} {5}$.
\item   \label{part_f}
For every prime $p$ and $r\in {\mathbb N}$, 
we have $T_{p^r}\mid 2p^r \ord_5(p)$.
\end{enumerate}
\end{theorem}

The function $T_m$ thus shares some similarities with the Carmichael function introduced in~\cite{Carmichael12}, 
and it is expected that its asymptotic behavior is also similar (following, e.g., the lines of~\cite{ErdosPomeranceSchmutz91}).
In this article, we focus on the rich arithmetic properties of this function. 
Note that Theorem~\ref{theo2} allows computing $T_m$ in a much faster way than the 
brute-force algorithm mentioned in Section~\ref{sec:introduction}:
the complexity goes from $m^{2r+1}$ via brute-force to $\ln(m)^3$ via Shor's factorization algorithm~\cite{Shor97}
(or to sub-exponential complexity in $\ln(m)$ with other efficient algorithms, if one does not want to rely on the use of quantum computers!).

\bigskip
\noindent {\it Proof of~\ref{part_a}.} The proof will use a little preliminary result. 
We call $T_m$ the ``eventual period of the sequence mod $m$'', or, for short, the ``period'', even if the sequence starts with some terms which do not satisfy the periodic pattern. 
The following lemma holds for all eventually periodic sequences of integers.

\begin{lemma}
$T_m$ divides all other periods of $(u_n)_{n\ge 0}$ modulo $m$. 
\end{lemma} 

\begin{proof}
Let $T_m=a$ and assume there is $b$ (not a multiple of $a$) which is also a period modulo~$m$. Thus, there are $n_a,~n_b$ such that $u_{n+a}\equiv \modd{u_n}{m}$ for all $n>n_a$ and 
$u_n\equiv \modd{u_{n+b}}{m}$ for all $n>n_b$. Let $d=\gcd(a,b)$. 
By B{\'e}zout's identity, one has then $d=Aa+Bb$ for some integers $A,~B$. Let $n_{a,b}=\max\{n_a,n_b\}+|A|a+|B|b$ 
and assume that $n>n_{a,b}$. Then $u_{a+d}=u_{n+Aa+Bb}\equiv u_{(n+Aa)+bB}\equiv u_{n+Aa}\equiv \modd{u_n}{m}$ so $d<a$ is a period of $(u_n)_{n\ge 0}$ modulo $m$, contradicting the minimality of $a$. 
\end{proof}

An immediate consequence is the following:

\begin{corollary}
\label{cor1}
We have $T_{\lcm(m_1,\dots,m_r)}=\lcm(T_{m_1},\dots,T_{m_r})$.
\end{corollary}
\begin{proof}
First consider $r=2$, and let $a:=m_1$, $b:=m_2$.
Since $\lcm(T_a,T_b)$ is a multiple of both $T_a$ and $T_b$, it follows that it is a period of $(u_n)_{n\ge 0}$ modulo both $a$ and $b$, so modulo $\lcm(a,b)$. It remains to prove that it is the minimal one. To this aim, suppose that $T_{\lcm(a,b)}<\lcm(T_a,T_b)$.
Then either $T_a\nmid T_{\lcm(a,b)}$ or $T_b\nmid T_{\lcm(a,b)}$. Since the two cases are similar, we only deal with the first one. 
In this case we would have that both $T_a$ and $T_{\lcm(a,b)}$ would be periods modulo~$a$.
By the previous lemma, this would force $\gcd(T_a,T_{\lcm(a,b)})<T_a$, which would obviously be a contradiction. 
Now, a trivial induction on the number $r\ge 2$ gives that
\begin{equation*}
T_{\lcm(m_1,\dots,m_r)}=\lcm(T_{m_1},\dots,T_{m_r})
\end{equation*}
holds for all positive integers $m_1,\dots,m_r$. 
\end{proof}


In particular, Part (a) of Theorem~\ref{theo2} holds: $T_m=\lcm(T_{p_1^{e_1}},\dots,T_{p_k^{e_k}})$. Let us now tackle the proofs of Parts (b)--(f).

\bigskip
\noindent{\it Proof of~\ref{part_b}.} We use the generating function~\eqref{eq:B}, which tells us that
\begin{equation}
[x^n] B(x) = \frac{b_n}{n!}=\frac{(-1)^n}{\sqrt{5}}\left(\A\binom{\B}{n}-\B \binom{\A}{n}\right).
\end{equation}
Thus, 
\begin{equation}
b_n = \frac{(-1)^{n-1}}{\sqrt{5}} \left(\B \A(\A-1)\cdots (\A-(n-1))-\A \B(\B-1)\cdots (\B-(n-1))\right).
\end{equation}
By Fermat's little theorem, 
\begin{equation}
\label{eq:X}
\prod_{k=0}^{p-1} (X-k)=X^p-X\pmod p.
\end{equation}
Now, assume  that $p\equiv \modd{1,4}{5}$. Then 
\begin{equation*}
\prod_{k=0}^{p-1} (\A-k)\equiv \A^p-\A \equiv 0\pmod p,
\end{equation*}
where for the last congruence we used the law of quadratic reciprocity:
since $p\equiv \modd{1,4}{5}$, we have 
\begin{equation*}
\legendre{5}{p}=\legendre{p}{5}=1,
\end{equation*}
 where 
 $\legendre{\bullet}{p}$ is the Legendre symbol. Thus, 
\begin{equation}
\label{eq:alpha}
\A^p=\left(\frac{1+{\sqrt{5}}}{2}\right)^p\equiv \frac{1+{\sqrt{5}}\cdot 5^{(p-1)/2}}{2^p}\equiv \A \pmod p,
\end{equation}
because $5^{(p-1)/2}\equiv \legendre{5}{p}\equiv \modd{1} {p}$ by Euler's criterion. 

In the above and in what follows, for two algebraic integers $\delta,~\gamma$ and an integer $m$ we write $\delta\equiv \modd{\gamma}{m}$ if the number $(\delta-\gamma)/m$ is an algebraic integer.
This shows that
\begin{equation*}
\frac{1}{p} \prod_{k=0}^{p-1} (\A-k)
\end{equation*}
is an algebraic integer. The same is true with $\A$ replaced by $\B$. Now take $r\ge 1$ be any integer and take $n\ge pr$. Then, for each $\ell=0,1,\dots,r-1$, we have that both
\begin{equation*}
\frac{1}{p}\prod_{k=0}^{p-1} (\A-(p\ell+k))\quad {\text{\rm and }}\qquad \frac{1}{p}\prod_{k=0}^{p-1} (\B-(p\ell+k))
\end{equation*}
are algebraic integers. Thus, if $n\ge pr$, then 
\begin{equation*}
\frac{{\sqrt{5}} b_n}{p^r}=(-1)^{n-1}\left(\B\prod_{\ell=0}^{r-1}\prod_{k=0}^{p-1} (\A-(p\ell+k))\prod_{k=pr}^{n-1} (\A-k)-\A\prod_{\ell=0}^{r-1}\prod_{k=0}^{p-1} (\B-(p\ell+k))\prod_{k=pr}^{n-1} (\B-k)\right)
\end{equation*}
is an algebraic integer. Thus, $5b_n^2/p^{2r}$ is an algebraic integer and a rational number, so an integer. Since $p\ne 5$, it follows that $p^{2r}\mid b_n^2$, so $p^r\mid b_n$ for $n\ge pr$. This shows that
$T_{p^r}=1$ for all such primes $p$ and positive integers $r$. The same is true for $p=5$. There we use that $\A-3={\sqrt{5}}\B$, so ${\sqrt{5}}\mid \A-3$. Thus, if $n\ge 10r$, we have that 
\begin{equation*}
\prod_{k=1}^n (\A-k)\quad {\text{\rm is~a~multiple~of}}\quad \prod_{\ell=0}^{2r-1} (\A-(3+5\ell))\quad {\text{\rm in}}\quad {\mathbb Z}[(1+{\sqrt{5}})/2],
\end{equation*}
which in turn is a multiple of $5^r={\sqrt{5}}^{2r}$ in ${\mathbb Z}[(1+{\sqrt{5}})/2]$. Thus, if $n\ge 10r$, then $5^r\mid b_n$. This shows that also $T_{5^r}=1$ and in fact, 
$m\mid b_n$ for all $n>n_m$ if $m$ is made up only of primes $\modd{0,1,4}{5}$. This finishes the proof of (b).

\bigskip
\noindent{\it Proof of~\ref{part_c}.} The claim is satisfied for $p=2$,
as $(b_n \bmod 2)_{n\geq 0}=(1,0)^\infty$, thus $T_2=2 \mid 4$.
Consider now $p>2$. By~\ref{part_b}, it suffices to consider odd primes $p\equiv \modd{2,3}{5}$.
Evaluating Formula~\eqref{eq:X} at~$\A=\frac{1+\sqrt{5}}{2}$, one has
\begin{equation*}
\prod_{k=0}^{p-1} (\A-k)\equiv \A^p-\A\pmod p. 
\end{equation*}
Since $5^{(p-1)/2}\equiv -1\pmod p$, the argument from~\eqref{eq:alpha} shows that $\A^p\equiv \modd{\B}{p}$. Thus
\begin{equation*}
\prod_{k=1}^{2p} (\A-k)=\prod_{k=1}^p (\A-k) \prod_{k=p+1}^{2p} (\A-k)\equiv (\B-\A)^2\equiv 5\pmod p.
\end{equation*}
The same is true for $\A$ replaced by $\B$. Thus, for $n>2p$, it follows that we have
\begin{align*}
b_{n+2p} & =  \frac{(-1)^{n+2p-1}}{{\sqrt{5}}} \left(\B \prod_{k=0}^{n+2p-1} (\A-k)-\A \prod_{k=0}^{n+2p-1} (\B-k)\right)\\
& \equiv  \frac{(-1)^{n-1}}{{\sqrt{5}}} 5 \left(\B\prod_{k=0}^{n-1} (\A-k)-\A \prod_{k=0}^{n-1} (\B-k)\right)\pmod p\\
& \equiv  5b_n\pmod p.
\end{align*}  
Applying this $k$ times, we get
\begin{equation*}
b_{n+2pk}\equiv 5^k b_n\pmod p.
\end{equation*}
Taking $k=p-1$ and applying Fermat's little theorem $5^{p-1}\equiv \modd{1}{p}$, 
we get $T_p\mid 2p(p-1)$.
We can optimize this idea by taking $k=\ord_p(5)$ (this notation is defined in footnote~\ref{footnote_order}), 
this gives the stronger wanted claim: $T_p\mid 2p\, \ord_p(5)$.

\bigskip
\noindent{\it Proof of~\ref{part_d}.} 
By (a), we know that $T_p \mid T_{pm}$.
Taking $p=2$, one gets $2 \mid T_m$. 
Now, if $T_m>1$, by (b), there is at least a prime $p= \modd{2,3}{5}$ 
such that $p \mid m$.
We then have $T_p \mid T_m$ by (a). We now prove by contradiction that $T_p$ is a multiple of $4$.

Take a prime $p\geq 3$ and assume $\nu_2(T_p)<2$,
where $\nu_q(a)$ is the exponent of $q$ in the factorization of $a$. That is, $T_p$ would either be odd or $2$ times an odd number. Since $T_p\mid 2p(p-1)$, it would follow that if we write $p-1=2^a k$, where $k$ is odd, then $T_p\mid 2pk$. Thus, one would have
\begin{equation}\label{eqmodp}
b_{n}\equiv b_{n+2pk}\equiv 5^k b_n\pmod p
\end{equation}
for all $n>n_p$. Since $p=\modd{2,3}{5}$, $5$ is not a quadratic residue, 
and thus $5^k\not\equiv \modd{1}{p}$ (since $-1\equiv 5^{(p-1)/2}\equiv \modd{(5^k)^{2^{a-1}}}{p}$). So, the above congruence~\eqref{eqmodp} would imply that $p\mid (5^k-1)b_n$ but
$p\nmid 5^k-1$, so $b_n\equiv \modd{0}{p}$ for all large $n$. Take $n$ and $n+1$ and rewrite what we got, i.e., $b_n\equiv b_{n+1}\equiv \modd{0}{p}$ in ${\mathbb Z}[\A]/p{\mathbb Z}[\A]$ as 

\begin{align*}
b_n =\B \prod_{k=0}^{n-1} (\A-k)-\A \prod_{k=0}^{n-1} (\B-k) & \equiv  0\pmod p \,,\\
b_{n+1} =\B \left(\prod_{k=0}^{n-1} (\A-k)\right)(\A-n)-\B\left(\prod_{k=0}^{n-1}(\B-k)\right)(\B-n) & \equiv  0\pmod p.
\end{align*}
We treat this as a linear system in the two unknowns 
\begin{equation*}
(X,Y)=\left(\B\prod_{k=0}^{n-1}(\A-k),\A \prod_{k=0}^{n-1} (\B-k)\right)
\end{equation*} 
in the field with $p^2$ elements ${\mathbb Z}[\A]/p{\mathbb Z}[\A]$. This is homogeneous. None of $X$ or $Y$ is $0$ since $p$ cannot divide $\B\prod_{k=0}^{n-1}(\A-k)$. Thus, it must be that the determinant of the above 
matrix is~$0$~modulo~$p$, but this is 
\begin{equation*}
\left|\begin{matrix}1 & -1 \\ \A-n & -(\B-n)\end{matrix}\right|={\sqrt{5}},
\end{equation*}
which is invertible modulo~$p$. Thus, indeed, it is not possible that both $b_n$ and $b_{n+1}$ are multiples of~$p$ for all large $n$, getting a contradiction. 
This shows that $T_p$ is a multiple of $4$.

\bigskip
\noindent{\it Proof of~\ref{part_e}.}
Let $m$ be of shape different from the one required in Part (b), i.e., $m$ now has at least one prime $p\equiv \modd{2,3} {5}$ such that $p\mid m$. Then $4\mid T_p$ by what we have done above, and so $4\mid T_m$ by (a). Thus, such $m$ cannot participate in
the situations described either at (d) or (e). Further, one has $T_4=8$ as 
$(b_n \bmod 4 )_{n\ge 0} = (1,0,1,2,3,0,3,2)^\infty$.
Thus, if $4\mid m$, then $8\mid T_m$. Hence, if $T_m=2$, then the only possibility is that $2\mid m$ and $m/2$ is a product of primes congruent to $0,1,4$ modulo $5$.
Conversely, if $m$ has such structure then $T_m=2$ by (a) and the fact that $T_2=2$ and $T_{p^r}=1$ for all odd prime power factors $p^r$ of $m$. 
This ends the proof of (e).

\bigskip
\noindent{\it Proof of~\ref{part_f}.} Finally, (f) is based on a preliminary result: a slight generalization of~\eqref{eq:X}, namely
\begin{equation}
\label{eq:ptor}
\prod_{k=0}^{p^r-1} (X-k)\equiv (X^p-X)^{p^{r-1}}\pmod {p^r}
\end{equation}
valid for all odd primes $p$ and $r\ge 1$. Let us prove~\eqref{eq:ptor} by induction on~$r$. We first prove it for $r=2$. We return to~\eqref{eq:X} and write
\begin{equation*}
\prod_{k=0}^{p-1} (X-k)=X^p-X+pH_1(X),
\end{equation*}
where $H_1(X)\in {\mathbb Z}[X]$. Changing $X$ to $X-p\ell$ for $\ell=0,1,\dots,p-1$, we get that
\begin{equation*}
\prod_{k=0}^{p-1} (X-(p\ell+k))=(X-p\ell)^p-(X-p\ell)+pH(X-p\ell)\equiv (X^p-X-pH(X))-p\ell\pmod {p^2}.
\end{equation*}
In the above, we used the fact that $H(X-p\ell)\equiv \modd{H(X)}{p}$. Thus,
\begin{align*}
\prod_{k=0}^{p^2-1} (X-k) & =  \prod_{\ell=0}^{p-1} \prod_{k=0}^{p-1} (X-(p\ell+k))\\
 & \equiv  \prod_{k=0}^{p-1} ((X^p-X-pH(X))-p\ell)\pmod {p^2}\\
 & \equiv  (X^p-X-pH(X))^p-(X^p-X-pH(X))^{p-1} p\left(\sum_{\ell=0}^{p-1} \ell\right)\pmod {p^2}\\
 & \equiv  (X^p-X)^p-(X^p-X-pH(X))^{p-1} p\left(\frac{p(p-1)}{2}\right)\pmod {p^2}\\
 & \equiv  (X^p-X)^p\pmod {p^2}.
 \end{align*}
 In the above, we used the fact that $p$ is odd so $p(p-1)/2$ is a multiple of~$p$. This proves~\eqref{eq:ptor} for $r=2$. Now,
assuming that~\eqref{eq:ptor} holds for $p^r$, for some $r\ge 2$, we get that for all $\ell\ge 0$, we have
\begin{align*}
 \prod_{k=0}^{p^r-1} (X-(p^r\ell+k)) & \equiv ((X-p^r\ell)^p-(X-p^r\ell))^{p^{r-1}}+p^rH_r(X-p^r\ell)\pmod {p^{r+1}}\\
 & \equiv  (X^p-X)^{p^{r-1}}+p^rH_r(X)\pmod {p^{r+1}},
 \end{align*}
 where $H_r(X)\in {\mathbb Z}[X]$. This allows concluding the induction step, and thus the generalization~\eqref{eq:ptor} that we wanted: 
 \begin{align*}
 \prod_{k=0}^{p^{r+1}-1} (X-k) & =  \prod_{\ell=0}^p \prod_{k=0}^{p^r-1} (X-(p^r\ell+k))\\
 & \equiv  ((X^p-X)^{p^{r-1}}+p^r H_r(X))^p \pmod {p^{r+1}} \\
 & \equiv  (X^p-X)^{p^r}\pmod {p^{r+1}}.
 \end{align*}

Equipped with this preliminary result, 
letting $p>2$ be congruent to $\modd{2,3}{5}$, evaluating the above identity in~$\A$, and using that $\A^p\equiv \modd{\B}{p}$, we get that
\begin{equation*}
\prod_{k=0}^{p^r-1} (\A-k)\equiv (X^p-X)^{p^{r-1}}\equiv (\A^p-\A)^{p^{r-1}}\equiv (\B-\A)^{p^{r-1}}\pmod {p^r}.
\end{equation*}
This shows that
\begin{equation*}
\prod_{k=0}^{2p^r-1} (\A-k)\equiv (\B-\A)^{2p^{r-1}}\equiv 5^{p^{r-1}}\pmod {p^r}.
\end{equation*}
The same is true for $\B$; this leads to 
\begin{equation*}
b_{n+2p^r}\equiv \frac{(-1)^{n+2p^r-1}}{{\sqrt{5}}} 5^{p^{r-1}} \left(\B\prod_{k=0}^{n-1}(\A-k)-\A\prod_{k=0}^{n-1} (\B-k)\right)\equiv 5^{p^{r-1}} b_n\pmod {p^r}.
\end{equation*}
Thus, applying this $k$ times, we get
\begin{equation}\label{eqpr}
b_{n+2p^r k} \equiv 5^{p^{r-1}k} b_n\pmod {p^r}.
\end{equation}
By Euler's theorem $a^{\phi(n)}\equiv \modd{1}{n}$,
one has
 $5^{p^{r-1}(p-1)}\equiv \modd{1}{p^r}$.
 Thus, taking $k=p-1$ in~\eqref{eqpr}, we get $b_{n+2p^{r}(p-1)}\equiv \modd{b_n}{p^r}$. Therefore, $T_{p^r}\mid 2p^r (p-1)$. \\
As in the proof of (c), we can optimize this idea; indeed $\ord_5(p^r)=p^{r-1} \ord_5(p)$
 and thus, taking $k=\ord_5(p)$, one gets the wanted claim:  $T_{p^r}\mid 2p^{r} \ord_5(p)$. 

\bigskip
Finally, it remains to prove (f) for $p=2$. Here, by inspection, we have 
\begin{equation*}
\prod_{k=0}^7 (X-k)\equiv (X^2-X)^4\pmod 4.
\end{equation*}
By induction on $r\ge 2$, one shows that
\begin{equation*}
\prod_{k=0}^{2^{r+1}-1}(X-k)\equiv (X^2-X)^{2^r}\pmod {2^r}.
\end{equation*}
Evaluating this in $\A$, we get 
\begin{equation*}
\prod_{k=0}^{2^{r+1}-1} (\A-k)\equiv (\A^2-\B)^{2^r}\equiv 5^{2^{r-1}}\pmod {2^r}.
\end{equation*}
The same holds for $\B$, so this gives
\begin{align*}
b_{n+2^{r+1}} & \equiv  \frac{(-1)^{n+2^{r+1}-1}}{\sqrt{5}} 5^{2^{r-1}} \left(\B\prod_{k=0}^{n-1}(\A-k)-\A\prod_{k=0}^{n-1} (\B-k)\right) \equiv  5^{2^{r-1}} b_n \equiv b_n\pmod {2^r}\,,
\end{align*}
showing that $T_{2^r}\mid 2^{r+1}$ for all $r\ge 2$. 

\section{Comments and generalizations}

Along the proof of our main result we showed that if $p\equiv \modd{2 \text{ or } 3} {5}$, then 
\begin{equation*}
b_{n+2p}\equiv 5b_{n}\pmod p.
\end{equation*}
 From here we deduced that $T_p\mid 2p(p-1)$ via the fact that $5^{p-1}\equiv \modd{1} {p}$. One may ask whether it can be the case that 
\begin{equation}\label{Divis}
T_{p^2}\mid 2p(p-1), \text{ for some prime $p$?}
\end{equation}
Well, first of all, it implies  that $5^{p-1}\equiv \modd{1} {p^2}$. 
This makes $p$ a base-$5$ Wieferich prime\footnote{A prime $p$ is a Wieferich prime in base $b$ if $b^{p-1}\equiv 1\pmod {p^2}$.
This notion was introduced (with $b=2$) by Arthur Wieferich in 1909 in his work on Fermat's last theorem~\cite{Wieferich09}.}.
Despite the fact that it is conjectured that there are infinitely many such primes, only 7 base-5 Wieferich primes are currently known! (They are listed as \seqnum{A123692}). 
Amongst them, only $p=2,40487,1645333507$, and $6692367337$ are additionally congruent to $\modd{2} {5}$, and none is known to be congruent to $\modd{3} {5}$. 
Note that the condition of $p\equiv \modd{2 \text{ or } 3} {5}$ being base-$5$ Wieferich is not sufficient to have the divisibility property~\eqref{Divis}. 
A close analysis of our arguments shows that 
in addition to be a base-$5$ Wieferich prime, it should also hold that
\begin{equation*}
\prod_{k=0}^{2p-1}(\alpha-k)-5\equiv 0\pmod {p^2}\,,
\end{equation*}
 and if this is the case then indeed $T_{p^2}\mid 2p(p-1)$. 
So, how many other primes could lead to $T_{p^2}\mid 2p(p-1)$? 
Since the integer 
\begin{equation*}
\frac{1}{p} \left(\prod_{k=0}^{2p-1} (\alpha-k)-5 \right) \in {\mathbb Z}[\A]
\end{equation*}
 should be the zero element in the finite field ${\mathbb Z}[\A]/p{\mathbb Z}[\A]$, with $p^2$ elements, it could be that the ``probability'' that this condition happens 
is $1/p^2$. By the same logic, the ``probability'' that $p$ is base-$5$ Wieferich should be $1/p$. 
Assuming these events to be independent, we could infer that the probability that both these conditions hold is $1/p^3$. Then, as the series 
\begin{equation*}
\sum_{p\equiv 2,3\pmod 5} \frac{1}{p^3}
\end{equation*}
is convergent, this heuristically suggests that there should be only finitely many primes $p\equiv \modd{2 \text{ or } 3}{5}$ such that $T_{p^2}\mid 2p(p-1)$.
 
 \medskip
 
Finally, our results apply to other sequences as well. More precisely, let $a,~b$ be integers and let $\alpha,~\beta$ be the roots of $x^2-ax-b$. Let 
\begin{equation*}
B(x)= \frac{\beta}{\beta-\alpha} (1-x)^{\alpha}+ \frac{\alpha}{\alpha-\beta} (1-x)^{\beta}=\sum_{n\ge 0} b_n \frac{x^n}{n!}.
\end{equation*}
Accordingly, the sequence $(b_n)_{n\ge 0}$ satisfies $b_0=1$, $b_1=0$, and, for $n\ge 0$
\begin{equation*}
b_{n+2}=(2n-a+1)b_{n+1}+(b+an-n^2)b_n.
\end{equation*}
What are the periods mod $m$ of such sequences?
\begin{itemize}\item In case $\alpha$ and $\beta$ are rational (hence, integers), $B(x)$ is a rational function, so $b_n=n! u_n$, where $(u_n)_{n\ge 0}$ is binary recurrent with constant coefficients. 
It then follows that $b_n\equiv \modd{0}{m}$ for all $m$ provided $n>n_m$ is sufficiently large. Thus, $T_m=1$. 
\item In case $\alpha,\beta$ are irrational, then we get a result similar to Theorem~\ref{theo2} (where we had $(a,b)=(1,1)$). Namely, 
$b_n\equiv \modd{0}{m}$ for all $n$ sufficiently large whenever $m$ is the product of odd primes $p$ for which the Legendre symbol ${\displaystyle{\left(\frac{\Delta}{p}\right)=0,1}}$, 
where $\Delta=a^2+4b$ is the discriminant of the quadratic $x^2-ax-b$. In case $p$ is odd and ${\displaystyle{\left(\frac{\Delta}{p}\right)=-1}}$, 
we have that $T_p\mid 2p(p-1)$ and $T_p$ is a multiple of $4$. Also, $T_{p^r}\mid 2p^r(p-1)$ 
for all $r\ge 1$ in this case. The proofs are similar. In the case of the prime $2$, one needs to distinguish cases according to the parities of $a,b$. For example, if $a$ and $b$ are odd,
then $\Delta\equiv \modd{5}{8}$, so $2$ is not a quadratic residue modulo $\Delta$, so $T_{2^r}\mid 2^{r+1}$ for all $r\ge 1$, whereas if $a$ is odd and $b$ is even then $T_2=1$. 
\end{itemize}
This concludes our analysis of the periodicity of such P-recursive sequences mod $m$. 

\section{Acknowledgments}

We thank the editor and the referee for comments which improved the quality of our paper. 
This work has been initiated when the second author was invited professor at the Paris Nord University, in April 2018. 
In addition, Florian Luca was supported by the NRF of South Africa
via an A-rated scientist award and the grant CPRR160325161141.

\begin{thebibliography}{10}

\bibitem{BanderierBarilMoreiraDosSantos17}
C.~Banderier, J.-L. Baril, and C.~Moreira Dos~Santos, {Right-jumps \& pattern
  avoiding permutations}, {\em Discrete Math. Theor. Comput. Sci.}
  {\bf 18} (2017), 1--17.

\bibitem{Carmichael12}
R.~D. Carmichael, On composite numbers {$P$} which satisfy the {F}ermat
  congruence {$a^{P-1} \equiv 1 \operatorname{mod} P$}, {\em Amer. Math.
  Monthly} {\bf 19} (1912), 22--27.

\bibitem{DeutschSagan06}
E.~Deutsch and B.~E. Sagan, Congruences for {C}atalan and {M}otzkin numbers and
  related sequences, {\em J. Number Theory} {\bf 117} (2006), 191--215.

\bibitem{ErdosPomeranceSchmutz91}
P.~Erd\H{o}s, C.~Pomerance, and E.~Schmutz, Carmichael's lambda function, {\em
  Acta Arith.} {\bf 58} (1991), 363--385.

\bibitem{FlajoletSedgewick09}
P.~Flajolet and R.~Sedgewick, {\em {A}nalytic {C}ombinatorics}, Cambridge
  University Press, 2009.

\bibitem{Gessel84}
I.~M. Gessel, Combinatorial proofs of congruences.
\newblock In {\em Enumeration and {D}esign}, 
Academic Press, 1984, pp.~157--197. 

\bibitem{Gessel90}
I.~M. Gessel, Symmetric functions and {P}-recursiveness, {\em J. Combin. Theory
  Ser. A} {\bf 53} (1990), 257--285.

\bibitem{GuoZudilin19}
V.~J.~W. Guo and W.~Zudilin, A {$q$}-microscope for supercongruences, {\em Adv.
  Math.} {\bf 346} (2019), 329--358.

\bibitem{KauersKrattenthalerMueller11}
M.~Kauers, C.~Krattenthaler, and T.~W. M{\"u}ller, A method for determining the
  {${\rm mod}\text{-}2^k$} behaviour of recursive sequences, with applications
  to subgroup counting, {\em Electron. J. Combin.} {\bf 18} (2011), Paper 37.

\bibitem{KlazarLuca05}
M.~Klazar and F.~Luca, On integrality and periodicity of the {M}otzkin numbers,
  {\em Aequationes Math.} {\bf 69} (2005), 68--75.

\bibitem{Knuth98}
D.~E. Knuth, {\em Sorting and Searching}, 2nd edition,
The {A}rt of {C}omputer {P}rogramming, {V}ol.~3,
  Addison-Wesley, 1998.

\bibitem{OsburnSchneider09}
R.~Osburn and C.~Schneider, Gaussian hypergeometric series and
  supercongruences, {\em Math. Comp.} {\bf 78} (2009), 275--292.

\bibitem{PetkovsekWilfZeilberger96}
M.~Petkov\v{s}ek, H.~S. Wilf, and D.~Zeilberger, {\em {$A=B$}}, A. K. Peters,
  1996.

\bibitem{RowlandZeilberger14}
E.~Rowland and D.~Zeilberger, A case study in meta-automation: automatic
  generation of congruence automata for combinatorial sequences, {\em J.
  Difference Equ. Appl.} {\bf 20} (2014), 973--988.

\bibitem{Shor97}
P.~W. Shor, Polynomial-time algorithms for prime factorization and discrete
  logarithms on a quantum computer, {\em SIAM J. Comput.} {\bf 26} (1997),
  1484--1509.

\bibitem{Stanley99}
R.~P. Stanley, {\em Enumerative Combinatorics}, {V}ol.~2, Cambridge University
  Press, 1999.

\bibitem{Straub19}
A.~Straub, Supercongruences for polynomial analogs of the {A}p\'{e}ry numbers,
  {\em Proc. Amer. Math. Soc.} {\bf 147} (2019), 1023--1036.

\bibitem{Wieferich09}
A.~Wieferich, Zum letzten {F}ermatschen {T}heorem, {\em J. Reine Angew. Math.}
  {\bf 136} (1909), 293--302.

\bibitem{XinXu11}
G.~Xin and J.-F. Xu, A short approach to {C}atalan numbers modulo {$2^r$}, {\em
  Electron. J. Combin.} {\bf 18} (2011), Paper 177.

\end{thebibliography}



\bigskip\hrule\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B50; Secondary 11B39, 11B85, 05A15.

\noindent \emph{Keywords: }  D-finite function, modular property,
P-recursive sequence, supercongruence, Carmichael function, quadratic
residue, Wieferich prime.

\bigskip\hrule\bigskip

\noindent (Concerned with sequences \seqnum{A123692}, \seqnum{A265165}, and
\seqnum{A306699}.)

\bigskip\hrule\bigskip

\vspace*{+.1in}
\noindent
Received March 11 2019; 
revised versions received March 23 2019; July 25 2019; August 6 2019.
Published in {\it Journal of Integer Sequences}, August 19 2019.  

\bigskip\hrule\bigskip

\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}

.