# How do I find a polynomial in a field?

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?

• Is this Question about the Software Mathematica? If so please complement your Question with Code. Else Mathematics satisfies your needs better.
– user9660
Feb 12, 2016 at 17:48
• @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. Feb 12, 2016 at 17:53
• matt, please fix your example and/or clarify why you accepted an answer that gives a different result. Feb 12, 2016 at 19:15

## 2 Answers

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

• 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! Feb 12, 2016 at 18:12
• 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! Feb 12, 2016 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 )