Brain Teaser #92: Solve Fibonacci Puzzle

[davilla]

Brain Thumper #6

Find the smallest positive integer that does not evenly divide any Fibonacci number in the sequence starting 1, 1, 2, 3, 5, 8, 13, 21, etc.

 

[catch.yossarian]

disregarding dividing by 1, could the smallest positive integer be 11?

 

[davilla]

disregarding dividing by 1

1 evenly divides a Fibonacci number (in fact it divides every Fibonacci number) so there's no reason to list it as an exception.

could the smallest positive integer be 11?

Sorry, 11 divides the tenth Fibonacci number, 55.

 

[NateTG]

There are no suitable numbers.

Let's assume, for a moment that there is some number, n with the desired property. Then we can look at the Fibonacci numbers modulo that number.

Since there are at most n different residues, and the state of the fibonacci sequence is determined by two consecutive values, there are at most [tex]n^2[/tex] states that the fibonacci sequence can be in.

Moreover, if I have [tex]F_k[/tex] and [tex]F_{k+1}[/tex] I know that [tex]F_{k-1}=F_{k+1}-F_{k}[/tex] for [tex]k>2[/tex] - so at any particular location (barring the start), the sequence is determined in both directions.

Now, since the number of possible states is finite, the sequence must, at some point, return to a state that it previously had, and because the sequence is deterministic in both directions, you have that the sequence mod n must be a single loop.

Now, in order loop back to the start [tex]1,1[/tex] the sequence must eventually get to [tex]-1,1,0...[/tex].

Since the sequence hits a value that is zero mod [tex]n[/tex] n divides some of the numbers.

In more concrete terms, given some [tex]n>0[/tex] there is at least one Fibonacci number in the first [tex]n^2[/tex] fibonacci numbers that is divisible by [tex]n[/tex].

 

[gnome]

Nate, please define the term state as you are using it in your proof.

 

[holly]

is it the number 89?

 

[davilla]

NateTG with the point!

In computer science, state is a term for the configuration of a program or an abstract computing machine at a given point in time as the collection of all of its data values. With analogous components, the meaning is the same in electrical engineering.

For a mathematician, the proof might be easier to understand using existential instantiation. There are only finitely many pairs (F(k), F(k+1)) mod n, so for some k there must be a j > k such that F(j) = F(k) and F(j+1) = F(k+1), mod n. Inductively we can prove that F(j+i) = F(k+i) mod n for every i where the expression is defined. Hence F(j-k) = 0 mod n.

 

[gnome]

I'm missing something here. How can we assume that every pair (F(k), F(k+1)) mod n is necessarily repeated simply because there is a finite number of pairs? How do we know that there isn't one such pair that is never repeated?

For example, F(5) = 1, mod 4 and F(6) = 0, mod 4. I think you're saying that we know that there must be some j>5 such that F(j) = 1, mod 4 and F(j+1) = 0, mod 4. But how do we know that? (Or is that not what you are saying at all?)

I don't doubt that NateTG's conclusion is correct. I'm just having trouble following the proof.

 

[davilla]

How can we assume that every pair (F(k), F(k+1)) mod n is necessarily repeated simply because there is a finite number of pairs? How do we know that there isn't one such pair that is never repeated?

NateTG concludes that "the sequence mod n must be a single loop" based on determinism of the minimal state, a consecutive pair of Fibonacci numbers mod n. If you consider a directed graph where each node is a state, determinism in both directions means that there's no branching forward or backward, so the only possibility for a finite graph is a loop.

In the variation I gave, it wasn't assumed that every pair (F(k), F(k+1)) mod n that occurs is repeated. This turns out to be the case, of course, but from the fact that there are a finite number, we only know that some pair must be repeated somewhere: "for some k there must be a j" such that j is a repeat of k. The induction with i must be carried backwards.

 

[NateTG]

I'm missing something here. How can we assume that every pair (F(k), F(k+1)) mod n is necessarily repeated simply because there is a finite number of pairs? How do we know that there isn't one such pair that is never repeated?

There are pairs that never occur. For example, every pair of consecutive fibonacci numbers is coprime, so the state 0,0 never occurs mod any number greater than 1.

There are a finite number of states that the finbonnaci sequence can be in, so at some point, it must repeat a state. (Where states are consecutive pairs.) Obviously once it's repeated, it's stuck in the loop.

Now, let's assume that the first repeated state is not 1,1. Then we can look at the first two occurances of a,b. So we have
1,1...a,b...a,b
where none of the ...'s contain a,b or 1,1
Now, consider that you can go to the left from the left hand a,b, since you know the sequence is ...b-a,a,b and then ...2a-b,b-a,a and then ...3a-2b,2a-b,b-a. But then we have the situation that that sequence (going to the left) gets to 1,1 before it gets to a,b for the first ... and gets to a,b before it gets to 1,1 on the second ... This is a contradiction, since the sequences must be the same.

