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'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.

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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.