Modular Polynomial Arithmetic

I have came across this modular polynomial arithmetic question. I not really understand how the answers were derived.

For the first example right, from what I understand it is the polynomial whose coefficient are from Z_p, {0,1,...,p-1}. So given p = 3, I can get 0,1,2. And if given p = 2, I can get 0,1.

But I not sure how those x are derived. Any ideas? Thanks in advance.

2 Answers

It seems to be the list of all polynomials of degree less than $2$, with coefficients in $\mathbf Z/3\mathbf Z$ in the first case; of all polynomials of degree less than $3$, with coefficients in $\mathbf Z/2\mathbf Z$ in the second case.

Indeed, for the first case, a polynomial of degree less than $2$ has the form $a_0+a_1x$. Plug in the different possible values for the pairs $(a_0,a_1)$, getting \begin{matrix} (0,0)\to \color{red}{0}&(0,1)\to \color{red}{x}&(0,2)\to \color{red}{2x}\\ (1,0)\to \color{red}{1}&(1,1)\to \color{red}{1+x}&(1,2)\to \color{red}{1+2x}\\ (2,0)\to \color{red}{2}&(2,1)\to \color{red}{2+x}&(2,2)\to \color{red}{2+2x} \end{matrix} The second case goe along the same lines: \begin{matrix} &(0,0,1)&&(0,1,1)\\ &\color{red}{x^2} &&\color{red}{x+x^2}\\ (0,0,0)&&(0,1,0) \\ \color{red}{0}&&\color{red}{x}\\[2ex] &(1,0,1)&&(1,1,1)\\ & \color{red}{1+x}&&\color{red}{1+x+x^2}\\ (1,0,0)&&(1,1,0)\\ \color{red}{1}&& \color{red}{1+x} \end{matrix}

• Sorry do you mind to explain a little more on that? The textbook does not provide enough explanation though. – hyperfkcb Jan 28 '17 at 13:13
• @Denise Tan: I've added details. Is it clearer? – Bernard Jan 28 '17 at 13:31
• Thanks so much, it is so much clearer now. However, as for the second case which the degree is less than 3, does that means the formula is a0 + a1 + a2x? I tried to do it the same way as above but the results seemed off track :( – hyperfkcb Jan 28 '17 at 13:52
• More exactly $a_0+a_1x+a_2x^2$, with coefficients equal to $0$ or $1$. You have to write out methodically all the possibilities, to be sure you don't forget some possibility. – Bernard Jan 28 '17 at 13:56
• I see I see but if that is the case, then it should not be 3x3 matrix anymore, am I right? It should be larger than that. – hyperfkcb Jan 28 '17 at 14:05

If n=2, the polynomial has 2 terms, the x and constant term. If x=3, the polynomial has three terms, $x^2$, $x$, and the constant term. So the highest degree of the polynomial is $n-1$.

• Sorry but I don't quite get it. Is there any way to multiply or division or anything to derive those x + 1, x + 2, 2x etc? – hyperfkcb Jan 28 '17 at 9:35
• Any ideas? I still can't figure it out :( – hyperfkcb Jan 28 '17 at 9:49