FT18: Divisibility Properties for the Lucas Numbers

Two other formulas from part 16 contain terms with the factor F(m), and so can be treated similarly to the previous post. These are:

• F(kn + m) ≡ (−1)^(n+1)k/2 F (m) (mod L(n)),
  for k even.

• L(kn+m) ≡ (−1)^{(n+1)(k−1)/2} F(m) L(n−1) (mod L(n)),
  for k odd.

Take m = 0 and use the fact that F(0) = 0 to see that:

• L(n) | F (kn) for k even.

• L(n) | L (kn) for k odd.

FT17: Divisibility Properties for the Fibonacci Numbers

Let's look at the first two congruences from the previous section:

• F(kn + m) ≡ (−1)^nk/2 F (m) (mod F(n)),
  for k even.

• F(kn + m) ≡ (−1)^n(k−1)/2 F (m) F(n−1) (mod F(n)),
  for k odd.

Since F(0) = 0, we can take m = 0 here to see that:

• n | j implies F(n) | F(j)

(where "x | y" means "y is a multiple of x").

Here's a direct consequence of this:

• If F(n) is prime, then either n is prime or n=4.

In fact, we can improve on the divisibility property. We'll show that:

• gcd(F(m), F(n)) = F(gcd(m, n)) for non-zero m and n.

To see this, first observe that it's sufficient to look at positive m and n, since F(−x) = ±F(x).

Also, for x > 1, it's easy to see by induction that F(x−1) and F(x) are relatively prime.

Now, since gcd(m, n) | m and gcd(m, n) | n, the divisibility property above tells us that F(gcd(m, n)) is a common divisor of F(m) and F(n).

To complete the proof, we'll use mathematical induction. If the claim fails, we can let n be the least positive integer for which (*) there exists a positive integer m < n such that F(m) and F(n) have a common divisor d > F(gcd(m, n)).

Divide n by m to write n = qm + r, with 0 ≤ r < m.

Note that r > 0, since if m | n, we already know that there is no such d.

By the congruence for F, we have

F(n) = F (qm + r) ≡ ±F(r) or ±F(r) F(m−1) (mod F(m)).

So at least one of the four numbers ±F(r) or ±F(r) F(m−1) is equal to F(n) plus some multiple of F(m).

Since d divides both F(m) and F(n), d also divides at least one of the four numbers ±F(r) or ±F(r) F(m−1).

Now, d and F(m−1) are relatively prime; this is because d divides F(m), which is relatively prime to F(m−1). It follows that d divides F(r).

So we know that 0 < r < m and that d is a common divisor of F(r) and F(m). Also, n = qm+r, so gcd(r, m) = gcd(n, m), and hence that d > F(gcd(r, m)). But this contradicts the choice of n as the least positive number satisfying (*), completing the proof by induction.

FT16: Summary of Modular Formulas for F(kn+m) and L(kn+m)

• F(kn + m) ≡ (−1)^nk/2 F (m) (mod F(n)),
  for k even.

• F(kn + m) ≡ (−1)^n(k−1)/2 F (m) F(n−1) (mod F(n)),
  for k odd.

• L(kn + m) ≡ (−1)^nk/2 L (m) (mod F(n)),
  for k even.

• L(kn + m) ≡ (−1)^n(k−1)/2 L (m) F(n−1) (mod F(n)),
  for k odd.

• F(kn + m) ≡ (−1)^(n+1)k/2 F (m) (mod L(n)),
  for k even.

• 5 F(kn+m) ≡ (−1)^{(n+1)(k−1)/2} L(m) L(n−1) (mod L(n)),
  for k odd.

• L(kn + m) ≡ (−1)^(n+1)k/2 L(m) (mod L(n)),
  for k even.

• L(kn+m) ≡ (−1)^{(n+1)(k−1)/2} F(m) L(n−1) (mod L(n)),
  for k odd.

FT15: F(kn+m) and L(kn+m) mod L(n )

In this section, we look at the remaining four formulas from part 13, reducing them modulo L(n):

• 5^k/2 F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

• 5^(k+1)/2 F(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j+m ) L(n) ^j L(n−1)^k−j, for k odd.

• 5^k/2 L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

• 5^(k−1)/2 L(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j+m ) L(n) ^j L(n−1)^k−j, for k odd.

Each term in each of these sums is a multiple of L(n), with the possible exception of the terms with j=0. So we get the following congruences:

• 5^k/2 F (kn + m) ≡ F ( m ) L(n−1)^k (mod L(n)), for k even.

• 5^(k+1)/2 F(kn+m) ≡ L( m ) L(n−1)^k (mod L(n)), for k odd.

• 5^k/2 L (kn + m) ≡ L ( m ) L(n−1)^k (mod L(n)), for k even.

• 5^(k−1)/2 L(kn+m) ≡ F( m ) L(n−1)^k (mod L(n)), for k odd.

Simplify these using the congruence L(n−1)² ≡ 5 (−1)ⁿ⁺¹ (mod L(n)):

• 5^k/2 F (kn + m) ≡ F (m) (5 (−1)ⁿ⁺¹)^k/2 (mod L(n)), for k even.

