How it Works › Forums › Exploration Problems (Interesting Math Problems!) › Unique Properties of Integers Exploration!
This topic contains 3 replies, has 2 voices, and was last updated by Yash Agarwal 3 years, 3 months ago.

AuthorPosts

MathJax TeX Test Page
Hey Math Circle Students!These math problems are for 20 points and really develop your skills as mathematicians to understand higher order thinking beyond just math competitions and AMC 8/Mathcounts, etc. These focus on observing and proving patterns and making conjectures!
If you don’t understand one of the questions, feel free to post in the questions forum here
1. Consider the terms of the Fibonacci sequence in mod 2, mod 3, mod 5. Note any patterns that you see and if you can, prove that there must be a pattern and calculate the period of the pattern. (Hint: $F_{n}=F_{n1}+F_{n2}$ where $F_{n}$ represents the $n$th term of the fibonnaci sequence which is 1,1,2,3,5,8… where you add the two previous terms to get the next term).
NOTE: The period of the “pattern” is defined as the smallest $k$ such that $F_{n+k}=F_{n}$ in the modulus you are working in. If that is unclear, then consider the following pattern: $1,2,3,1,2,3,1,2,3…..$.
The period of this pattern is $3$ because the length of each cycle of the pattern is $3$.2. Find powers of $2$ mod 3, mod 5, mod 7 and try to find a pattern and calculate the periods of the pattern. Do you notice anything about the period in these prime moduli?
If you discover a pattern or you manage to prove one of the problems, post your discoveries below! These are really openended so you can post any progress you have made on the problems!
Anton1. If we take this sequence mod 2, we get 1,1,0,1,1,0,1,1,0,1,1,0, so it has period 3. To prove this, we can first see that taking mod 2 is basically seeing if the numbers are odd or even. Since the first two are odd, the third must be even because the sum of 2 odds is always even. The term after that must be odd, since is it a sum of an even number and an odd number. The term after that must be odd as well, since it is a sum of an even number and an odd number. The last two terms are both odd, just like the two ones at the start of the sequence, so we know that this will repeat.
Next we can take this sequence mod 3, to get 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1. This sequence has period 8. This is the case because we can just add up each term of the mod sequence and take mod 3. Every time 1,1 comes up, the sequence must repeat.
We can do the same with mod 5, and just count the number of terms until 1,1 comes up again.. 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0, 1,1,2,3,0, which has period 20.
MathJax TeX Test Page
Very good Anton, you have received 20 points for your observations! Try to see if you can prove a more general result though that the fibonnaci sequence is periodic in $\bmod n$ for all integers $n$.
 This reply was modified 3 years, 3 months ago by admin.
Yash Agarwal#2:
The powers of 2 (mod 3) are: 1, 2, 1, 2, 1, 2, …
The period is 2 since the amount of numbers that repeat is 2.
The powers of 2 (mod 5) are: 1, 2, 4, 3, 1, 2, 4, 3, …
The period is 4 since the amount of numbers that repeat is 4.
The powers of 2 (mod 7) are: 1, 2, 4, 1, 2, 4, 1, 2, 4, …
The period is 3 since the amount of numbers that repeat is 3.
This response is written by Yash Agarwal.

AuthorPosts