Exact Divisibility by Powers of the Fibonacci and Lucas Numbers

Prapanpong Pongsriiam Department of Mathematics, Faculty of Science Silpakorn University Ratchamankanai Rd, Nakhon Pathom Thailand, 73000

                     prapanpong@gmail.com

Abstract

We give new results on exact divisibility by powers of the Fibonacci and Lucas numbers. For example, we prove that if F_{n}^{k} exactly divides m and n is not congruent to 3 modulo 6, then F_{n}^{k+1} exactly divides F_{nm}. We also provide some examples and open questions.

1 Introduction

Let (F_{n})_{n≥0} be the Fibonacci sequence defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2, and let (L_{n})_{n≥0} be the Lucas sequence given by L_{0} = 2, L_{1} = 1 with the same recursive pattern as the Fibonacci sequence.

The divisibility property of Fibonacci and Lucas numbers has always been a popular area of research. In particular, the divisibility by powers of the Fibonacci numbers became a popular topic when Matijasevic̆ [10, 11, 12] proved in 1970 that

F_{n}^{2} | F_{nm} if and only if F_{n} | m  (1)

which led to the solution to Hilbert’s 10th Problem. Since (1) appeared, there have been several results [2, 5, 9, 13, 14, 17] on divisibility by powers of the Fibonacci numbers in the literature. However, exact divisibility by powers of the Fibonacci and Lucas numbers seems to be new. (Recall that for integers a, d ≥ 2 and k ≥ 1, we say that d^{k} exactly divides a and write d^{k} ∥ a if d^{k} | a and d^{k+1} ∤ a). Now let us consider the following divisibility:

F_{n}^{k+1} | F_{nF_{n}^{k}}.  (2)

Marques [9, p. 241] mentioned that to the best of his knowledge, (2) was first proved by Benjamin and Rouse [2], using a combinatorial approach, and a second proof of (2) is due to Seibert and Trojovsky [16] by using mathematical induction together with an identity for \frac{F_{nm}}{F_{m}}. Marques [9] himself also gave another proof of (2) by applying Lengyel’s theorem [8] on the p-adic order of Fibonacci and Lucas numbers. However, there was an older result which implied (2); it was proved in 1977 by Hoggatt and Bicknell-Johnson [5], as follows:

Theorem 1. [2, 5] Let k, m, and n be positive integers. If F_{n}^{k} | m, then F_{n}^{k+1} | F_{nm}.

Note that, from Theorem 1, we can easily obtain (2) by substituting m = F_{n}^{k}, and obtain one direction of (1) by substituting k = 1. Now it is natural to ask if k + 1 in Theorem 1 is the largest exponent of F_{n} such that F_{n}^{k+1} divides F_{nm}. Our purpose is to give another proof of Theorem 1, and generalize the result to include the divisibility and exact divisibility by powers of the Fibonacci and Lucas numbers. Our results are as follows:

Theorem 2. Let k, m, n be positive integers and n ≥ 3. Then

(i) if F_{n}^{k} ∥ m and n ≢ 3 (mod 6), then F_{n}^{k+1} ∥ F_{nm};

(ii) if F_{n}^{k} ∥ m, n ≡ 3 (mod 6), and \frac{F_{n}^{k+1}}{2} ∤ m, then F_{n}^{k+1} ∥ F_{nm};

(iii) if F_{n}^{k} ∥ m, n ≡ 3 (mod 6), and \frac{F_{n}^{k+1}}{2} | m, then F_{n}^{k+2} ∥ F_{nm}.

Theorem 3. Let k, m, n be positive integers and m is odd. Then

(i) if L_{n}^{k} | m, then L_{n}^{k+1} | L_{nm};

(ii) if n ≥ 2 and L_{n}^{k} ∥ m, then L_{n}^{k+1} ∥ L_{nm}.

Theorem 4. Let k, m, and n be positive integers, m is even, and n ≥ 2. Then the following statements hold.

(i) If L_{n}^{k} | m, then L_{n}^{k+1} | F_{nm};

(ii) If L_{n}^{k} ∥ m and n ≢ 0 (mod 3), then L_{n}^{k+1} ∥ F_{nm};

(iii) If L_{n}^{k} ∥ m, n ≡ 0 (mod 6), and \frac{L_{n}^{k+1}}{2} ∤ m, then L_{n}^{k+1} ∥ F_{nm};

(iv) If L_{n}^{k} ∥ m, n ≡ 0 (mod 6), and \frac{L_{n}^{k+1}}{2} | m, then L_{n}^{k+2} | F_{nm};