• 5^(k+1)/2 F(kn+m) ≡ L(m) L(n−1) (5 (−1)ⁿ⁺¹)^(k−1)/2 (mod L(n)), for k odd.

• 5^k/2 L (kn + m) ≡ L (m) (5 (−1)ⁿ⁺¹)^k/2 (mod L(n)), for k even.

• 5^(k−1)/2 L(kn+m) ≡ F(m) L(n−1) (5 (−1)ⁿ⁺¹)^(k−1)/2 (mod L(n)), for k odd.

Now, L(n) is relatively prime to every power of 5, so we can conclude:

• F(kn + m) ≡ (−1)^(n+1)k/2 F (m) (mod L(n)), for k even.

• 5 F(kn+m) ≡ (−1)^{(n+1)(k−1)/2} L(m) L(n−1) (mod L(n)), for k odd.

• L(kn + m) ≡ (−1)^(n+1)k/2 L(m) (mod L(n)), for k even.

• L(kn+m) ≡ (−1)^{(n+1)(k−1)/2} F(m) L(n−1) (mod L(n)), for k odd.

FT14: F(kn+m) and L(kn+m) mod F(n )

Next we'll look at the formulas from part 13, but taken modulo F(n) or L(n).

First, though, let's mention a couple of simple formulas which will be useful. Start with the following, which can be proven by mathematical induction.)

• F(n−1) F(n+1) = F(n)²+(−1)ⁿ
• L(n−1) L(n+1) = L(n)²+5 (−1)ⁿ⁺¹

We'll reduce these modulo F(n) and L(n), respectively. Using the fact that F(n−1) ≡ F(n+1) (mod F(n)), and similarly for L, we get:

• F(n−1)² ≡ (−1)ⁿ (mod F(n))
• L(n−1)² ≡ 5 (−1)ⁿ⁺¹ (mod L(n))

Now, consider the following two formulas from section 13:

• F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) F(n) ^j F(n−1)^k−j

• L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) F(n) ^j F(n−1)^k−j

All the terms in the two sums are multiples of F(n) except possibly for the j=0 term in each.

In consequence, we have the following congruences:

• F (kn + m) ≡ F (m) F(n−1)^k (mod F(n))

• L (kn + m) ≡ L (m) F(n−1)^k (mod F(n))

Now, applying the congruence above for F(n−1)², we have:

• F (kn + m) ≡ (−1)^nk/2 F (m) (mod F(n)), for k even

• F (kn + m) ≡ (−1)^n(k−1)/2 F (m) F(n−1) (mod F(n)), for k odd

• L (kn + m) ≡ (−1)^nk/2 L (m) (mod F(n)), for k even

• L (kn + m) ≡ (−1)^n(k−1)/2 L (m) F(n−1) (mod F(n)), for k odd

FT13: Summary of Formulas for F(kn+m) and L(kn+m)

The previous two sections covered a variety of formulas for F(kn+m) and L(kn+m); we summarize them here.

Formulas for the Fibonacci numbers:

• F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) F(n) ^j F(n−1)^k−j, for any k.

• 5^k/2 F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

• 5^(k+1)/2 F(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j+m ) L(n) ^j L(n−1)^k−j, for k odd.

Formulas for the Lucas numbers:

• L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) F(n) ^j F(n−1)^k−j, for any k.

• 5^k/2 L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

• 5^(k−1)/2 L(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j+m ) L(n) ^j L(n−1)^k−j, for k odd.

FT12: Lucas-Based Formulas for F(kn+m) and L(kn+m)

Let's follow the method of the last section, but using the formula

• (L(kn−1) + φL(kn))/√5 = (L(n−1) + φL(n))^k/√5^k

with Lucas numbers, instead of the similar formula with Fibonacci numbers).

Using the binomial formula and the equation φ ^j = (L( j − 1 ) + φ L ( j )) / √5, we get:

• 5^k/2 (L(kn−1) + φ L(kn))

  = √5 (L(n−1) + φ L(n))^k

  = ∑_{0 ≤ j ≤ k} (  k   j  ) √5 φ ^j L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) (L( j−1 ) + φ L( j )) L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j−1 ) L(n) ^j L(n−1)^k−j  +
         φ ∑_{0 ≤ j ≤ k} (  k   j  ) L( j ) L(n) ^j L(n−1)^k−j

We'll need to treat this differently based on whether the number k is even or odd.

Case 1: k is even.

If k is even, then 5^k/2 is an integer. It follows that, as in part 11, we can apply the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, to conclude that the following two formulas must be true:

• 5^k/2 L (kn − 1) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j − 1 ) L(n) ^j L(n−1)^k−j, for k even
• 5^k/2 L (kn) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j ) L(n) ^j L(n−1)^k−j, for k even

Combine these two formulas with the basic recurrence relation for the Lucas numbers to yield:

• 5^k/2 L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

Also, the formula F(x) = (L(x−1) + L(x+1)) / 5 gives us:

• 5^k/2 F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

Case 2: k is odd.

If k is odd, then 5^k/2 is an integer multiple of √5, so it is irrational.

