I'm learning about polynomials stored in a closed form that resembles a generating function or power series. Generally speaking, I have fractions of polynomials, with one example being
$\displaystyle\sum_{k=0}^9{x^k} = \frac{1 - x^{10}}{1-x}$
So I have the representation on the right-hand side. I wish to evaluate this representation for values that return an integer. However, there's a catch. I want to further evaluate this result modulo a prime $p$. I'm wondering what the fastest way to do this is. Can someone please help?
Some Ideas One naive technique is to evaluate the fraction on the bottom to get a value, say $b$. Then we only have to evaluate the top $(\bmod b\cdot p)$, as this should give a result which we can then simply divide by $b$ to get the final answer.
I'm wondering whether a quotient ring or more likely a finite field can help return the final result in a more straightforward and perhaps easier way. I don't understand these two, however, so I'll need some help with them.