Chapter 8 Number Theory296
Problem 8.33.
This problem will use elementary properties of congruences to prove that every
positive integer divides infinitely many Fibonacci numbers.
A functionfWN!Nthat satisifies
f.n/Dc 1 f.n 1/Cc 2 f.n 2/CCcdf.n d/ (8.38)
for someci 2 Nand allndis calleddegreedlinear-recursive.
A functionf WN!Nhas a degreedrepeat modulomatnandkwhen it
satisfies the followingrepeat congruences:
f.n/ f.k/ .modm/;
f.n 1/ f.k 1/ .modm/;
::
:
f.n .d 1// f.k .d 1// .modm/:
fork > nd 1.
For the rest of this problem, assume linear-recursive functions and repeats are
degreed > 0.
(a)Prove that if a linear-recursive function has a repeat modulomatnandk, then
it has one atnC 1 andkC 1.
(b)Prove that for allm > 1, every linear-recursive function repeats modulomat
nandkfor somen;k 2 Œd 1;dCmd/.
(c)A linear-recursive function isreverse-linearif itsdth coefficientcd D ̇ 1.
Prove that if a reverse-linear function repeats modulomatnandkfor somend,
then it repeats modulomatn 1 andk 1.
(d)Conclude that every reverse-linear function must repeat modulomatd 1
and.d 1/Cjfor somej > 0.
(e)Conclude that iff is an reverse-linear function andf.k/D 0 for somek 2
Œ0;d/, then every positive integer is a divisor off.n/for infinitely manyn.
(f)Conclude that every positive integer is a divisor of infinitely many Fibonacci
numbers.
Hint:Start the Fibonacci sequence with the values 0,1 instead of 1, 1.