# 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