Problem 12128
(American Mathematical Monthly, Vol.126, August-September 2019) Proposed by O. Kouba (Syria).
LetFn be then-th Fibonacci number, defined by F0= 0, F1= 1, and Fn+1= Fn+ Fn−1forn ≥ 1.
Find, in terms ofn, the number of trailing zeros in the decimal representation of Fn.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. Let νp(n) be the highest power of a prime p which divides a positive integer n. We will show that the number of trailing zeros of Fn is equal to
min(ν2(Fn), ν5(Fn)) =
0 if b = 0 or c = 0,
1 if b ≥ 1 and c ≥ 1 and a = 0, min(a + 2, c) if b ≥ 1 and c ≥ 1 and a ≥ 1.
where n = 2a· 3b· 5c· m with a, b, c ≥ 0 and gcd(m, 30) = 1.
The above formula follows straightforwardly from the next two claims.
Claim 1. ν5(Fn) = ν5(n).
For n ≥ 1, by the Binet’s formula, 2n−1Fn= (1 +√
5)n− (1 −√ 5)n 2√
5 = n +
⌊(n−1)/2⌋
X
k=1
n
2k + 1
5k.
Since for 1 ≤ k ≤ ⌊(n − 1)/2⌋, ν5
n 2k + 1
5k
= ν5
n
2k + 1
n − 1 2k − 1
5k
= ν5(n) − ν5(2k + 1) + ν5 n − 1 2k − 1
5k
≥ ν5(n) − ν5(2k + 1) + k > ν5(n) it follows that ν5(Fn) = ν5(2n−1Fn) = ν5(n).
Claim 2. ν2(Fn) =
0 if n 6≡ 0 (mod 3), 1 if n ≡ 3 (mod 6), ν2(n) + 2 if n ≡ 0 (mod 6).
It is easy to see by induction that Fn is even if and only if n ≡ 0 (mod 3).
For m ≥ 1, by the Binet’s formula, F3m=(1 +√
5)3m− (1 −√ 5)3m 23m√
5 = (2 +√
5)m− (2 −√ 5)m
√5 =
⌊(m−1)/2⌋
X
k=0
m
2k + 1
5k2m−2k. Thus, if n = 3m = 6q + 3 then
Fn = 2 · 5q+ 8
q−1
X
k=0
2q + 1 2k + 1
5k4q−1−k and we find that ν2(Fn) = 1.
If n = 3m = 6q then
Fn= 4(2q)5q−1+
q−2
X
k=0
2q 2k + 1
5k4q−k.
Therefore ν2(Fn) = ν(4(2q)5q−1) = ν2(2q) + 2 = ν2(n) + 2 because for 0 ≤ k ≤ q − 2, ν2
2q 2k + 1
5k4q−k
= ν5
2q 2k + 1
2q − 1 2k
5k4q−k
= ν2(2q) + ν22q − 1 2k
5k
+ 2(q − k) > ν2(2q) + 2.
