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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.