Finding equivalent polynomials (mod n)

Question

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.

Answer 1

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$.

Answer 2

As proved in another answer, two polynomials $f$ and $g$ induce the same function on $\mathbb{Z}/n\mathbb{Z}$ precisely when, written in the form $$f(x) = \sum_{k} b_k x^{\underline k}$$ and $$g(x) = \sum_{k} c_k x^{\underline k},$$ they satisfy the property that $$b_k \equiv c_k \mod {\frac{n}{\gcd(n, k!)}}$$ for each $k$.

Here, $x^{\underline k}$ is the "falling factorial": $x^{\underline k} = x(x-1)\cdots(x-k+1)$. Any polynomial can be written in this form (i.e. using the "falling factorial basis" instead of the monomial basis) using the identity $x^n = \sum_k {n \brace k} x^{\underline k}$ where ${n \brace k}$ is a Stirling subset number ("Stirling number of the second kind"). See Wikipedia on Stirling numbers, for example.