(v) If L_{n}^{k} ∥ m, n ≡ 3 (mod 6), and \frac{L_{n}^{k+1}}{4} ∤ m, then L_{n}^{k+1} ∥ F_{nm};

(vi) If L_{n}^{k} ∥ m, n ≡ 3 (mod 6), and \frac{L_{n}^{k+1}}{4} | m, then L_{n}^{k+2} ∥ 4F_{nm}.

To prove the above theorems, we will need a number of lemmas given in the next section.

2 Preliminaries and lemmas

In this section, we will give some auxiliary results that will be used in this article. Let m, n, and r be positive integers. Then the following statements hold.

gcd(F_{m}, F_{n}) = F_{gcd(m,n)}.  (3)

F_{nm} = ∑_{j=1}^{m} \binom{m}{j}F_{n}^{j}F_{n−1}^{m−j}F_{j}.  (4)

If m ≥ 3, then F_{m} | F_{n} if and only if m | n.  (5)
L_{n} = F_{n−1} + F_{n+1}.  (6)

gcd(L_{n}, F_{n}) = \begin{cases}1, & if 3 ∤ n; \\ 2, & if 3 | n. \end{cases}  (7)

For the reader’s convenience, let us give references for the above statements. Properties (3) and (5) can be found in [7, pp. 196–198]. Property (4) can be found in several articles such as [2, 4, 5]. Property (6) appears in [7, p. 80], and (7) can be proved by using (6), (3), and (5). We refer the reader to [1, 3, 6, 7, 15, 18] for more details and additional references.

Next we give the following results, similar to (4).

L_{nm} · 2^{m−1} = \begin{matrix}⌊ & \frac{m}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m}{m − 2j}L_{n}^{m−2j}F_{n}^{2j}5^{j}.  (8)

F_{nm} · 2^{m−1} = \begin{aligned}⌊ & \frac{m−1}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned} \binom{m}{m − 2j − 1}L_{n}^{m−(2j+1)}F_{n}^{2j+1}5^{j}.  (9)

These are probably less well known, so we will give a proof for completeness.

Proof. Recall Binet’s formula that F_{n} = \frac{α^{n}−β^{n}}{α−β} and L_{n} = α^{n} + β^{n}, where α = \frac{1+\sqrt{5}}{2} and β = \frac{1−\sqrt{5}}{2}. Then α^{n} = \frac{1}{2} (L_{n} + (α − β)F_{n}) = \frac{1}{2} (L_{n} + \sqrt{5}F_{n}), and β^{n} = \frac{1}{2} (L_{n} − (α − β)F_{n}) = \frac{1}{2} (L_{n} − \sqrt{5}F_{n}). Then

L_{nm} = α^{nm} + β^{nm} = \frac{1}{2^{m}} (L_{n} + \sqrt{5}F_{n})^{m} + \frac{1}{2^{m}} (L_{n} − \sqrt{5}F_{n})^{m}

= \frac{1}{2^{m}} ∑_{k=0}^{m} \binom{m}{m − k}L_{n}^{m−k}(\sqrt{5}F_{n})^{k} (1 + (−1)^{k}) .

When k is odd, 1 + (−1)^{k} = 0, so we replace k by 2j and obtain

L_{nm} = \frac{1}{2^{m−1}} \begin{matrix}⌊ & \frac{m}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m}{m − 2j}L_{n}^{m−2j}F_{n}^{2j}5^{j},

which gives (8). For (9), we write

\sqrt{5}F_{nm} = (α − β)F_{nm} = α^{nm} − β^{nm} = \frac{1}{2^{m}} (L_{n} + \sqrt{5}F_{n})^{m} − \frac{1}{2^{m}} (L_{n} − \sqrt{5}F_{n})^{m}

= \frac{1}{2^{m}} ∑_{k=0}^{m} \binom{m}{m − k}L_{n}^{m−k}(\sqrt{5}F_{n})^{k} (1 − (−1)^{k}) .

As in the previous case, we replace k by 2j + 1 to obtain (9).

The next lemma is about the p-adic orders of Fibonacci and Lucas numbers given by Lengyel [8]. Recall that the order of appearance of m and the period modulo m of the Fibonacci sequence, respectively, is the smallest positive integer k such that m | F_{k} and the smallest positive integer k such that F_{n+k} ≡ F_{n} (mod m) for all n ≥ 1.

Lemma 5. [8] For each m ∈ ℕ, let ν_{p}(m) be the p-adic order of m, z(m) the order of appearance of m, and s(m) the period modulo m of the Fibonacci sequence. For n ≥ 1, we have

