Problem 10974
(American Mathematical Monthly, Vol.109, November 2002) Proposed by S. Marivani (USA).
The digital root ρ(n) of a positive integer n is the eventual image of n under the mapping that carries an integer n to the sum of its base-ten digit. Thus ρ(10974) = ρ(21) = 3. Find ρ(Fn), where Fn is the nth Fibonacci number, with F1= F2= 1.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
It is well known that the digital root of a positive integer n is the remainder of the division of n by 9, so we define
fn= mod(Fn,9) = ρ(Fn).
The sequence fn can be generated by the recurrence relation
fn+1= fn+ fn−1 ( mod 9 ) f1= 1, f2= 1
and it is periodic with a period length of 24. Indeed
f1= 1 f2= 1 f3= 2 f4= 3 f5= 5 f6= 8 f7= 4 f8= 3 f9= 7 f10= 1 f11= 8 f12= 0 f13= 8 f14= 8 f15= 7 f16= 6 f17= 4 f18= 1 f19= 5 f20= 6 f21= 2 f22= 8 f23= 1 f24= 0.
and the sequence goes on with f25= f1= 1 and f26= f2= 1.
A first explicit formula for fn is the following fn= (5 + i)n− (5 − i)n
2i = Im ((5 + i)n) ( mod 9 ).
Note that the complex numbers 5+i and 5−i allow to split in the Galois field GF(9) the characteristic polynomial x2− x − 1 associated to the Fibonacci recurrence equation. The formula can be proven by induction:
f1= Im(5 + i) = 1 ( mod 9 ),
f2= Im (5 + i)2 = Im (6 + i) = 1 ( mod 9 ).
moreover, for n ≥ 2, we have that
fn+ fn−1= Im ((5 + i)n) + Im (5 + i)n−1
( mod 9 )
= Im (5 + i)n+ (5 + i)n−1
( mod 9 )
= Im (5 + i)n−1· (5 + i + 1)
( mod 9 )
= Im (5 + i)n−1· (5 + i)2 = fn+1 ( mod 9 ).
Using the formula one can easily show that the sequence is periodic: since by the Fermat’s Little Theorem mod(26,9) = 1, then
(5 + i)24= (5 + i)38
= (2(1 + i))8= 28· 24= 212= 1 ( mod 9 ) and for n ≥ 1
fn+24= Im (5 + i)n· (5 + i)24 = Im ((5 + i)n) = fn ( mod 9 ).
Hence the computation of fn can be further on simplified:
fn= Im
(5 + i)(n,24)
( mod 9 ) where (n, 24) = mod(n, 24) and, since
5 + i =√
26 exp
iarcsin
√1 26
, we have our final formula
fn= (√
26)(n,24)sin
(n, 24) · arcsin
√1 26
( mod 9 ).
