Prove that $\varphi$ is a surjective ring homomorphism.

Question

Let $n\in \mathbb{Z_+}$ with $n>1$, and let $\varphi : \mathbb{Z[x]} \to \mathbb{Z_n[x]}$ be given by $\varphi : a_0+a_1x+a_2x^2+ … +a_mx^m \to [a_0]_n+[a_1]_nx+[a_2]_nx^2+ … +[a_m]_nx^m$. Prove that $\varphi$ is a surjective ring homomorphism.

I understand that I am to show it is surjective and satisfies the addition and multiplication characteristics of a homomorphism. The thing that is causing me the most trouble is showing surjectivity and that for the multiplication part of homomorphism, I am to use the summation notation definition (see below), which is causing a bit of confusion for me.
\begin{align*}
f(x)\cdot g(x) &= \sum_{k=0}^{n} (\sum_{j=0}^{k} a_kb_{k-j}) x^k \\
\end{align*}
There is also a hint that \begin{align*}
[\sum_{j=0}^{k} r_j\cdot s_j]_n = \sum_{j=0}^{k}[r_j]_n\odot [s_j]_n \\
\end{align*}

Answer 1

To get a sense of how the polynomial $f(x)g(x)$ looks like for general $f$ and $g$, try first with $f$ and $g$ of low degree. If they're both of degree 1, then

$$(a_0+a_1x)(b_0+b_1x)=a_0b_0+(a_1b_0+a_0b_1)x+a_1b_1x^2$$ It is easy to see why $\varphi$ is a homomorphism on this specific example.

When $f$ and $g$ are both of degree 2, then $$(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2)=\\a_0b_0+(a_1b_0+a_0b_1)x+(a_2b_0+a_1b_1+a_0b_2)x^2+(a_1b_2+a_2b_1)x^3+a_2b_2 x^4.$$ The thing to notice here is that the coefficient next to $x^k$ is a sum consisting of $a_ib_j$ such that $i+j=k$. Therefore, if $f$ and $g$ are of the same degree $n$, then $$f(x)g(x)=\sum_{k=0}^n\left(\sum_{i+j=k}a_ib_j\right) x^k.$$ This is the same sum as the one in your post under an appropriate substitution of indices.

If $f$ and $g$ are not of the same degree, e.g. $m=\deg g < \deg f=n$, we can pretend that they have the same degree by adding to $g$ the terms $b_{m+1}x^{m+1},\dots,b_{n}x^n$ with $b_{m+1}=\cdots=b_n=0.$

Now, since $\varphi$ acts by mapping a coefficient $a$ to $[a]$, and $[]$ passes through sums and products (i.e. $[a+b]=[a]+[b]$ and $[ab]=[a][b]$), we get (spoilers below)

$$\varphi(f(x)g(x))=\varphi(\sum_{k=0}^n\left(\sum_{i+j=k}a_ib_j\right) x^k)=\sum_{k=0}^n\varphi\left(\sum_{i+j=k}a_ib_j\right) x^k=\sum_{k=0}^n\left[\left(\sum_{i+j=k}a_ib_j\right)\right] x^k=\sum_{k=0}^n\left(\sum_{i+j=k}[a_ib_j]\right) x^k=\sum_{k=0}^n\left(\sum_{i+j=k}[a_i][b_j]\right) x^k$$ The right hand side is now clearly $\varphi(f(x))\varphi(g(x))$.

For surjectivity, take an explicit polynomial in the codomain of $\varphi$, e.g. for $n=5$ that might be $$[11]_5 + [23]_5x+[30]_5x^2+[4]_5x^7.$$ You can immediately see that $\varphi$ maps the polynomial $11+23x+30x^2+4x^7$ (as well as many others) to the one we've chosen. Now generalize this for an arbitrary choice of $n>1$.