ν_{2}(F_{n}) = \begin{cases}0, & if n ≡ 1, 2 (mod 3); \\ 1, & if n ≡ 3 (mod 6); \\ ν_{2}(n) + 2, & if n ≡ 0 (mod 6), \end{cases}

ν_{2}(L_{n}) = \begin{cases}0, & if n ≡ 1, 2 (mod 3); \\ 2, & if n ≡ 3 (mod 6); \\ 1, & if n ≡ 0 (mod 6), \end{cases}

ν_{5}(F_{n}) = ν_{5}(n), ν_{5}(L_{n}) = 0, and if p is a prime, p ≠ 2 and p ≠ 5, then

ν_{p}(F_{n}) = \begin{cases}ν_{p}(n) + ν_{p}(F_{z(p)}), & if n ≡ 0 (mod z(p)); \\ 0, & otherwise. \end{cases}

ν_{p}(L_{n}) = \begin{cases}ν_{p}(n) + ν_{p}(F_{z(p)}), & if s(p) ≠ 4z(p) and n ≡ \frac{z(p)}{2} (mod z(p)); \\ 0, & otherwise. \end{cases}

The next result given by Onphaeng and Pongsriiam [13] is an important tool for obtaining the main results of this article.

Lemma 6. [13] Let k, ℓ, m, s be positive integers and s^{k} | m. Then s^{k+ℓ} | \binom{m}{j}s^{j} for all 1 ≤ j ≤ m satisfying 2^{j−ℓ+1} > j. In particular, s^{k+1} | \binom{m}{j}s^{j} for all 1 ≤ j ≤ m, and s^{k+2} | \binom{m}{j}s^{j} for all 3 ≤ j ≤ m.

3 Proof of the main results

In this section, we will give the proof of Theorems 1, 2, 3, and 4. Another proof of Theorem 1. Assume that F_{n}^{k} | m. Then by Lemma 6, F_{n}^{k+1} | \binom{m}{j}F_{n}^{j} for all 1 ≤ j ≤ m. Therefore F_{n}^{k+1} | F_{nm} by (4). Proof of Theorem 2. Assume that F_{n}^{k} ∥ m. By Theorem 1, F_{n}^{k+1} | F_{nm}. So to show that F_{n}^{k+1} ∥ F_{nm}, it is enough to show that F_{n}^{k+2} ∤ F_{nm}. First we write

m = F_{n}^{k}c where c ≥ 1 and F_{n} ∤ c.  (10)

By Lemma 6, F_{n}^{k+2} | \binom{m}{j}F_{n}^{j} for all 3 ≤ j ≤ m. Then we obtain by (4) that

F_{nm} ≡ mF_{n}F_{n−1}^{m−1} + \frac{m(m − 1)}{2}F_{n}^{2}F_{n−1}^{m−2} (mod F_{n}^{k+2}).  (11)

Proof of (i): Case 1 of (i): n ≡ 1, 2, 4, 5 (mod 6). Then by Lemma 5, F_{n} is odd. Since F_{n}^{k} | 2 (\frac{m(m−1)}{2}) and F_{n} is odd, we obtain that F_{n}^{k} | \frac{m(m−1)}{2}. Therefore

F_{n}^{k+2} |\frac{m(m − 1)}{2}F_{n}^{2}F_{n−1}^{m−2} .  (12)

By (11) and (12), we obtain F_{nm} ≡ mF_{n}F_{n−1}^{m−1} (mod F_{n}^{k+2}). Since gcd(F_{n}, F_{n−1}) = 1 with respect to (3), we see that

F_{n}^{k+2} | F_{nm} ⇔ F_{n}^{k+2} | mF_{n}F_{n−1}^{m−1} ⇔ F_{n}^{k+1} | m.  (13)

Since F_{n}^{k} ∥ m, F_{n}^{k+1} ∤ m. So we obtain by (13) that F_{n}^{k+2} ∤ F_{nm}. Case 2 of (i): n ≡ 0 (mod 6). Then by Lemma 5 we have F_{n} ≡ 0 (mod 4). Let

d = F_{n−1} + (m − 1)\frac{F_{n}}{2} .

Since F_{n} is even,

d is an integer and (\frac{F_{n}}{2} , d) = 1  (14)

By (11) and (10), we obtain

F_{nm} ≡ mF_{n}F_{n−1}^{m−2} (F_{n−1} + \frac{m − 1}{2}F_{n}) ≡ cF_{n}^{k+1}F_{n−1}^{m−2}d (mod F_{n}^{k+2}).

