2
$\begingroup$

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?

$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 at 19:15

2 Answers 2

3
$\begingroup$

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
$\endgroup$
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$ Feb 12, 2016 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, 2016 at 18:58
3
$\begingroup$

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 )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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