# What's the easiest way to calculate a power series/polynomial modulo a prime?

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.

-
Please note that the representations may be much more complicated than the example I give, but they are all in the form of a fraction. –  Matt Groff Oct 22 '11 at 15:58
The question doesn't make much sense to me. How do you know which values of $x$ are going to make that polynomial an integer? What do you mean by "the fraction on the bottom"? All I see on the bottom is $1-x$, which isn't a fraction. Well, it is, if $x$ is a fraction, but then it's unlikely that the quotient is an integer. –  Gerry Myerson Oct 23 '11 at 6:15
@Gerry Myerson: Sorry for the confusion. I meant that the entire closed form is a fraction. I use only integer values for $x$, and I know ahead of time which values will lead to integer results. I think I managed to solve this on my own, though, so perhaps this question isn't worthwhile anymore. –  Matt Groff Oct 23 '11 at 13:41
Every integer value of $x$ leads to integer results. Anyway, you can evaluate $1-x^{10}$ mod $p$ by doing a few multiplications. Then if you've evaluated $1-x^{10}\equiv a\pmod p$, and $1-x\equiv b\pmod p$, the quotient you want is the solution $y$ to the congruence $by\equiv a\pmod p$. There are standard methods for solving such, based on Euclid's algorithm, and found in every intro number theory text. –  Gerry Myerson Oct 23 '11 at 23:58
@Gerry Myerson: Thanks. I'll study on. –  Matt Groff Oct 24 '11 at 2:06
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9022320508956909, "perplexity": 214.86520143344808}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-35/segments/1408500815861.64/warc/CC-MAIN-20140820021335-00157-ip-10-180-136-8.ec2.internal.warc.gz"}