Suppose, in order to get a contradiction, that F_{n}^{k+2} | F_{nm}. Then F_{n}^{k+2} | cF_{n}^{k+1}F_{n−1}^{m−2}d which implies that F_{n} | cd. By F_{n} ≡ 0 (mod 4), F_{n} | cd, and (14) we obtain that d is odd, c is even, and \frac{F_{n}}{2} | \frac{c}{2}d. This and (14) imply that F_{n} | c, which contradicts (10). Hence F_{n}^{k+2} ∤ F_{nm}.

Proof of (ii):

Assume that n ≡ 3 (mod 6) and \frac{F_{n}^{k+1}}{2} ∤ m. Then by Lemma 5 and (10), respectively, we obtain ν_{2}(F_{n}) = 1 and \frac{F_{n}}{2} ∤ c. We can follow the argument in Case 2 of (i) to see that F_{nm} ≡ cF_{n}^{k+1}F_{n−1}^{m−2}d (mod F_{n}^{k+2}), and that F_{n}^{k+2} | F_{nm} if and only if F_{n} | cd. But if F_{n} | cd, then \frac{F_{n}}{2} | cd which implies by (14) that \frac{F_{n}}{2} | c, a contradiction. So F_{n} ∤ cd and therefore F_{n}^{k+2} ∤ F_{nm}. Hence F_{n}^{k+1} ∥ F_{nm}.

Proof of (iii):

Assume that n ≡ 3 (mod 6) and \frac{F_{n}^{k+1}}{2} | m. In this case, we will show that F_{n}^{k+2} ∥ F_{nm}. We can still follow the argument in Case 2 of (i) and the proof of (ii) to obtain F_{nm} ≡ cF_{n}^{k+1}F_{n−1}^{m−2}d (mod F_{n}^{k+2}) and F_{n}^{k+2} | F_{nm} if and only if F_{n} | cd. Since n ≡ 3 (mod 6), F_{n} is even and \frac{F_{n}}{2} is odd. Therefore F_{n−1} and m − 1 are odd and d is even. Since m = F_{n}^{k}c and \frac{F_{n}^{k+1}}{2} | m, we obtain F_{n} | 2c. Since 2c | cd, we obtain F_{n} | cd and therefore F_{n}^{k+2} | F_{nm}. It remains to show that F_{n}^{k+3} ∤ F_{nm}. Suppose for a contradiction that F_{n}^{k+3} | F_{nm}. So for every prime p dividing F_{n}, ν_{p}(F_{n}^{k+3}) ≤ ν_{p}(F_{nm}). By Lemma 5, we obtain the following inequalities:

2 + ν_{2}(F_{n}^{k+1}) = ν_{2}(F_{n}^{k+3}) ≤ ν_{2}(F_{nm}) = ν_{2}(nm) + 2 = ν_{2}(m) + 2,
2ν_{5}(n) + ν_{5}(F_{n}^{k+1}) = ν_{5}(F_{n}^{k+3}) ≤ ν_{5}(F_{nm}) = ν_{5}(n) + ν_{5}(m),

and for every prime p ∉ {2, 5} and p | F_{n}, we have

2ν_{p}(F_{n}) + ν_{p}(F_{n}^{k+1}) = ν_{p}(F_{n}^{k+3}) ≤ ν_{p}(F_{nm})
= ν_{p}(nm) + ν_{p}(F_{z(p)}) = ν_{p}(m) + ν_{p}(n) + ν_{p}(F_{z(p)})
= ν_{p}(m) + ν_{p}(F_{n}).

From the above inequalities, we obtain that ν_{p}(m) ≥ ν_{p}(F_{n}^{k+1}) for every prime p dividing F_{n}. Therefore F_{n}^{k+1} | m which contradicts F_{n}^{k} ∥ m. This gives (iii). Hence the proof is complete.

Proof of Theorem 3. Proof of (i):

Assume that L_{n}^{k} | m. Since m is odd and L_{n} | m, L_{n} is odd too. By Lemma 6, L_{n}^{k+1} | \binom{m}{j}L_{n}^{j} for each 1 ≤ j ≤ m. Then L_{n}^{k+1} | \binom{m}{m−2j}L_{n}^{m−2j} for all 0 ≤ j ≤ \frac{m−1}{2}. Then by (8), we see that L_{n}^{k+1} | L_{nm} · 2^{m−1}. Hence L_{n}^{k+1} | L_{nm}. This proves (i).

Proof of (ii):

