Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

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.

share|improve this answer
add comment

$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)$

share|improve this answer
add comment

$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}$$

share|improve this answer
1  
+1. Though of course if $a-1$ is not coprime with $m$, then this formula is not so helpful. –  Henning Makholm Jun 28 '12 at 19:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.