# Calculate the remainder when there are division

Supose we have a set $S$ of natural numbers. We define: $$f(x) = \begin{cases} {x \over 2} & x \text{ is even } \\ {x - 1 \over 2} & x \text{ is odd }\end{cases}$$

Now let $a_0 = a_1 = 1$ and $a_n = a_{n-1} + a_{n-2}$ for $n \notin S$ and $a_n = f(a_{n-1} + a_{n-2})$ otherwise for $n > 1$.

I want to calculate the remainder of $a_n \bmod p$ for $p$ prime. The problem is that the numbers become quite large so I can not store then. I must work with the reminders.

My fist idea was to work with the modular inverse of $2$ and e kept the remainder mod p at each step and instead of dividing by $2$, I multiply by $1/2$. The problem is that is does not work if $S$ has more than one element.

I think the solution is to keep the values $\bmod 2^y\cdot p$ where $y$ is the number of elements in $S$ $(\#S)$. And in the end take do remainder of $a_n \bmod p$. It seems to work but I don't understand why...

I'm sorry if I was not clear.

Thank you.

-
How big is p? And how big is n, or the set S? This matters for what time/space complexities would be acceptable. – ShreevatsaR Aug 11 '10 at 20:43
#S <= 50 and n,p <= 10^9 – fran.aubry Aug 13 '10 at 14:27

This sounds similar to computing the last nonzero base-10 digit of factorial(n). The fact that you are, according to some scheme, dropping the last bit of what would otherwise be a Fibonacci sequence expressed in binary makes me think there is no hope for finding any periodicity in the values mod p, which is what happens in the Fibonacci sequence itself. If you drop the last bit only finitely many times, then continue after that, your sequence modulo p will become periodic.

-
Yes, I read the FAQ. I invite email from a moderator regarding signatures. [signature removed by moderator] – G. Paseman Aug 11 '10 at 21:49
Ok, but I am not trying to find some kind of periodicity because I can afford computing the value for all m <= n. If I never divided by 2 it would be sufficient to work in Z_p. But with division after some trial and error it seemed that if I work in Z_((2^y) * p) and then take the final result and do mod p I get the right answer. I want to know why it works, or a counter example. – fran.aubry Aug 13 '10 at 14:37