Next assume that n ≥ 2 and L_{n}^{k} ∥ m. Then m ≥ 3 and by Lemma 6, L_{n}^{k+2} | \binom{m}{j}L_{n}^{j} for all 3 ≤ j ≤ m. This implies that L_{n}^{k+2} | \binom{m}{m−2j}L_{n}^{m−2j} for all 0 ≤ j ≤ \frac{m−3}{2}. Then by (8), we see that

L_{nm} · 2^{m−1} ≡ mL_{n}F_{n}^{m−1}5^{\frac{m−1}{2}} (mod L_{n}^{k+2})  (15)

Since L_{n} is odd, we obtain

L_{n}^{k+2} | L_{nm} ⇔ L_{n}^{k+2} | L_{nm} · 2^{m−1}
⇔ L_{n}^{k+1} | mF_{n}^{m−1}5^{\frac{m−1}{2}} , by (15)
⇔ L_{n}^{k+1} | m, by (7) and Lemma 5.

Now L_{n}^{k} ∥ m, so L_{n}^{k+1} ∤ m and thus L_{n}^{k+2} ∤ L_{nm}. Hence L_{n}^{k+1} ∥ L_{nm} as desired. Proof of Theorem 4. Assume that L_{n}^{k} | m. Since n ≥ 2, we have m ≥ 4. Then by Lemma 6, L_{n}^{k+1} | \binom{m}{j}L_{n}^{j} for every 1 ≤ j ≤ m. Therefore L_{n}^{k+1} | \binom{m}{m−2j−1}L_{n}^{m−(2j+1)} for every 0 ≤ j ≤ \frac{m−2}{2}. Then by (9), we obtain F_{nm} · 2^{m−1} ≡ 0 (mod L_{n}^{k+1}). From this point on, p-adic orders will be used and we sometimes apply Lemma 5 without referring to it explicitly.

Proof of (i): Case 1 of (i): n ≡ 1, 2 (mod 3). Then gcd(2, L_{n}) = 1. Since L_{n}^{k+1} | F_{nm} · 2^{m−1}, L_{n}^{k+1} | F_{nm}. Case 2 of (i): n ≡ 0 (mod 6). Then ν_{2}(L_{n}) = 1. Since L_{n}^{k} | m, ν_{2}(m) ≥ ν_{2}(L_{n}^{k}) = k. Since n ≡ 0 (mod 6), nm ≡ 0 (mod 6) and therefore

ν_{2}(F_{nm}) = ν_{2}(nm) + 2 = ν_{2}(n) + ν_{2}(m) + 2 ≥ k + 2.

Since L_{n}^{k+1} | F_{nm} · 2^{m−1} and ν_{2}(L_{n}) = 1, we obtain (\frac{L_{n}}{2} )^{k+1} | \frac{F_{nm}}{2^{k+1}} · 2^{m−1}, which implies (\frac{L_{n}}{2} )^{k+1} | \frac{F_{nm}}{2^{k+1}} . Therefore L_{n}^{k+1} | F_{nm}. Case 3 of (i): n ≡ 3 (mod 6). Then ν_{2}(L_{n}) = 2 and ν_{2}(F_{n}) = 1. Since L_{n}^{k} | m, ν_{2}(m) ≥ ν_{2}(L_{n}^{k}) = 2k. Therefore nm ≡ 0 (mod 6) and ν_{2}(F_{nm}) = ν_{2}(nm) + 2 = ν_{2}(n) + ν_{2}(m) + 2 ≥ 2k + 2. Since L_{n}^{k+1} | F_{nm} · 2^{m−1}, ν_{2}(L_{n}) = 2, and ν_{2}(F_{nm}) ≥ 2k + 2, we obtain

\frac{L_{n}^{k+1}}{(2^{2})^{k+1}} | \frac{F_{nm}}{2^{2k+2}} · 2^{m−1},

which implies that \frac{L_{n}^{k+1}}{(2^{2})^{k+1}} | \frac{F_{nm}}{2^{2k+2}} . Therefore L_{n}^{k+1} | F_{nm}.

In any case, we obtain that L_{n}^{k+1} | F_{nm}. This proves (i).

Proof of (ii):

Next assume that L_{n}^{k} ∥ m. Recall that m ≥ 4. By Lemma 6, L_{n}^{k+2} | \binom{m}{j}L_{n}^{j} for every 3 ≤ j ≤ m. Therefore L_{n}^{k+2} | \binom{m}{m−2j−1}L_{n}^{m−(2j+1)} for every 0 ≤ j ≤ \frac{m−4}{2}. Then by (9),

F_{nm} · 2^{m−1} ≡ mL_{n}F_{n}^{m−1}5^{\frac{m−2}{2}} (mod L_{n}^{k+2}).  (16)

