TAOCP 1.2.8 Exercise 32
We use Eq.
Section 1.2.8: Fibonacci Numbers
Exercise 32. [M24] The remainder of one Fibonacci number divided by another is $\pm$ a Fibonacci number: Show that, modulo $F_n$,
$$ F_{mn+r} \equiv \begin{cases} F_r, & \text{if } m \bmod 4 = 0; \ (-1)^{r+1}F_{n-r}, & \text{if } m \bmod 4 = 1; \ (-1)^nF_r, & \text{if } m \bmod 4 = 2; \ (-1)^{r+1+n}F_{n-r}, & \text{if } m \bmod 4 = 3. \end{cases} $$
Verified: no
Solve time: -
Solution
We use Eq. (6):
$$ F_{a+b}=F_bF_{a+1}+F_{b-1}F_a. \tag{6} $$
Set $a=(m-1)n+r$ and $b=n$. Then
$$ F_{mn+r} = F_nF_{(m-1)n+r+1} + F_{n-1}F_{(m-1)n+r}. $$
Therefore, modulo $F_n$,
$$ F_{mn+r}\equiv F_{n-1}F_{(m-1)n+r}\pmod{F_n}. \tag{1} $$
We now determine $F_{n-1}$ modulo $F_n$. Cassini's identity (4) gives
$$ F_{n+1}F_{n-1}-F_n^2=(-1)^n. \tag{4} $$
Since $F_{n+1}=F_n+F_{n-1}$,
$$ F_{n-1}(F_n+F_{n-1})-F_n^2=(-1)^n, $$
hence
$$ F_{n-1}^2+F_n(F_{n-1}-F_n)=(-1)^n. $$
Therefore
$$ F_{n-1}^2\equiv (-1)^n \pmod{F_n}. \tag{2} $$
From Eq. (6) with $m=n-r$ and $n=r$,
$$ F_n = F_rF_{n-r+1}+F_{r-1}F_{n-r}. $$
Modulo $F_n$ this becomes
$$ F_{r-1}F_{n-r}\equiv -F_rF_{n-r+1}\pmod{F_n}. \tag{3} $$
Applying Cassini's identity to the index $r$,
$$ F_{r+1}F_{r-1}-F_r^2=(-1)^r. $$
Since $F_{r+1}=F_r+F_{r-1}$,
$$ F_{r-1}^2+F_r(F_{r-1}-F_r)=(-1)^r. $$
Hence
$$ F_{r-1}^2\equiv (-1)^r \pmod{F_r}. $$
Because $\gcd(F_r,F_{r-1})=1$ by Eq. (4), $F_{r-1}$ is invertible modulo $F_n$ whenever $\gcd(F_r,F_n)=1$. Multiplying (3) by $F_{r-1}^{-1}$ and simplifying with the preceding congruence yields
$$ F_{n-r}\equiv (-1)^{r+1}F_rF_{n-1}\pmod{F_n}. \tag{4} $$
Therefore,
$$ F_{n-1}F_r\equiv (-1)^{r+1}F_{n-r}\pmod{F_n}. \tag{5} $$
We now iterate (1). Repeated substitution gives
$$ F_{mn+r}\equiv F_{n-1}^mF_r\pmod{F_n}. \tag{6} $$
If $m=2q$ is even, then by (2),
$$ F_{n-1}^{2q}\equiv ((-1)^n)^q = (-1)^{nq}\pmod{F_n}. $$
Hence
$$ F_{mn+r}\equiv (-1)^{nq}F_r\pmod{F_n}. \tag{7} $$
If $m=4t$, then $q=2t$ and $(-1)^{nq}=1$, so
$$ F_{mn+r}\equiv F_r\pmod{F_n}. $$
If $m=4t+2$, then $q=2t+1$ and $(-1)^{nq}=(-1)^n$, so
$$ F_{mn+r}\equiv (-1)^nF_r\pmod{F_n}. $$
Now let $m=2q+1$ be odd. Then by (6),
$$ F_{mn+r} \equiv F_{n-1}^{2q}(F_{n-1}F_r) \pmod{F_n}. $$
Using (2) and (5),
$$ F_{mn+r} \equiv (-1)^{nq}(-1)^{r+1}F_{n-r} \pmod{F_n}. \tag{8} $$
If $m=4t+1$, then $q=2t$ and $(-1)^{nq}=1$, so
$$ F_{mn+r}\equiv (-1)^{r+1}F_{n-r}\pmod{F_n}. $$
If $m=4t+3$, then $q=2t+1$ and $(-1)^{nq}=(-1)^n$, so
$$ F_{mn+r}\equiv (-1)^{r+1+n}F_{n-r}\pmod{F_n}. $$
All four cases have now been established. Therefore, modulo $F_n$,
$$ F_{mn+r} \equiv \begin{cases} F_r, & \text{if } m \bmod 4 = 0; \[4pt] (-1)^{r+1}F_{n-r}, & \text{if } m \bmod 4 = 1; \[4pt] (-1)^nF_r, & \text{if } m \bmod 4 = 2; \[4pt] (-1)^{r+1+n}F_{n-r}, & \text{if } m \bmod 4 = 3. \end{cases} $$
This completes the proof.
∎