An analogue of Hensel's lifting for Fibonacci numbers

Let $F_0, F_1, F_2, \ldots$ be the Fibonacci numbers, defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n\geq 2$.

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ where $k \in \mathbb{N}$ and $n \in \mathbb{N}$. This can be regarded as an analogue of Hensel's lifting lemma.

I would be glad to give a proof (following the share your knowledge, Q&A-style), based on a simple combinatorial identity, and see if others come out with more elegant ones.

Solution 1:

Step 1. Since, by the Binet formula, $$ F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\bar{\sigma}^n\right), $$ where $\sigma+\bar{\sigma}=1$ and $\sigma\bar{\sigma}=-1$, we have: $$ F_m \mid F_{mn}, $$ since in $\mathbb{Z}[x,y]$ the polynomial $x^m-y^m$ divides the polynomial $x^{mn}-y^{mn}$.

Step 2. We can prove our statement by assuming without loss of generality that $k$ is a prime power. The Chinese theorem in conjunction with Step 1 grants that if the statement holds when $k$ is a prime power, then it holds for every integer.

Step 3. The Pisano period for the Fibonacci and Lucas sequences $\!\!\pmod{2}$ is $3$. In particular, $F_n$ (as well as $L_n$) is even iff $n$ is a multiple of $3$. Moreover, $$ F_{2n} = F_n \cdot L_n.$$

Step 4. By assuming that $2^h\mid F_n$ we have $n=3m$ in virtue of Step 3, and: $$ F_{2^{(d-1)h}n} = F_{2^{(d-1)h}3m} = F_{2^{(d-1)h-1}3m}L_{2^{(d-1)h-1}3m} = F_{3m}\cdot\prod_{j=0}^{(d-1)h-1}L_{3\cdot 2^j m}, $$ so: $$ \nu_2(F_{2^{(d-1)h}n})\geq \nu_2(F_{n}) + (d-1)h \geq dh,$$ since every term in the product is even. So we just proved the statement in case that $k$ is a power of $2$.

Step 5. We assume now that $k$ is odd. Since $\frac{x^l-y^l}{x-y}=\sum_{j=0}^{l-1} x^j y^{l-1-j}$, we have: $$\frac{F_{kn}}{F_n}=\sum_{j=0}^{k-1} \sigma^{jn}\bar{\sigma}^{(k-1-j)n}=(-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn} L_{(k-1-2j)n},$$ where $L_a = \sigma^a + \bar{\sigma}^a$. If now we use the identity: $$ L_{2a} = \sigma^{2a}+\bar{\sigma}^{2a} = 5 F_a^2 + 2(-1)^a$$ we get: $$\frac{F_{kn}}{F_n}= (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn}\left(5 F_{\left(\frac{k-1}{2}-j\right)n}^2+2(-1)^{\left(\frac{k-1}{2}-j\right)n}\right).$$ Since $F_n$ divides $F_{mn}$ and $k$ divides $F_{n}$, the last sum $\pmod{k}$ is just: $$ \frac{F_{kn}}{F_n}\equiv (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}}2(-1)^{\frac{k-1}{2}n}\equiv k (-1)^{\frac{k-1}{2}n}\equiv 0\pmod{k}.$$ Hence we have that $k\mid F_n$ implies $(k F_n)\mid F_{kn}$, and our claim follows by induction.

Solution 2:

Here is a different proof, using neither the notion of a prime nor that of an algebraic integer (which Jack used tacitly in Step 1 of his proof, I believe). Instead it uses the algebra of $2\times2$ matrices (which, arguably, emulates that of algebraic integers in $\mathbb{Z}\left[ \sqrt{-5}\right] $).

We first recall how the usual Hensel lifting lemma is proven:

Lemma 1. Let $A$ be a commutative ring with unity. Let $a$ and $b$ be two elements of $A$. Let $p$ be a nonnegative integer. Let $k\in\mathbb{N}$ and $\ell \in\mathbb{N}$ be such that $k>0$. Assume that $a\equiv b\operatorname{mod} p^{k}A$. Then, $a^{p^{\ell}}\equiv b^{p^{\ell}}\operatorname{mod}p^{k+\ell}A$.

(Here and in the following, $\mathbb{N}$ means the set $\left\{ 0,1,2,\ldots\right\} $.)

