Sunday, August 8, 2010

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.

Saturday, August 7, 2010

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.

Friday, August 6, 2010

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):

  • 5k/2 F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k+1)/2 F(kn+m)
    = ∑0 ≤ jk (  k   j  ) L( j+m ) L(n) j L(n−1)kj, for k odd.
  • 5k/2 L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k−1)/2 L(kn+m)
    = ∑0 ≤ jk (  k   j  ) F( j+m ) L(n) j L(n−1)kj, 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:

  • 5k/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.
  • 5k/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)2 5 (−1)n+1 (mod L(n)):

  • 5k/2 F (kn + m) F (m) (5 (−1)n+1)k/2 (mod L(n)), for k even.
  • 5(k+1)/2 F(kn+m) L(m) L(n−1) (5 (−1)n+1)(k−1)/2 (mod L(n)), for k odd.
  • 5k/2 L (kn + m) L (m) (5 (−1)n+1)k/2 (mod L(n)), for k even.
  • 5(k−1)/2 L(kn+m) F(m) L(n−1) (5 (−1)n+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)2+(−1)n
  • L(n−1) L(n+1) = L(n)2+5 (−1)n+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)2 (−1)n (mod F(n))
  • L(n−1)2 5 (−1)n+1 (mod L(n))


Now, consider the following two formulas from section 13:

  • F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) F(n) j F(n−1)kj
  • L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) F(n) j F(n−1)kj


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)2, 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 ≤ jk (  k   j  ) F ( j + m ) F(n) j F(n−1)kj, for any k.
  • 5k/2 F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k+1)/2 F(kn+m)
    = ∑0 ≤ jk (  k   j  ) L( j+m ) L(n) j L(n−1)kj, for k odd.


Formulas for the Lucas numbers:

  • L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) F(n) j F(n−1)kj, for any k.
  • 5k/2 L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k−1)/2 L(kn+m)
    = ∑0 ≤ jk (  k   j  ) F( j+m ) L(n) j L(n−1)kj, 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/√5k

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:

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

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

    = ∑0 ≤ jk (  k   j  )5 φ j L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) (L( j−1 ) + φ L( j )) L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) L( j−1 ) L(n) j L(n−1)kj  +
           φ ∑0 ≤ jk (  k   j  ) L( j ) L(n) j L(n−1)kj

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 5k/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:

  • 5k/2 L (kn − 1) = 0 ≤ jk (  k   j  ) L ( j − 1 ) L(n) j L(n−1)kj, for k even
  • 5k/2 L (kn) = 0 ≤ jk (  k   j  ) L ( j ) L(n) j L(n−1)kj, for k even

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

  • 5k/2 L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) L(n) j L(n−1)kj, for k even.

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

  • 5k/2 F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) L(n) j L(n−1)kj, for k even.


Case 2: k is odd.

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

We'll start with the formula 5k/2 (L(kn−1) + φ L(kn)) = 0 ≤ jk (  k   j  ) L( j−1 ) L(n) j L(n−1)kj +
φ ∑0 ≤ jk (  k   j  ) L( j ) L(n) j L(n−1)kj, 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 ≤ jk (  k   j  ) L( j−1 ) L(n) j L(n−1)kj  +
           (φ+2) ∑0 ≤ jk (  k   j  ) L( j ) L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) (2 L( j ) − L( j−1 )) L(n) j L(n−1)kj  +
     φ ∑0 ≤ jk (  k   j  ) (2 L( j−1 ) + L( j ) )L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) 5 F( j−1 ) L(n) j L(n−1)kj  +
           φ ∑0 ≤ jk (  k   j  ) 5 F( j ) L(n) j L(n−1)kj

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 ≤ jk (  k   j  ) F( j−1 ) L(n) j L(n−1)kj

and

  • 5(k−1)/2 L(kn)
    = ∑0 ≤ jk (  k   j  ) F( j ) L(n) j L(n−1)kj.

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

  • 5(k−1)/2 L(kn+m)
    = ∑0 ≤ jk (  k   j  ) F( j+m ) L(n) j L(n−1)kj,
    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 ≤ jk (  k   j  ) L( j+m ) L(n) j L(n−1)kj,
    for k odd.