Re: math -- yet another Fibonacci mystery

On Tue, 11 Mar 2008 00:43:37 -0500, quasi <quasi@xxxxxxxx> wrote:

On Tue, 11 Mar 2008 05:10:54 GMT, Gerry Myerson
<gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

In article <41ubt3l8ombql810qcqph2pegdrfmqslo0@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote:

Let F[n] denote the n'th Fibonacci number.

Define functions f,g from N to N, as follows ...

f(m) = the period of the sequence F[n] (mod m), n = 1,2,3, ...

g(m) = the least positive integer n such that F[n] = 0 (mod m).

It's easy to prove that f(m) must be a multiple of g(m).

What surprised me was the discovery, based on the numerical evidence,
that the ratio f(m)/g(m) is always either 1, 2, or 4.

Can anyone prove this apparent, but mysterious fact, or at least
explain it heuristically?

quasi

Consider the sequence mod m.

Around g(m) it looks like a, 0, a, a, 2 a, 3 a, ...,
where a is the residue of term number g(m) - 1.
So, g(m + r) = a g(r) for all r.

I think the above line should be

So, F[g(m) + r] = a F[r], for all r.

Yes?

So g(2 m + r) = a^2 g(r).

Similarly (if I'm right about the prior correction), the above line
should be

So F[2 g(m) + r] = a^2 F[r].

But a standard Fibonacci property is
f_(n-1) f_(n+1) - (f_n)^2 = plus or minus 1,
so g(2 m + r) = pm1 g(r),
and g(4 m + r) = g(r).

I'm not sure how to correct the above 2 lines.

so g(2 m + r) = (+/-) F[r],
and g(4 m + r) = g(r).

At this point, I'm lost.

But if the errors I noted are actually not errors, let me apologize in
advance.

Ok, I now understand the proof you outlined.

Let j = f(m), k = g(m).

Then F[k] = 0 (mod m).

Let a = F[k-1] (mod m). Then also F[k+1] = a (mod m), hence the
identity

F[k-1]*F[k+1] - F[k]^2 = (+/-) 1 implies a^2 = (+/-) 1 (mod m)

and thus a^4 = 1 (mod m).

Also, based on the ideas you outlined,

F[k + r] = a F[r] (mod m)
F[2k + r] = a^2 F[r] (mod m)
F[3k + r] = a^3 F[r] (mod m)
F[4k + r] = a^4 F[r] (mod m) = F[r] (mod m).

In particular, F[4k] = 0 (mod m) and F[4k + 1] = 1 (mod m).

It follows that j|4k.

By definition of g, F[n] is nonzero (mod m) if n < k.

But then, since F[k + r] = a F[r] (mod m) for all positive integers r,
it follows that F[n] = 0 (mod m) iff n is a multiple of k.

In particular, j must be a multiple of k.

Thus, since k|j and j|4k, the ratio j/k must be 1, 2, or 4, as was to
be shown.

Thanks, Gerry.

quasi
.

Relevant Pages
Quantcast