Notice that we do not require $p$ to be a prime; we merely call it $p$ because it fills the role that is usually reserved for primes in such results.

Proof of Lemma 1. The following proof is mostly copypasted from my witt#3 note (where Lemma 1 appears as Lemma 3):

We will show Lemma 1 by induction over $\ell$. For $\ell=0$, the assertion of Lemma 1 is trivial. Now, for the induction step, we assume that $a^{p^{\ell} }\equiv b^{p^{\ell}}\operatorname{mod}p^{k+\ell}A$ for some $\ell\in \mathbb{N}$, and we want to show that $a^{p^{\ell+1}}\equiv b^{p^{\ell+1} }\operatorname{mod}p^{k+\ell+1}A$.

We have $a^{p^{\ell}}\equiv b^{p^{\ell}}\operatorname{mod}p^{k+\ell}A$, thus $a^{p^{\ell}}-b^{p^{\ell}}\in p^{k+\ell}A$.

On the other hand, $a\equiv b\operatorname{mod}p^{k}A$, thus $a-b\in p^{k}A\subseteq pA$ (since $k>0$) and therefore $a\equiv b\operatorname{mod} pA$. Hence,

$\sum\limits_{i=0}^{p-1}\left( \underbrace{a^{p^{\ell}}}_{\substack{\equiv b^{p^{\ell}}\\\text{(since }a\equiv b\operatorname{mod}pA\text{)}}}\right) ^{i}\left( b^{p^{\ell}}\right) ^{p-1-i}\equiv\sum\limits_{i=0} ^{p-1}\underbrace{\left( b^{p^{\ell}}\right) ^{i}\left( b^{p^{\ell} }\right) ^{p-1-i}}_{=\left( b^{p^{\ell}}\right) ^{p-1}}$

$=\sum\limits_{i=0}^{p-1}\left( b^{p^{\ell}}\right) ^{p-1}=p\left( b^{p^{\ell}}\right) ^{p-1}\equiv0\operatorname{mod}pA$,

so that $\sum\limits_{i=0}^{p-1}\left( a^{p^{\ell}}\right) ^{i}\left( b^{p^{\ell}}\right) ^{p-1-i}\in pA$. Hence,

$a^{p^{\ell+1}}-b^{p^{\ell+1}}=\left( a^{p^{\ell}}\right) ^{p}-\left( b^{p^{\ell}}\right) ^{p}$

$=\underbrace{\left( a^{p^{\ell}}-b^{p^{\ell}}\right) }_{\in p^{k+\ell} A}\cdot\underbrace{\sum\limits_{i=0}^{p-1}\left( a^{p^{\ell}}\right) ^{i}\left( b^{p^{\ell}}\right) ^{p-1-i}}_{\in pA}\in\left( p^{k+\ell }A\right) \cdot\left( pA\right) =p^{k+\ell+1}A$,

so that $a^{p^{\ell+1}}\equiv b^{p^{\ell+1}}\operatorname{mod}p^{k+\ell+1}A$, and the induction step is complete. Thus, Lemma 1 is proven.

