Finding equivalent polynomials (mod n)

During some casual investigation of polynomials over an integer ring $$\mathbb{Z}_n$$ (or $$\mathbb{Z}/n\mathbb{Z}$$ if you prefer), I noticed that some polynomials induce the same map. I'm curious about how one could tell if two polynomials are equivalent in this way without checking directly.

For example, in $$\mathbb{Z}_8$$, $$f(x) = 2x^3 + 5x + 3$$ is the same as $$g(x)=x^4 + 3x^2 + 3x + 3$$. They are bijective and act on $$\mathbb{Z}_8$$ as the permutation $$(3, 2, 5, 0, 7, 6, 1, 4)$$.

My main question is: What are the criteria for two polynomials to induce the same map on $$\mathbb{Z}_n$$?

I'm also interested in other information about this, such as: For a given polynomial, are there infinitely many equivalent polynomials? Will the lowest-degree polynomial in an equivalence class always have a degree less than $$n$$? Does it matter what kind of number $$n$$ is (e.g. prime or composite)? Are there unique polynomials with $$deg\geq1$$ having no equivalent?

Without knowing much about this situation, my guess is that the Chinese Remainder Theorem, Euler's Theorem, and/or Fermat's Little Theorem will come into play. I'm exploring a bit outside of my mathematical comfort zone and I have very little experience with number theory, so this is where I get kind of lost.

• Euler, and Polynomial remainder theorem may be of use. – Roddy MacPhee Oct 9 at 14:57
• Try looking at $g-f$. This is a polynomial that is zero for any value of $x$. In this case it factorises very nicely as a product of four consecutive numbers - these will always have a multiple of 4 and another even number among them, so the product is 0 mod 8. For a prime modulus $p$, you have $x^p-x=0$ for all $x$, so you can add any multiple of this to a polynomial to get an equivalent one (and one of these will have degree less than $p$). I'm not sure what you'd need for composite moduli in general (at least not if it has to work even when $x$ and $n$ are not coprime). – Jaap Scherphuis Oct 9 at 15:36
• – lhf Oct 9 at 23:47

Two polynomials induce the same function iff their difference induces the zero function.

Here is a general result about polynomials that induce the zero function:

If $$r$$ is the maximum exponent in the prime factorization of $$n$$, then $$x \mapsto x^{r+\lambda (n)}-x^r$$ is the zero function mod $$n$$. [Wikipedia]

Here, $$\lambda$$ is the Carmichael function.

I don't know whether this is the polynomial of least degree that induces the zero function mod $$n$$.

• Can you expand on how this relates to polynomials with more terms and coefficients? If I'm not mistaken, $f-g$ from my example is $x^4+6x^3+3x+6x$ and the $\lambda$ version of the zero function is $x^5+7x^3$. – Era Oct 9 at 17:49
• @Era, you're quite right. So, in this case, $x^5+7x^3$ is not the polynomial of least degree that induces the zero function mod $8$. – lhf Oct 9 at 18:17
• The polynomial of least degree that induces the zero function mod $8$ is $4x^2+4x$. – lhf Oct 9 at 18:27
• The monic polynomial of least degree that induces the zero function mod $8$ is $x^4+2x^3+3x^2+2x$, which is your $f-g$, up to sign. – lhf Oct 9 at 18:34
• The quoted theorem is a special case of the theorem I prove here. and is also proved elsewhere here. – Bill Dubuque Oct 9 at 19:09

By Euler's totient function, $$x^{\varphi (n)\cdot y+k}\equiv x^k\bmod n$$

Meaning any univariate polynomial, with degree more than $$\varphi(n)$$ is redundant as the coefficients from higher terms is congruent to adding it to the coefficient of a lower degree term.

Furthermore, by polynomial remainder theorem, the values of the polynomial differing in input by $$n$$ are also congruent.

• Can you explain what you mean by "by Euler's totient function"? I know what the function is, but how does it produce this result? Is that a theorem? – Era Oct 9 at 16:54
• it's an extension of the normal use, just like my extension of Fermat, used to find the remainder of a 78 digit number on division by 7. – Roddy MacPhee Oct 9 at 16:56
• math.stackexchange.com/questions/3152587/… – Roddy MacPhee Oct 9 at 16:57
• You're making an obvious mistake (what if $n=4$ and $x=2$?). – metamorphy Oct 9 at 17:09
• then only the last 2 terms matter... – Roddy MacPhee Oct 9 at 17:26