I found a cool application of finite fields to prove an intriguing result related to Fibonacci numbers last fall. The theorem goes as follows:
If then is divisible by
if then is divisible by
and is divisible by
for primes where denotes the th Fibonacci number.
This statement is both surprising and itself has nothing to do with finite fields, which is why I find it quite interesting. It also happens that using finite fields results in a very elegant proof! Let’s begin.
The first thing to notice is that the perfect squares are So, if and only if Quadratic Reciprocity tells us that
As a result, if and only if
Now, let’s consider the first case, when Then, is a perfect square modulo That is, there exists some integer such that In this field, acts exactly like By Binet’s Formula, the th Fibonacci Number is given by
and by Fermat’s Little Theorem, so working in our field, we have
This means that is a multiple of as desired. Note that we can only do this since “exists.”
Now, let’s move on to the second case, which is a little more interesting. Here, does not exist modulo but we can construct a field with characteristic such that it does. We introduce a variable which satisfies the simplification rule Then, acts like a root of the polynomial Without loss of generality, suppose is “equivalent” to the root So, our field now has . Since the Froebius Automorphism is an automorphism that maps field elements to , we can say that if and only if and as a result, is our other root Applying Binet’s Formula again, we have
The last case is clear, so we have proven the curious theorem! Although coming up with the proof seems impossible, the main intuition for arriving at the statement lies in embedding the algebraic numbers in Binet’s Formula into fields and playing around with them to see what kind of th Fibonacci numbers are divisible by their prime
Further Investigation
Following the same proof methods, as above, I investigated some more possible results. If we replace and with in the two first cases of the theorem, we can obtain a similar surprising result. Embedding in the same field of elements for we get the following:
This means that when the th Fibonacci number minus is a multiple of . We can do a similar thing for when Letting and in the field of elements as we did before, we have
In this case, when the th Fibonacci number plus is a multiple of . For nice symmetry, we can still say that is a multiple of
However, like before, given the result
If then is divisible by
if then is divisible by
and is divisible by
it is difficult to see how to prove this. However, through almost-magical finite field manipulations, we are able to conclude this. It is strange that we can actually “take” the and from the subscript of the Fibonacci number to the outside. Despite defying all intuition, this is really awesome, and it neatly exhibits the power of finite fields.
I would love to play around with this more, but I’ll keep it nice and concise for my first post. If anyone reads this, I hope you enjoyed it, and I hope to keep on posting cool little math tidbits in the future!
Source: I first learned about this in Sam Vandervelde’s Finite Fields class, but the result appears in this paper as well: https://math.berkeley.edu/~tb65536/Fibonacci_Exposition.pdf.
Leave a comment