# Product polynomial in $\mathbb{F}_7$

I need to compute the product polynomial $$(x^3+3x^2+3x+1)(x^4+4x^3+6x^2+4x+1)$$

when the coefficients are regarded as elements of the field $\mathbb{F}_7$.

I just want someone to explain to me what does it mean when a cofficient (let us take 3 for example) is in $\mathbb{F}_7$ ? I know that $\mathbb{F}_7= \mathbb{Z}/7\mathbb{Z}$

-
It means that when you compute e.g. $3\cdot 4$, you reduce the result modulo $7$, so you get $12 - 7 = 5$. Of course there's a short-cut here. –  Daniel Fischer Sep 16 '13 at 13:45
And by "short-cut" @DanielFischer is referring to (HINT) the factorization of the polynomials you are multiplying together. Find out what the factors are, and you will certainly have a much easier time multiplying them together. –  abiessu Sep 16 '13 at 13:46
@DanielFischer What happens in the cases 1 and 21 ? –  Jean-Francois Rossignol Sep 16 '13 at 13:47
Well, modulo $7$, we have $21 = 0$. –  Daniel Fischer Sep 16 '13 at 13:50
@DanielFischer Therefore the result is $x^7+1$ modulo 7 –  Jean-Francois Rossignol Sep 16 '13 at 13:54

Hint: Use Binomial Theorem to factor the two polynomials. What do you know about $(a+b)^p$ when $a,b\in\Bbb F_p$? If the answer to that question is "I'm not sure," don't worry: you can just use Binomial Theorem again to expand the product, and remember that integer multiples of $7$ are equal to $0$ modulo $7$.

-

We use $3$ as shorthand for the coset $$7\mathbb{Z}+3=\{\ldots,-11,-4,3,10,17,\ldots\}$$ in $\mathbb{Z}/7\mathbb{Z}$. Since $$\cdots=7\mathbb{Z}-11=7\mathbb{Z}-4=7\mathbb{Z}+3=3\mathbb{Z}+10=3\mathbb{Z}+17=\cdots,$$ when working in $\mathbb{Z}/7\mathbb{Z}$, we have $$\cdots=-11=-4=3=10=17=\cdots.$$

Practically, this means if $k$ arises as a coefficient, we can replace $k$ with $k \text{ mod } 7$.

-

Well, you can multiply two polynomials in the usual way first, then you look at the coefficients and reduce them to modulo 7. For example: $(3x^2+x+1)(x^2+3x+6) = 3x^2(x^2+3x+6)+x(x^2+3x+6)+1.(x^2+3x+6)=(3x^4+9x^3+18x^2)+(x^3+3x^2+6x)+(x^2+3x+6)=3x^4+10x^3+22x^2+9x+6$ which is the same as $3x^4+3x^3+x^2+2x-1$ in $\mathbb{Z}_7$ because $10 \equiv 3 \pmod{7}$, $22 \equiv 1 \pmod{7}$, $9 \equiv 2 \pmod{7}$ and $6 \equiv -1 \pmod{7}$.

-

As others have mentioned, an integer $n$ in $\mathbb{Z}_p\equiv{n\mod p}$. So coefficients can only be in the set $\{0,1,2,...,p-2, p-1\}$ Thus, you can knock out terms with coefficients of the form $pn$. In your case multiples of $7\equiv{0\mod7}$.

I will add a little more of a hint to cameron's

$(a+b)^p={p\choose0}a^p+{p\choose 1}a^{p-1}b+{p\choose 2}a^{p-2}b^2+...+{p\choose p-1}ab^{p-1}+{p\choose p}b^p$

$=\frac{p!}{p!0!}a^p+\frac{p!}{(p-1)!1!}a^{p-1}b+\frac{p!}{(p-2)!2!}a^{p-2}b^2+...+\frac{p!}{1!(p-1)!}ab^{p-1}+\frac{p!}{0!p!}b^p$

$=1a^p+pa^{p-1}b+\frac{p(p-1)}{2}a^{p-2}b^2+...+pab^{p-1}+1b^p$

$=a^p+0a^{p-1}b+0a^{p-2}b^2+...+0ab^{p-1}+b^p$

$=a^p+b^p$

-
you didn't answer his question, you just explained that $(a+b)^p=a^p+b^p$ in $\mathbb{Z}_p$ –  Irish M Powers Sep 16 '13 at 14:46
you're right. I'll amend –  Eleven-Eleven Sep 16 '13 at 14:48