Assume that n ≡ 1, 2 (mod 3). Then by Lemma 5, (16), and (7), we obtain that

L_{n}^{k+2} | F_{nm} ⇔ L_{n}^{k+2} | F_{nm} · 2^{m−1} ⇔ L_{n}^{k+2} | mL_{n}F_{n}^{m−1}5^{\frac{m−2}{2}} ⇔ L_{n}^{k+1} | m.

But L_{n}^{k} ∥ m, so L_{n}^{k+1} ∤ m and thus L_{n}^{k+2} ∤ F_{nm}. Then L_{n}^{k+1} ∥ F_{nm}. This proves (ii).

Proof of (iii) and (iv):

Assume that L_{n}^{k} ∥ m and n ≡ 0 (mod 6). In analogy with the proof of Case 2 of (i), we see that

L_{n}^{k+2} | F_{nm} · 2^{m−1} ⇔ \frac{L_{n}^{k+2}}{2^{k+2}} | \frac{F_{nm}}{2^{k+2}} · 2^{m−1} ⇔ \frac{L_{n}^{k+2}}{2^{k+2}} | \frac{F_{nm}}{2^{k+2}} ⇔ L_{n}^{k+2} | F_{nm}.  (17)

Let m = L_{n}^{k}c where c ≥ 1 and L_{n} ∤ c. Then by (17), (16), and Lemma 5, we obtain that

L_{n}^{k+2} | F_{nm} ⇔ L_{n}^{k+2} | mL_{n}F_{n}^{m−1}5^{\frac{m−2}{2}} ⇔ L_{n} | cF_{n}^{m−1}.  (18)

Now gcd(L_{n}, F_{n}) = 2 and ν_{2}(L_{n}) = 1, so gcd (\frac{L_{n}}{2} , F_{n}) = 1, and therefore

L_{n} | cF_{n}^{m−1} ⇔ \frac{L_{n}}{2} | c\frac{F_{n}^{m−1}}{2} ⇔ \frac{L_{n}}{2} | c ⇔ \frac{L_{n}^{k+1}}{2} | m.  (19)

By (18) and (19), we see that L_{n}^{k+2} | F_{nm} ⇔ \frac{L_{n}^{k+1}}{2} | m. This proves (iii) and (iv).

Proof of (v) and (vi):

Assume that L_{n}^{k} ∥ m and n ≡ 3 (mod 6). In analogy with the proof of Case 3 of (i), we obtain that

L_{n}^{k+2} | F_{nm} · 2^{m−1} ⇔ \frac{L_{n}^{k+2}}{2^{2(k+2)}} | \frac{F_{nm}}{2^{2k+2}} · \frac{2^{m−1}}{2^{2}}

⇔ \frac{L_{n}^{k+2}}{2^{2(k+2)}} | \frac{F_{nm}}{2^{2k+2}}

⇔ L_{n}^{k+2} | 4F_{nm}.  (20)

Next, we write m = L_{n}^{k}c, use (16), and use the similar idea in the proof of (iii) and (iv) to obtain that

L_{n}^{k+2} | F_{nm} · 2^{m−1} ⇔ L_{n}^{k+2} | mL_{n}F_{n}^{m−1}5^{\frac{m−2}{2}} ⇔ L_{n} | cF_{n}^{m−1} ⇔ \frac{L_{n}}{4} | c\frac{F_{n}^{m−1}}{4}
⇔ \frac{L_{n}}{4} | c ⇔ \frac{L_{n}^{k+1}}{4} | m.  (21)

From (20) and (21), we conclude that L_{n}^{k+2} | 4F_{nm} ⇔ \frac{L_{n}^{k+1}}{4} | m. This gives (v) and to prove (vi), it suffices to show that L_{n}^{k+3} ∤ 4F_{nm}. Suppose for a contradiction that L_{n}^{k+3} | 4F_{nm}. Then for every prime p dividing L_{n}, ν_{p}(L_{n}^{k+3}) ≤ ν_{p}(4F_{nm}). Consider the following inequalities:

4 + ν_{2}(L_{n}^{k+1}) = ν_{2}(L_{n}^{k+3}) ≤ ν_{2}(4F_{nm}) = 2 + ν_{2}(nm) + 2 = 4 + ν_{2}(m),

where we use that mn ≡ 0 (mod 6), and for every prime p ∉ {2, 5} and p | L_{n}, we have

ν_{p}(L_{n}^{k+1}) + 2ν_{p}(L_{n}) = ν_{p}(L_{n}^{k+3}) ≤ ν_{p}(4F_{nm}) ≤ ν_{p}(nm) + ν_{p}(F_{z(p)})
= ν_{p}(m) + ν_{p}(n) + ν_{p}(F_{z(p)}) = ν_{p}(m) + ν_{p}(L_{n}).

