Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

$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|cite|improve this answer
+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

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|cite|improve this answer

$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|cite|improve this answer

Your Answer


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.