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.