From the above inequalities, we obtain that ν_{p}(m) ≥ ν_{p}(L_{n}^{k+1}) for every prime p dividing L_{n}. Therefore L_{n}^{k+1} | m which contradicts the fact that L_{n}^{k} ∥ m. Hence L_{n}^{k+3} ∤ 4F_{nm}. This proves (vi) and the proof is complete.

4 Examples

In this section, we give some examples to clarify the results in Theorems 3 and 4. Then we give some open questions at the end of this article. First we will show that the assumption that m is odd in Theorem 3 and that m is even in Theorem 4 cannot be omitted.

Example 7. Let n ≡ 0 (mod 3), k ≥ 1, and m = L_{n}^{k}. Then m is even, L_{n}^{k} | m, but ν_{2}(L_{n}^{k+1}) ≥ k + 1 > 1 = ν_{2}(L_{nm}). Therefore L_{n}^{k+1} ∤ L_{nm}. This shows that Theorem 3 does not hold if m is not odd.

Example 8. Let n ≥ 2, n ≡ 1, 2 (mod 3), k ≥ 1, and m = L_{n}^{k}. Then m is odd and L_{n}^{k} | m. As in the argument used in beginning of the proof of Theorem 4(i), we see that L_{n}^{k+1} | \binom{m}{m−2j−1}L_{n}^{m−(2j+1)} for every 0 ≤ j ≤ \frac{m−3}{2} and F_{nm} · 2^{m−1} ≡ F_{n}^{m}5^{\frac{m−1}{2}} (mod L_{n}^{k+1}). Since n ≡ 1, 2 (mod 3), we obtain by (7) that gcd(L_{n}, F_{n}) = 1. As L_{n} ≥ 3 and gcd(L_{n}, 5) = 1 with respect to Lemma 5, we obtain L_{n}^{k+1} ∤ F_{n}^{m}5^{\frac{m−1}{2}} . Hence L_{n}^{k+1} ∤ F_{nm}. This shows that Theorem 4 does not hold if m is not even.

The conclusion L_{n}^{k+2} | F_{nm} in Theorem 4(iv) may or may not be L_{n}^{k+2} ∥ F_{nm} as shown in the next example.

Example 9. Let k ≥ 1, ℓ ≥ 2k + 2, n = 6, and m = 2^{k}3^{ℓ}. Then m is even, n ≡ 0 (mod 6), L_{n} = 18, L_{n}^{k} ∥ m, and \frac{L_{n}^{k+1}}{2} | m. Then we obtain

ν_{2}(F_{nm}) = ν_{2}(nm) + 2 = k + 3 = (k + 3)ν_{2}(L_{n}) = ν_{2}(L_{n}^{k+3}),
ν_{3}(F_{nm}) = ν_{3}(nm) + ν_{3}(F_{4}) = ℓ + 2, and
ν_{3}(L_{n}^{k+3}) = ν_{3}(18^{k+3}) = 2k + 6.

From this we see that if ℓ ≥ 2k + 4, then L_{n}^{k+3} | F_{nm} and if 2k + 2 ≤ ℓ < 2k + 4, then L_{n}^{k+3} ∤ F_{nm}. This shows that the conclusion in Theorem 4(iv) may or may not be replaced by an exact divisibility.

In view of Theorems 2, 3, and 4, the reader may expect to see the result concerning the divisibility of Lucas numbers by powers of the Fibonacci numbers. But this is not possible in general. For example, let n ≥ 3, n ≡ 0 (mod 3), k ≥ 1, m = F_{n}^{k}, then ν_{2}(F_{n}^{k+1}) ≥ k + 1 ≥ 2 > ν_{2}(L_{nm}) and therefore F_{n}^{k} ∥ m but F_{n}^{k+1} ∤ L_{nm}. Even though we assume n ≢ 0 (mod 3), the desired result is still false as shown in the next example.

Example 10. Let n ≥ 3 and n ≢ 0 (mod 3). Let k, m ≥ 1 and F_{n}^{k} | m. Then by Lemma 6, F_{n}^{k+1} | \binom{m}{2j}F_{n}^{2j} for every 1 ≤ j ≤ ⌊\frac{m}{2}⌋. By (8), we obtain

L_{nm} · 2^{m−1} = \begin{matrix}⌊ & \frac{m}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m}{2j}F_{n}^{2j}L_{n}^{m−2j}5^{j} ≡ L_{n}^{m} (mod F_{n}^{k+1}).

