×

# Recurrences with modulo

Is there any specific way to solve recurrence of form (example):

$f(x) = (a \cdot f(x-1) + c) \bmod{r}$ (when recurrence involves modulo).

For recurrence without modular arithmetic I could use generating function method (multiply by $$x^n$$, sum, manipulate terms and so on) and often solve it in simple way. Could I somehow exploit information about recurrence solution without modulo to solve recurrence with modulo?

Note by Santiago Hincapie
3 weeks, 1 day ago

Sort by:

Well, we can solve it as $$f(x) = a f(x-1) + c$$, and then apply the $$\pmod{r}$$ at the end right?

Check out linear recurrence relations to show that $$f(x) = A a^{n-1} + \frac{ c(a^n-1)} { a-1}$$. Staff · 2 weeks, 4 days ago