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

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*}

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