6
$\begingroup$

How do you reduce polynomials that are mod m?

For example if I have 10x + 5 (mod 3) can I just reduce that to x + 2 (mod 3)?

  • 1
    Correct. Do remember that you are not allowed to reduce the exponents, though. The exponents are usual integers, but the coefficients of the polynomial are treated as residue classes modulo your favorit modulus.2011-07-11

2 Answers 2

6

Yes, you are correct. Reducing polynomials mod $m$ means that you reduce all coefficients mod $m$ (of course, I am assuming that the coefficients are integers). Your example is correct too.

7

If $\rm\ m\in \mathbb Z\ $ then $\rm\ f\:\equiv\: g\ \ (mod\ m\: \mathbb Z[x])\:$ means $\rm\:f-g\:\in\: m\:\mathbb Z[x]\:,\:$ i.e. $\rm\:m\ |\ f-g\ $ in $\rm\:\mathbb Z[x]\:.\:$ This is equivalent to saying that $\rm\:m\ |\ f_{\:i} - g_{\:i}\:,\:$ i.e. the polynomials have equivalent coefficients $\rm\:(mod\ m)\:.$

Said structurally $\rm\ \mathbb Z[x]/m\:\mathbb Z[x]\ \cong \mathbb (\mathbb Z/m\mathbb Z)[x]\:.$