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