Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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
1  
@DanielFischer Therefore the result is $x^7+1$ modulo 7 –  Jean-Francois Rossignol Sep 16 '13 at 13:54
show 5 more comments

4 Answers 4

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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