(If you are wondering why your favorite version of Lemma 1 is only the $k=1$ case of my Lemma 1, don't worry -- you are not missing much. The general case follows easily from the $k=1$ case.)

Now, let $\left( F_{0},F_{1},F_{2},\ldots\right) $ be the Fibonacci sequence, defined by $F_{0}=0$, $F_{1}=1$ and $F_{n}=F_{n-1}+F_{n-2}$ for every $n\geq2$. Let $X$ be the $2\times2$-matrix $\left( \begin{array} [c]{cc} 0 & 1\\ 1 & 1 \end{array} \right) \in\mathbb{Z}^{2\times2}$. A fundamental property of the Fibonacci numbers is the following fact:

Lemma 2. We have $X^{m}=F_{m-1}I_{2}+F_{m}X$ for every positive integer $m$.

(Here, $I_{2}$ denotes the $2\times2$ identity matrix.)

Proof of Lemma 2. We will prove Lemma 2 by induction over $m$.

Induction base: We have $\underbrace{F_{1-1}}_{=F_{0}=0}I_{2} +\underbrace{F_{1}}_{=1}X=0I_{2}+1X=X=X^{1}$, so that $X^{1}=F_{1-1} I_{2}+F_{1}X$. In other words, Lemma 2 holds for $m=1$. This completes the induction base.

Induction step: Let $M$ be a positive integer. Assume that Lemma 2 holds for $m=M$. We need to prove that Lemma 2 holds for $m=M+1$.

We have $X^{M}=F_{M-1}I_{2}+F_{M}X$ (since Lemma 2 holds for $X=M$). It is straightforward to check that $X^{2}=X+I_{2}$. The recursive definition of the Fibonacci number $F_{M+1}$ shows that $F_{M+1}=F_{M-1}+F_{M}$. Now,

$X^{M+1}=X\underbrace{X^{M}}_{=F_{M-1}I_{2}+F_{M}X}=X\left( F_{M-1} I_{2}+F_{M}X\right) =F_{M-1}X+F_{M}\underbrace{X^{2}}_{=X+I_{2}}$

$=F_{M-1}X+F_{M}\left( X+I_{2}\right) =F_{M-1}X+F_{M}X+F_{M}I_{2}$

$=\underbrace{\left( F_{M-1}+F_{M}\right) }_{=F_{M+1}}X+\underbrace{F_{M} }_{=F_{M+1-1}}I_{2}=F_{M+1}X+F_{M+1-1}I_{2}$

$=F_{M+1-1}I_{2}+F_{M+1}X$.

In other words, Lemma 2 holds for $m=M+1$. This completes the induction step, and thus Lemma 2 is proven by induction.

As a simple application of Lemma 2, let us prove Jack's Claim 1 and a bit more:

Proposition 3. Let $m\in\mathbb{N}$ and $n\in\mathbb{N}$. Then, $F_{m}\mid F_{mn}$. Also, if $m$ and $n$ are positive, we have $F_{mn-1}\equiv\left( F_{m-1}\right) ^{n}\operatorname{mod} F_{m}$.

While Proposition 3 will not be used in the following, I believe it is a worthwhile demonstration of how useful Lemma 2 can be even without Lemma 1.

Proof of Proposition 3. If $m=0$, then $F_{mn}=F_{0n}=F_{0}=0$, whence $F_{m}\mid F_{mn}$ in this case. Hence, we WLOG assume that we don't have $m=0$. Thus, $m$ is a positive integer.

If $n=0$, then $F_{mn}=F_{m0}=F_{0}=0$, whence $F_{m}\mid F_{mn}$ in this case. Hence, we WLOG assume that we don't have $n=0$. Thus, $n$ is a positive integer.

The matrix ring $\mathbb{Z}^{2\times2}$ is not commutative. However, its subring $\mathbb{Z}\left[ X\right] $ generated by the matrix $X$ is commutative (because its elements are polynomials in $X$, and clearly any two such polynomials commute). Let $A$ be this commutative subring $\mathbb{Z} \left[ X\right] $. Thus, clearly, $X\in A$ and $I_{2}\in A$, and any polynomial in $X$ (with integer coefficients) lies in $A$.

Lemma 2 shows that $X^{m}=F_{m-1}I_{2}+F_{m}X$, so that $X^{m}-F_{m-1} I_{2}=F_{m}X\in F_{m}A$ (since $X\in A$). In other words, $X^{m}\equiv F_{m-1}I_{2}\operatorname{mod}F_{m}A$. Taking this congruence to the $n$-th power, we obtain $\left( X^{m}\right) ^{n}\equiv\left( F_{m-1}I_{2}\right) ^{n}\operatorname{mod}F_{m}A$. Thus,

$X^{mn}=\left( X^{m}\right) ^{n}\equiv\left( F_{m-1}I_{2}\right) ^{n}=\left( F_{m-1}\right) ^{n}I_{2}\operatorname{mod}F_{m}A$.

But applying Lemma 2 to $mn$ instead of $m$, we find that $X^{mn} =F_{mn-1}I_{2}+F_{mn}X$. Thus,

$F_{mn-1}I_{2}+F_{mn}X=X^{mn}\equiv\left( F_{m-1}\right) ^{n}I_{2} \operatorname{mod}F_{m}A$,

so that $\left( F_{mn-1}I_{2}+F_{mn}X\right) -\left( F_{m-1}\right) ^{n}I_{2}\in F_{m}\underbrace{A}_{\subseteq\mathbb{Z}^{2\times2}}\subseteq F_{m}\mathbb{Z}^{2\times2}$. Since

$\left( F_{mn-1}I_{2}+F_{mn}X\right) -\left( F_{m-1}\right) ^{n} I_{2}=F_{mn-1}I_{2}-\left( F_{m-1}\right) ^{n}I_{2}+F_{mn}X$

$=\left( F_{mn-1}-\left( F_{m-1}\right) ^{n}\right) \underbrace{I_{2} }_{=\left( \begin{array} [c]{cc} 1 & 0\\ 0 & 1 \end{array} \right) }+F_{mn}\underbrace{X}_{=\left( \begin{array} [c]{cc} 0 & 1\\ 1 & 1 \end{array} \right) }$

$=\left( F_{mn-1}-\left( F_{m-1}\right) ^{n}\right) \left( \begin{array} [c]{cc} 1 & 0\\ 0 & 1 \end{array} \right) +F_{mn}\left( \begin{array} [c]{cc} 0 & 1\\ 1 & 1 \end{array} \right) $

$=\left( \begin{array} [c]{cc} F_{mn-1}-\left( F_{m-1}\right) ^{n} & F_{mn}\\ F_{mn} & F_{mn-1}-\left( F_{m-1}\right) ^{n}+F_{mn} \end{array} \right) $,

this rewrites as $\left( \begin{array} [c]{cc} F_{mn-1}-\left( F_{m-1}\right) ^{n} & F_{mn}\\ F_{mn} & F_{mn-1}-\left( F_{m-1}\right) ^{n}+F_{mn} \end{array} \right) \in F_{m}\mathbb{Z}^{2\times2}$. In other words, all entries of the matrix $\left( \begin{array} [c]{cc} F_{mn-1}-\left( F_{m-1}\right) ^{n} & F_{mn}\\ F_{mn} & F_{mn-1}-\left( F_{m-1}\right) ^{n}+F_{mn} \end{array} \right) $ are divisible by $F_{m}$. In other words, the integers $F_{mn-1}-\left( F_{m-1}\right) ^{n}$, $F_{mn}$, $F_{mn}$ and $F_{mn-1} -\left( F_{m-1}\right) ^{n}+F_{mn}$ are divisible by $F_{m}$.

Now, $F_{m}\mid F_{mn}$ (since $F_{mn}$ is divisible by $F_{m}$) and $F_{mn-1}\equiv\left( F_{m-1}\right) ^{n}\operatorname{mod}F_{m}$ (since $F_{mn-1}-\left( F_{m-1}\right) ^{n}$ is divisible by $F_{m}$). Proposition 3 is proven.

Now, here is Jack's main result:

Theorem 4. Let $k\in\mathbb{N}$ and $n\in\mathbb{N}$ be such that $k\mid F_{n}$. Let $d$ be a positive integer. Then, $k^{d}\mid F_{k^{d-1}n}$.

Proof of Theorem 4. First, let us assume that $d=1$. Thus, $k^{d} =k^{1}=k\mid F_{n}$. Also, $k^{d-1}n=\underbrace{k^{1-1}}_{=k^{0}=1}n=n$. Hence, $k^{d}\mid F_{n}$ rewrites as $k^{d}\mid F_{k^{d-1}n}$. Thus, Theorem 4 holds under the assumption that $d=1$.

Now, let us forget that we assumed that $d=1$. Having proven Theorem 4 in the case when $d = 1$, we can now WLOG assume that $d\neq1$. Assume this. Hence, $d\geq2$, and thus $0^{d-1}=0$. Consequently, $F_{0^{d-1} n}=F_{0n}=F_{0}=0$ is divisible by every integer. In particular, $0^{d}\mid F_{0^{d-1}n}$. Hence, Theorem 4 holds if $k=0$. We thus WLOG assume that $k\neq0$. Thus, $k$ is a positive integer.

Also, $k^{d}\mid F_{k^{d-1}0}$ (since $F_{k^{d-1}0}=F_{0}=0$). Hence, Theorem 4 holds if $n=0$. We thus WLOG assume that $n\neq0$. Thus, $n$ is a positive integer.

The matrix ring $\mathbb{Z}^{2\times2}$ is not commutative. However, its subring $\mathbb{Z}\left[ X\right] $ generated by the matrix $X$ is commutative (because its elements are polynomials in $X$, and clearly any two such polynomials commute). Let $A$ be this commutative subring $\mathbb{Z} \left[ X\right] $. Thus, clearly, $X\in A$ and $I_{2}\in A$, and any polynomial in $X$ (with integer coefficients) lies in $A$. In particular, $\mathbb{Z} X \subseteq A$.

We have $F_{n}\in k\mathbb{Z}$ (since $k\mid F_{n}$). Lemma 2 (applied to $m=n$) shows that $X^{n}=F_{n-1}I_{2}+F_{n}X$, so that $X^{n}-F_{n-1} I_{2}=\underbrace{F_{n}}_{\in k\mathbb{Z}}X\in k\underbrace{\mathbb{Z} X}_{\subseteq A}\subseteq kA=k^{1}A$. In other words, $X^{n}\equiv F_{n-1}I_{2}\operatorname{mod}k^{1}A$. Thus, Lemma 1 (applied to $X^{n}$, $F_{n-1}I_{2}$, $k$, $1$ and $d-1$ instead of $a$, $b$, $p$, $k$ and $\ell$) shows that $\left( X^{n}\right) ^{k^{d-1}}\equiv\left( F_{n-1}I_{2}\right) ^{k^{d-1}}\operatorname{mod}k^{1+\left( d-1\right) }A$. Since

$\left( X^{n}\right) ^{k^{d-1}}=X^{nk^{d-1}}=X^{k^{d-1}n}=F_{k^{d-1} n-1}I_{2}+F_{k^{d-1}n}X$ (by Lemma 2, applied to $m=k^{d-1}n$)

and $1+\left( d-1\right) =d$, this rewrites as follows:

$F_{k^{d-1}n-1}I_{2}+F_{k^{d-1}n}X\equiv\left( F_{n-1}I_{2}\right) ^{k^{d-1}}\operatorname{mod}k^{d}A$.

Thus, $F_{k^{d-1}n-1}I_{2}+F_{k^{d-1}n}X-\left( F_{n-1}I_{2}\right) ^{k^{d-1}}\in k^{d}\underbrace{A}_{\subseteq\mathbb{Z}^{2\times2}}\subseteq k^{d}\mathbb{Z}^{2\times2}$.

Since

$F_{k^{d-1}n-1}I_{2}+F_{k^{d-1}n}X-\underbrace{\left( F_{n-1}I_{2}\right) ^{k^{d-1}}}_{=\left( F_{n-1}\right) ^{k^{d-1}}I_{2}}$

$=F_{k^{d-1}n-1}I_{2}+F_{k^{d-1}n}X-\left( F_{n-1}\right) ^{k^{d-1}}I_{2}$

$=F_{k^{d-1}n-1}I_{2}-\left( F_{n-1}\right) ^{k^{d-1}}I_{2}+F_{k^{d-1}n}X$

$=\left( F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}}\right) \underbrace{I_{2}}_{=\left( \begin{array} [c]{cc} 1 & 0\\ 0 & 1 \end{array} \right) }+F_{k^{d-1}n}\underbrace{X}_{=\left( \begin{array} [c]{cc} 0 & 1\\ 1 & 1 \end{array} \right) }$

$=\left( F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}}\right) \left( \begin{array} [c]{cc} 1 & 0\\ 0 & 1 \end{array} \right) +F_{k^{d-1}n}\left( \begin{array} [c]{cc} 0 & 1\\ 1 & 1 \end{array} \right) $

$=\left( \begin{array} [c]{cc} F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}} & F_{k^{d-1}n}\\ F_{k^{d-1}n} & F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}}+F_{k^{d-1}n} \end{array} \right) $,

this rewrites as

$\left( \begin{array} [c]{cc} F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}} & F_{k^{d-1}n}\\ F_{k^{d-1}n} & F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}}+F_{k^{d-1}n} \end{array} \right) \in k^{d}\mathbb{Z}^{2\times2}$.

Thus, the integers $F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}}$, $F_{k^{d-1}n}$, $F_{k^{d-1}n}$ and $F_{k^{d-1}n-1}-\left( F_{n-1}\right) ^{k^{d-1}}+F_{k^{d-1}n}$ are all divisible by $k^{d}$. In particular, $F_{k^{d-1}n}$ is divisible by $k^{d}$. This proves Theorem 4.