Let $f(n)$ denote $n$th number in the Fibonacci sequence. Find a two digit prime such that $p$ divides $f(n) + f(n+100)$ for all $n$.
Well to be honest I have no idea how to solve this problem so I don't really have anything to show for my attempts. Well I did try to play around with the recursion a bit but it ended with just a jumbled up nothing burger. Anyone any ideas?
Let us consider Fibonacci sequence modulo $41$. One can look up the Pisano period of $41$, it is equal to $40$, but actually (the $0$-th and then) every $20$-th Fibonacci number is divisible by $41$. Here are Fibonacci numbers modulo $41$:
$$0, 1,1,2,3,5,8,13,21,34,14,7,21,28,8,36,3,39,1,40,0$$
The next two numbers are $$40, 40.$$ This can be interpreted as $$-1,-1.$$ So the numbers repeat, but with opposite sign.
This means that $F_n$ and $F_{n+20+40k}$ are opposite modulo $41$ for any non-negative integer $k$. Or, $F_n + F_{n+20+40k}$ is divisible by $41$. Putting $k=2$ we get that $F_n + F_{n+100}$ is divisible by $41$ for any $n$.
Note. How did we guess to consider $41$? From the list of Fibonacci numbers and their prime factorizations. I’d like to see the solution without using such data.
Edit
Here I will prove why $41$ is the only two digit prime with such property. I will use some of the facts about Pisano periods, as well as some other facts about Fibonacci numbers:
If $p$ is prime of the form $10k\pm1$ then its Pisano period is the divisor of $p-1$.
If $p$ is prime of the form $10k\pm3$ then its Pisano period is the divisor of $2(p+1)$.
Zeros go in a Pisano period over equal segments.
There are no zeros in $4$ first numbers after the initial zero in any Pisano period for all two-digit numbers (this one is obvious).
For every prime number $p$ there is a Fibonacci number that is divisible by $p$ (for example, one of the $F_{p-1}$, $F_{p}$, or $F_{p+1}$).
So, let’s take $n$ such that $p\mid F_n$. Since $p\mid F_n+F_{n+100}$, we get $p\mid F_{n+100}$. A zero occured in the Fibonacci sequence modulo $p$ after $100$ steps. This means that a divisor of Pisano period of $p$ is a divisor of $100$.
If $p$ is a prime that ends on $3$ or $7$, then $2(p+1)$ is not divisible by $5$, so the only common divisor of $2(p+1)$ and $100$ is $1$, $2$ or $4$, but those are too small.
If $p$ is a prime that ends on $9$, then $p-1$ is not divisible by $5$, so the only common divisor of $p-1$ and $100$ is $1$, $2$ or $4$, but those are too small, again.
If $p$ is a prime that ends on $1$, the problem starts, since $10$ and sometimes $20$ are added to the list of possible common divisors. I guess, you have to write down the first $10$ or $20$ numbers from Pisano period for these numbers. For $11$: $$0,1,1,2,3,5,8,2,10,1.$$
We see that $F_1+F_{101}$ is $2$ modulo $11$. For $31$. Maximal common divisor of $30$ and $100$ is $10$, so we check the first $10$ Fibonacci numbers modulo $31$:
$$0,1,1,2,3,5,8,13,21,3.$$
No second zero. For $61$ we will have to write down the first $20$ numbers:
$$0,1,1,2,3,5,8,13,21,34,55,28,22,50,11,0.$$
We got zero, but $15$ isn’t a divisor of $100$. For $71$ we need $20$ numbers as well:
$$0,1,1,2,3,5,8,13,21,34,55,18,2,20,22,42,64,35,28,63.$$
No second zero. Thus, the check is over. No other two-digit prime works.