Mathematics for Computer Science

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.n1/Cc 2 f.n2/C


Ccdf.nd/ (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.n1/  f.k1/ .modm/;

::

:

f.n.d1//  f.k.d1// .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 Œd1;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.d1/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.