Given $n>0$ and modulus $m > 1$, Define $$L : \mathbb Z_m[x] \to \mathbb Z_m[x]$$ as $$L(p) = p(0) + p(1) x + p(2) x^2 \cdots + p(m-1)x^{m-1} \mod m$$ Where $p(i)$ is the image of the polynomial $p$ under the integer $i$.
It can be shown simply that $L$ will be of the form $p \mapsto Mp$, where the arithmetic is done modulo $m$, and $p$ is the vector containing the coefficients of the polynomial $p$. Further, $M^i_j=i^j \mod m$.
I conjecture that $L$ is an isomorphism if and only if $m$ is prime. What is the easiest way to prove this? Could we maybe take advantage of the nice formula of $M^i_j = i^j \mod p$ to construct an inverse - and then prove linear dependence for the composite case?
When $m$ is prime: one needs to restrict to polynomials of degree less than $m$ in the domain, since adding a multiple of $x^m-x$ to the input does not change the output (by Fermat's little theorem). With that proviso, the map is indeed an isomorphism: every polynomial of degree at most $m-1$ modulo the prime $m$ is uniquely determined by its values on the $m$ residue classes. (The uniqueness follows from unique factorization of polynomials modulo $m$; the existence can then be deduced by a counting argument.)
When $m$ is not prime, the uniqueness fails: there are polynomials of smaller degree that vanish on all inputs. The easiest example is if $m=pq$ is the product of two distinct primes; then $(x^p-x)(x^q-x)$ vanishes on all inputs but has degree strictly less than $m-1$.