Therefore, the first repeated state must be 1,1.

 

[NateTG]

Nate, please define the term state as you are using it in your proof.

In that context, I mean pairs of consecutive values of the Fibonacci numbers.

If you would like, here's a clearer proof using a directed graph as davilla suggested:

Let's assume, by contradiction, that some n with the desired property exists.

Now, construct a directed graph with [tex]n^2[/tex] nodes, and an arbitrary bijection from the ordered pairs [tex]p \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex] to the nodes in this graph. So now I can refer to vertices as [tex]v_{(a,b)} [/tex] with [tex] (a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex]. Then place edges from each vertex [tex]v_{(a,b)}[/tex] to the vertex [tex]v_{(b,a+b)}[/tex] (Where the addition is mod n).

Let's call this the Fibonacci mod n state graph.

By construction there is only one edge out of any vertex.

Now, given an arbitrary vertex [tex]v_{(a,b)}[/tex] the only vertex that has an edge to that vertex is [tex]v_{(b-a,a)}[/tex] (with subtraction mod n).

That means that every vertex has only one line in, and one line out.

Now, traveling along these edges starting with [tex]v_{(1,1)}[/tex] gives consecutive values of the Fibonacci sequence. Since there is a finite number of vertices, and an infinite number of values in the FIbonacci squenece, the path must eventually loop.

Now, let's assume that the first repeated vertex is not [tex]v_{(1,1)}[/tex]. Then there must be two edges leading into that vertex. One from the path from [tex]v_{(1,1)}[/tex] to that vertex, and another for the path from that vertex to itself (we know that the two are disjoint because this vertex is the first repeated vertex), but this contradicts that there is only one edge into any vertex. Therefore, the first repeated vertex is [tex]v_{(1,1)}[/tex].

This means that the fibonacci sequence mod n eventually hits ...,1,1 but that means that the fibonnaci sequence also hits ...,0,1,1 so there is a fibonacci number divisible by n./

 

[gnome]

Thanks very much for the explanations. I can follow the first. I follow the second in the sense that I can visualize a graph which I think is the graph you are describing. But my understanding of notation leaves much to be desired.

Does this
>>[tex]p \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex]

mean the same as this:

given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i ≤ n and 0 < j ≤ n ?​

As to the node you refer to as
>>
[tex]v_{(a,b)} (a,b) \in\mathbb{Z}_n[/tex]

can I interpret that as follows:

given two consecutive fibonacci numbers f_a, f_b and some integer n, in your node (a,b), a = f_a mod n and b = f_b mod n?​

But I'm puzzled by your child nodes [tex]v_{(a,a+b)}[/tex]. Did you mean to write [tex]v_{(b,a+b)}[/tex]? If not, then I must be misunderstanding the meaning of [tex]v_{(a,b)}[/tex]
so please help me out.

 

[NateTG]

Thanks very much for the explanations. I can follow the first. I follow the second in the sense that I can visualize a graph which I think is the graph you are describing. But my understanding of notation leaves much to be desired.

Does this
>>[tex]p \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex]

mean the same as this:

given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i ≤ n and 0 < j ≤ n ?​

Yes. [tex]\mathbb{Z}_n[/tex] is a notation for the intgers mod in, and [tex]\times[/tex] in that context is the cartesian product. (Technically it provides addition and subtraction, but I was explicit about that.)

As to the node you refer to as
>>
[tex]v_{(a,b)} (a,b) \in\mathbb{Z}_n[/tex]

can I interpret that as follows:

given two consecutive fibonacci numbers f_a, f_b and some integer n, in your node (a,b), a = f_a mod n and b = f_b mod n?​

That should definitely have been better. I meant that I can refer to [tex]v_{(a,b)}[/tex] where [tex]a[/tex] and [tex]b[/tex] are in [tex]\mathbb{Z}_n[/tex].

But I'm puzzled by your child nodes [tex]v_{(a,a+b)}[/tex]. D.id you mean to write [tex]v_{(b,a+b)}[/tex]? If not, then I must be misunderstanding the meaning of [tex]v_{(a,b)}[/tex]
so please help me out.

Once again, my error. I will correct those in the post, thank you.

 

[gnome]

Then I should have written

given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i < n and 0 < j < n​

not "≤ n", correct?

Thanks, NateTG.

 

[NateTG]

Then I should have written

given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i < n and 0 < j < n​

not "≤ n", correct?

Actually, either 0 &leq; i < n or 0 < i &leq; n work. Since [tex]0 \equiv n[/tex](mod n) they're equivalent. But one side must be &leq;. (Since the fibonacci sequence hits 0 mod n, those definitely need to be there.)

 

[gnome]

Duh...of course.

0 ≤ i < n and 0 ≤ j < n

Thanks again.