I came across this recurrence function:
$$F(n) = a \times F(n-1) + b$$
where $F(0) =1$. We have to solve for $F(n) \pmod {m}$
But for very large $n$, solving it with computer is also taking time. Is there anyway to simplify this. I think the values will be repeated again after some '$n$' based upon the values of $a,b$ and $m$. But I am unable to figure out how to solve it.
$F(n) = T(n) + c \implies T(n) + c = aT(n-1) + ac + b$.
Choosing $c = b/(1-a)$, we get that $T(n) = a T(n-1) \implies T(n) = a^n T(0)$.
Hence, $$F(n) = T(n) + c = a^n T(0) + b/(1-a) = a^n (F(0) - b/(1-a)) + b/(1-a)\\ \implies F(n) = a^n F(0) +b \dfrac{1-a^n}{1-a} = a^n + b \dfrac{1-a^n}{1-a}$$
If you are just interested in $F(n) \pmod{m}$, then make use of the recurrence. Call $G(n) = F(n) \pmod{m}$. Precompute $a' = a \pmod{m}$, $b' = b \pmod{m}$. Then we have that $$G(n) \equiv \left(a'G(n-1) + b' \right) \pmod{m}$$
If $m$ is small enough, compute when the sequence $$ 1,1+a,1+a+a^2,1+a+a^2+a^3,\dots\tag{1} $$ becomes $0\bmod{m}$. If the $k^{\text{th}}$ term of $(1)$ is $0\bmod{m}$, then $$ \frac{a^k-1}{a-1}\equiv0\pmod{m}\quad\quad\text{and}\quad\quad a^k\equiv1\pmod{m}\tag{2} $$ Reduce $n'\equiv n\pmod{k}$ and you have $F(n)\equiv F(n')\pmod{m}$. If $m$ is much smaller than $n$, this will reduce the number of iterations.
If $m$ is large, then you can still compute (as shown by Marvis, et al) $$ F(n)=a^nF(0)+b\frac{a^n-1}{a-1}\pmod{m}\tag{3} $$ Although $a^n$ and $\frac{a^n-1}{a-1}$ may get very big, $(3)$ takes very little time.
$F(n)=a.F(n-1)+b=a(a.F(n-2)+b)=a^2F(n-2)+ab=a^2(a.F((n-3)+b)+ab=a^3F(n-3)+a^2b+ab=\ldots=a^nF(0)+a^{n-1}b+\cdots +ab$
Now if $a\mod m\ne 1$ $$F(n)\mod m=(a\mod m)^n+(b\mod m)\frac{1-(a\mod m)^n}{1-a\mod m}$$
If $a\mod m=1$ then $a^i\mod m=1$ for all $i$, hence $F(n)\mod m=1+(n-1)(b\mod m)$
