A prime divisor in a second order recurrence

Question

I am dealing with the test of the OBM (Brasilian Math Olympiad), University level, 2016, phase 2.

As I've said at this topic (question 1), this other (question 2) and this (question 3), I hope someone can help me to discuss this test. Thanks for any help.

The question 3 says:

Let $k\geq 1$ be an integer. We define the sequence $(a_n)_{n\geq0}$ by $a_0=0,a_1=1$ and $a_{n+1}=ka_n+a_{n-1}$ for $n=1,2,\dots$.

Let $p$ be a prime odd number. Call $m(p)$ the smallest positive integer $i$ such that $p\mid a_i$.

Call $T(p)$ the smallest positive integer such that for all $j$ we have $p\mid a_{j+T(p)}-a_j$.

(i) Show that $T(p)\leq m(p)(p-1)$.

(ii) If $T(p)=m(p)(p-1)$, show that $\prod_{{1\leq j\leq T(p)-1}_{j\neq0\pmod {m(p)}}}a_j\equiv (-1)^{m(p)-1}\pmod p$.

I've tried somethings, but don't get anything substantial. I'd like to have clues to this type of problem… In fact, I couldn't at least prove that $m(p)$ always exists.

Thank you.

Answer 1

Let us fix an odd prime $\require{cancel}p$, and let $\bar{a}_n$ be the reduction of $a_n$ modulo $p$, i.e., as members of $\mathbb{Z}/p=\mathbb{F}_p$. There is a standard trick of letting $$ \mathbf{b}_n=\begin{bmatrix}\bar{a}_{n+1}\\\bar{a}_n\end{bmatrix}\in\mathbb{F}_p^2, $$ which converts the second order difference equation into a first-order difference equation (at the cost of having a vector equation rather than a scalar one): $$ \mathbf{b}_{n+1}=T\,\mathbf{b}_n,\quad T:=\begin{bmatrix}k&1\\1 & 0\end{bmatrix},\quad \mathbf{b}_0=\begin{bmatrix}1\\0\end{bmatrix}. $$ So $\mathbf{b}_{n+1}$ depends only on $\mathbf{b}_n$. Note that $\det T=-1$ so $T^{-1}$ exists.

By pigeonhole, there exists $0\leq i<j\leq p^2$ such that $\mathbf{b}_i=\mathbf{b}_j$. Applying $T^{-i}$, you get $\mathbf{b}_{j-i}=\mathbf{b}_0$, and applying $T^n$ gives $\mathbf{b}_{n+j-i}=\mathbf{b}_n$ for all $n$. So $T(p)$ exists and is equal to the minimal period of $(\mathbf{b}_n)_{n\geq 0}$. (This implies existence of $m(p)$, which is clearly $\leq T(p)$ by putting $j=0$ in the definition.)

For (i):

we consider what $\mathbf{b}_{m(p)},\mathbf{b}_{2m(p)},\mathbf{b}_{3m(p)},\dots$ could be. The last coordinate must be $0$, but the first coordinate isn't fixed.

However, we know

Claim: $$a_{km(p)+1}\not\equiv 0\pmod{p}$$ Proof. If $a_{km(p)+1}\equiv 0\pmod{p}$, then $\mathbf{b}_{km(p)}=\mathbf{0}$. Applying $T^{-km(p)}$ gives $\mathbf{b}_0=\mathbf{0}$, contradiction. $\square$

We have:

$T^{m(p)}\mathbf{b}_0=\bar{a}_{m(p)+1}\mathbf{b}_0$, so $$T^{m(p)(p-1)}\mathbf{b}_0=(\bar{a}_{m(p)+1})^{p-1}\mathbf{b}_0=\mathbf{b}_0$$ by Fermat's little theorem, and hence $T(p)\leq m(p)(p-1)$.

For (ii):

If $T(p)=m(p)(p-1)$, then $(\bar{a}_{m(p)+1})^j$ for $j=1,2,\dots,p-1$ are all distinct, i.e., $\mu=\bar{a}_{m(p)+1}$ is a generator of $\mathbb{F}_p^\times$. We have $\{\mu,\mu^2,\dots,\mu^{p-1}\}=\{1,2,\dots,p-1\}$ and so applying Wilson's theorem gives $\prod_{k=1}^{p-1}\mu^k=(p-1)!=-1$.

Hence

\begin{align}\prod_{\substack{1\leq j\leq T(p)-1\\m(p)\nmid j}}\bar{a}_j &=\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}\bar{a}_{km(p)+j}\\ &=\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}(\mu^k\bar{a}_j)\\ &=\left(\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}\mu^k\right)\left(\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}\bar{a}_j\right)\\ &=\left[\prod_{j=1}^{m(p)-1}\left(\prod_{k=1}^{p-1}\mu^k\right)\right]\cancelto{1}{\color{red}{\left(\prod_{j=1}^{m(p)-1}\bar{a}_j\right)^{p-1}}}\\ &=(-1)^{m(p)-1} \end{align}

as claimed.