28
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ For $k$ a prime power, it follows from the proposition I cite in my answer to the question you link to, using the same reasoning as for $2$ and $5$. (The case of non prime power $k$ is easy to deduce.) I can expand on this, but you probably won't consider it a "simple combinatorial identity". But fundamentally, it's the same concept as showing that $k|(c^n-1)$ implies $k^d|(c^{k^{d-1}n}-1)$. $\endgroup$ – Gro-Tsen Jul 20 '14 at 22:46
17
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Can we officially call this "Oleg Lemma"? Or "D'Aurizio Lifting Theorem"? ;) :D $\endgroup$ – VividD Jul 21 '14 at 0:45
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @JackD'Aurizio: It was, but it didn't take very long (fortunately the proofs are fairly algebraic and thus easy to explain). And Lemmas 1 and 2 are widely useful, so I have something to cite now. :) $\endgroup$ – darij grinberg Sep 19 '15 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.