As gcd(F_{n}, L_{n}) = 1 by (7), we have F_{n}^{k+1} ∤ L_{n}^{m}. Therefore F_{n}^{k+1} ∤ L_{nm}.

5 Open questions

It is natural to ask if the converse of each theorem holds. Marques [9, Corollary 3] shows that a partial converse of Theorem 1 holds. More precisely, he shows that if F_{n}^{k+1} | F_{nm} and m is odd, then F_{n}^{k} | m. Whether or not the converse of Theorem 1 holds when m is even is still open. Similar questions are the following.

Q1 Assume that F_{n}^{k+1} ∥ F_{nm} and m is odd. Can we conclude that F_{n}^{k} ∥ m?

Q2 Assume that L_{n}^{k+1} ∥ L_{nm} and m is odd (or any other assumption). Can we conclude that L_{n}^{k} ∥ m?

Q3 Assume that L_{n}^{k+1} ∥ F_{nm} and m is even (or any other assumption). Can we conclude that L_{n}^{k} ∥ m?

Q4 Suppose that Q1, Q2, or Q3 has a negative answer. Can we say something about the divisibility of m by powers of the Fibonacci and Lucas numbers?

Q5 Benjamin and Rouse [2] show that Theorem 1 holds if the Fibonacci numbers are replaced by the generalized Lucas numbers of the first kind (given by u_{0} = 0, u_{1} = 1, and u_{n} = au_{n−1} + bu_{n−2} for n ≥ 2). Does Theorem 1 hold for other sequences? Can we extend the results to include exact divisibility by powers of the generalized Lucas numbers of the first kind?

6 Acknowledgment

The author receives financial support from Faculty of Science, Silpakorn University, contract number SRF-PRG-2557-07. The author would like to thank the referee for his/her careful reading and for his/her suggestions which improve the presentation of this article.

References

[1] A. Benjamin and J. Quinn, The Fibonacci numbers-exposed more discretely, Math. Mag. 76 (2003), 182–192.

[2] A. Benjamin and J. Rouse, When does F_{m}^{L} divide F_{n}? A combinatorial solution, in Proceedings of the Eleventh International Conference on Fibonacci Numbers and Their Applications, Vol. 194, Congressus Numerantium, 2009, pp. 53–58.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[4] J. H. Halton, On the divisibility properties of Fibonacci numbers, Fibonacci Quart. 4 (1966), 217–240.

[5] V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Divisibility by Fibonacci and Lucas squares, Fibonacci Quart. 15 (1977), 3–8.

[6] D. Kalman and R. Mena, The Fibonacci numbers-exposed, Math. Mag. 76 (2003), 167– 181.

[7] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001.

[8] T. Lengyel, The order of the Fibonacci and Lucas numbers, Fibonacci Quart. 33 (1995), 234–239.

[9] D. Marques, The order of appearance of powers of Fibonacci and Lucas numbers, Fibonacci Quart. 50 (2012), 239–245.

[10] Y. Matijasevich, Enumerable sets are Diophantine, Soviet Math. 11 (1970), 354–358.

[11] Y. Matijasevich, My collaboration with Julia Robison, Math. Intelligencer 14 (1992), 38–45.

[12] Y. Matijasevich, Hilbert’s Tenth Problem, MIT Press, 1996.

[13] K. Onphaeng and P. Pongsriiam, Subsequences and divisibility by powers of the Fibonacci numbers, Fibonacci Quart. 52 (2014), 163–171.

[14] C. Panraksa, A. Tangboonduangjit, and K. Wiboonton, Exact divisibility properties of some subsequences of Fibonacci numbers, Fibonacci Quart. 51 (2013), 307–318.

[15] P. Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer, 2000.

[16] J. Seibert and P. Trojovský, On divisibility of a relation of the Fibonacci numbers, Int. J. Pure Appl. Math. 46 (2008), 443–448.

[17] A. Tangboonduangjit and K. Wiboonton, Divisibility properties of some subsequences of Fibonacci numbers, East-West J. Math. Spec. Vol. (2012), 331–336.

[18] S. Vajda, Fibonacci and Lucas Numbers and the Golden Section: Theory and Applications, Dover Publications, 2008.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11A07. Keywords: Fibonacci number, Lucas number, exact divisibility.

(Concerned with sequences \underline{A000032}, and \underline{A000045}.)

Received July 24 2014; revised versions received November 5 2014; November 6 2014. Published in Journal of Integer Sequences, November 7 2014.

Return to Journal of Integer Sequences home page.