We'll start with the formula 5^k/2 (L(kn−1) + φ L(kn)) = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j−1 ) L(n) ^j L(n−1)^k−j +
φ ∑_{0 ≤ j ≤ k} (  k   j  ) L( j ) L(n) ^j L(n−1)^k−j, from right before we split into two cases.

Multiply by 2φ−1 = √5 and use the fact that φ √5 = φ + 2 to yield:

• 5^(k+1)/2 (L(kn−1) + φ L(kn))

  = (2φ−1) ∑_{0 ≤ j ≤ k} (  k   j  ) L( j−1 ) L(n) ^j L(n−1)^k−j  +
         (φ+2) ∑_{0 ≤ j ≤ k} (  k   j  ) L( j ) L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) (2 L( j ) − L( j−1 )) L(n) ^j L(n−1)^k−j  +
   φ ∑_{0 ≤ j ≤ k} (  k   j  ) (2 L( j−1 ) + L( j ) )L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) 5 F( j−1 ) L(n) ^j L(n−1)^k−j  +
         φ ∑_{0 ≤ j ≤ k} (  k   j  ) 5 F( j ) L(n) ^j L(n−1)^k−j

Since we're assuming that k is odd, 5^(k+1)/2 is an integer, and, dividing by 5, it follows that:

• 5^(k−1)/2 L(kn−1)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j−1 ) L(n) ^j L(n−1)^k−j

and

• 5^(k−1)/2 L(kn)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j ) L(n) ^j L(n−1)^k−j.

We can apply the recurrence relations for F and L to conclude that:

• 5^(k−1)/2 L(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j+m ) L(n) ^j L(n−1)^k−j,
  for k odd.

Finally, using the facts that 5F(x) = L(x−1) + L(x+1) and L(x) = F(x−1) + F(x+1), we have:

• 5^(k+1)/2 F(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j+m ) L(n) ^j L(n−1)^k−j,
  for k odd.

FT11: Fibonacci-Based Formulas for F(kn+m) and L(kn+m)

In the last section, we derived the following form of our analogue to de Moivre's theorem:

• F(kn−1) + φ F(kn) = (F(n−1) + φ F(n))^k

Expanding the expression on the right with the binomial formula, applying the equation φ ^j = F( j − 1 ) + φ F ( j ), and then using the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, one obtains the following two formulas:

• F (kn − 1) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j − 1 ) F(n) ^j F(n−1)^k−j
• F (kn) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j ) F(n) ^j F(n−1)^k−j

Combine these two formulas with the basic recurrence relation for the Fibonacci numbers to yield:

• F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) F(n) ^j F(n−1)^k−j

Using the fact that L(x) = F(x−1) + F(x+1), we can also see that:

• L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) F(n) ^j F(n−1)^k−j

FT10: More on the de Moivre Analogue

In part 9, we looked at an analogue to de Moivre's theorem. Slightly rephrased, we saw that:

• L(n)/2 + √5 F(n)/2 = φⁿ

so that:

• L(kn)/2 + √5 F(kn)/2 = (L(n)/2 + √5 F(n)/2)^k.

However, we would like to eliminate the factors of ½, since, when we derive other formulas from these, the ½'s end up obscuring which numbers are integers.

We'll actually do this in two ways, one using the Fibonacci numbers and one using the Lucas numbers.

Taking the formula φⁿ = L(n)/2 + √5 F(n)/2, rewriting √5 as 2φ − 1, and using the fact that L(n) = 2F(n−1) + F(n) yields:

• φⁿ = F(n−1) + φ F(n)

Similarly, but using the fact that F(n) = (2L(n−1) + L(n))/5, we get:

• φⁿ = (L(n−1) + φL(n))/√5

Alternatively, one can prove these two formulas for φⁿ by mathematical induction.

Plugging these expressions into the formula (φⁿ)^k = φ^nk results in two more forms of our analogue to de Moivre's theorem:

• F(kn−1) + φ F(kn) = (F(n−1) + φ F(n))^k
• (L(kn−1) + φL(kn))/√5 = (L(n−1) + φL(n))^k/√5^k

Next we'll look at some applications of these formulas.

FT9: de Moivre's Formula

In this section, we look at the analogue to de Moivre's formula, cos kx + i sin kx = (cos x + i sin x)^k.

Let n be any integer. We know that L(n) + √5 F(n) = 2 φⁿ.

It follows that, for any non-negative integer k:

• L(kn) + √5 F(kn) = (L(n) + √5 F(n))^k / 2^k—1

If k is positive, we can expand this using the binomial theorem. Then, applying the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, we can derive the following two formulas:

• 2^k—1 L(kn) = ∑_{0 ≤ j ≤ [k/2]} (  k 2 j ) 5 ^j F(n) ^2j L(n) ^k—2j
• 2^k—1 F(kn) = ∑_{0 ≤ j ≤ [(k—1)/2]} (      k     2 j + 1 ) 5 ^j F(n)^2j+1 L(n)^k—2j—1

Note: [x] here denotes the greatest integer less than or equal to x.

However, the factor 2^k—1 here gets in the way, and we'll come up with more useful versions of these formulas in the next section.