If I have a polynomial:

$$f(x) = c_0 x^0 + c_1 x^1 + c_2 x^2 + \dots + c_n x^n$$

How can I find the polynomial, modulo a prime number $p$? In other words, I want to take all of the coefficients modulo $p$, and all of the powers modulo $p-1$. So, for instance, the result modulo 3 would be:

$$(c_0 \bmod 3)x^0+$$ $$(c_1 \bmod 3)x^1+$$ $$(c_2 \bmod 3)x^0+$$ $$(c_3 \bmod 3)x^1+$$ $$(c_4 \bmod 3)x^0+$$ $$(c_5 \bmod 3)x^1+$$ $$\dots$$

Please note that this is just an example, and in general I want to find any polynomial modulo any prime $p$.

So, in general, I have something like:

 5 + 13x + 14x^2 + 7x^3 + 8x^4

I want to take all powers of $x$ modulo $p-1$, so I get:

 5 + 13x + 14 + 7x + 8

...which, in turn, equals, by simplifying:

 27 + 20x

Then, taking all coefficients modulo 3, we get:

 0 + 2x

How can I code this?

  • $\begingroup$ Is this Question about the Software Mathematica? If so please complement your Question with Code. Else Mathematics satisfies your needs better. $\endgroup$ – user9660 Feb 12 '16 at 17:48
  • $\begingroup$ @Louis: This question is about code, although the right mathematics could make a difference, too. I've added code to show an example of what I'm after. $\endgroup$ – Matt Groff Feb 12 '16 at 17:53
  • $\begingroup$ matt, please fix your example and/or clarify why you accepted an answer that gives a different result. $\endgroup$ – george2079 Feb 12 '16 at 19:15

Given an equation

    eqn = 5 + 13 x + 14 x^2 + 7 x^3 + 8 x^4

We can simply apply a rule to all integers, replacing them the new Mod value. As follows:

    eqn /. x_ /; IntegerQ[x] :> Mod[x, 3]

Which gives:

    3 + 3 x + 2 x^2

The example you give in your question doesn't seem to tally with what you initially describe as your goal?

If you only want to apply the Mod to the exponents, then:

   eqn /. Power[x_, y_] :> Power[x, Mod[y, 3]]

Which gives:

    12 + 21 x + 14 x^2
  • $\begingroup$ Note the x I've used in my rule has nothing to do with the x in the equation! That was a poor choice of symbol on my part! $\endgroup$ – Quantum_Oli Feb 12 '16 at 18:12
  • $\begingroup$ This works, because I want to take the powers mod $p-1$, which you've done in the second part, followed by the coefficients (including the constant) modulo $p$. Thanks! $\endgroup$ – Matt Groff Feb 12 '16 at 18:58

Should be something like this:

poly = 5 + 13 x + 14 x^2 + 7 x^3 + 8 x^4;
p = 3;
Total@MapIndexed[# x^Mod[First@#2 - 1, p - 1] &, 
  Mod[#, p] & /@ CoefficientList[poly, x]]

6 + 2 x

(I don't follow your example though.. maybe I missed something )


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.