Putnam 2021, Problem B-4

Let $F_0, F_1, \ldots$ be the sequence of Fibonacci numbers, with $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. For $m > 2$, let $R_m$ be the remainder when the product $\prod_{k=1}^{F_m - 1} k^k$ is divided by $F_m$. Prove that $R_m$ is also a Fibonacci number.

Solution:
We can check directly that $R_3 = R_4 = 1$ are Virahanka-Fibonacci numbers; henceforth we will assume $m \geq 5$.

Denote the product $\prod_{k=1}^{F_m-1} k^k$ by $A$. Note that if $F_m$ is composite, say $F_m = ab$ for $a, b > 1$ integers, then $A$ is divisible by $a^ab^b$ and thus by $F_m = ab$; it follows that $R_m = 0 = F_0$ when $F_m$ is composite.

Now suppose that $F_m$ is prime. Since $F_{2n} = F_n(F_{n+1} + F_{n-1})$ for all $n$, $F_m$ is composite if $m > 4$ is even; thus we must have that $m$ is odd. Write $p = F_m$, and use $\equiv$ to denote congruence (mod $p$). Then we have
$$A = \prod_{k=1}^{p-1} (p-k)^{p-k} \equiv \prod_{k=1}^{p-1} (-k)^{p-k} = (-1)^{p(p-1)/2} \prod_{k=1}^{p-1} k^{p-k}$$
and consequently
$$A^2 \equiv (-1)^{p(p-1)/2} \prod_{k=1}^{p-1} (k^k k^{p-k})$$
$$= (-1)^{p(p-1)/2} ((p-1)!)^p$$
$$\equiv (-1)^{p(p+1)/2},$$
where the final congruence follows from Wilson's Theorem. Now observe that when $m$ is odd, $p = F_m$ must be congruent to either 1 or 2 (mod 4): this follows from inspection of the Virahanka-Fibonacci sequence mod 4, which has period 6: 1, 1, 2, 3, 1, 0, 1, 1, .... It follows that $A^2 \equiv (-1)^{p(p+1)/2} = -1$.

On the other hand, by the Kepler-Cassini identity
$$F_n^2 = (-1)^{n+1} + F_{n-1}F_{n+1}$$
with $n = m - 1$, we have $F_{m-1}^2 \equiv (-1)^m = -1$. Thus we have $0 \equiv A^2 - F_{m-1}^2 \equiv (A - F_{m-1})(A - F_{m-2})$. Since $p$ is prime, it must be the case that either $A = F_{m-1}$ or $A = F_{m-2}$, and we are done.

**Remark.** The Kepler-Cassini identity first appears in a letter of Kepler from 1608. Noam Elkies has scanned the relevant page of Kepler's collected works (slightly NSFW if your boss can read Latin).