Polynomials and Calculating via mod7

[silvermane]

Homework Statement

Working in (Z/7Z)[x], compute the greatest common divisor of the polynomials (X^2 - 3X + 2) and (X+6).

The Attempt at a Solution

I need help understanding how to compute this. It would be greatly appreciated if someone gave me an example with different modulus and polynomials if at all possible.

Background: I'm in a class with a teacher who, well, talks to the board when he teaches. It's getting pretty bad (not to rant) and nothing he does gets through to the students. I'm thinking this is a fairly simple process too, so if anyone can help me with this, you're my hero! :)

 

[micromass]

You use the Euclidean algorithm.

Would it help you if I calculate the gcd of two numbers? The principle is thesame, just replace numbers with polynomials

Take 12 and 18. Perform long division on 18 and 12 to obtain that

18=1.(12)+6

So the remainder is 6. Now perform long division on 12 and 6 to obtain

12=2.6+0

The remainder is 0, so the algorithm stopts. The last non-zero remainder is the gcd: 6 in this case.




Let's do some polynomials in \mathbb{R}[x] this time: take x³+3x and x²+x (they always have to be monic, otherwise gcd is not unique). First perform long division to obtain

x³+3x=x(x²+x)+(-x²+3x)

The first remainder is -x²+3x. Now we perform long division on x²+x and -x²+3x to obtain

x²+x=(-1)(-x²+3x)+4x

The second remainder is 4x. Now we perform long division on 4x to obtain

x²+x=(x/4)(4x)+x

The third remainder is x. Now we perform long division on 4x and x to obtain

4x=4x+0

The fourth remainder is 0, so the algorithm stops. The last non-zero remainder was x and is the gcd.

 

[silvermane]

I'm okay with doing the Euclidean algorithm, (though what you showed me was a wonderful refresher!) but I'm having trouble with the Z/7Z aspect of it. Where would that come into play?

 

[silvermane]

So, using the Euclidean Algorithm, I obtained 56 as the gcd of (x^2 - 3x + 2) and (x+6).
56 is congruent to 0mod7, so would 0mod7 just be my answer?

 

[micromass]

No, 56=0 is already to late. You'll need the first non-zero polynomial to be the gcd.

Correct me if I'm wrong:

x²-3x+2=x(x+6)+(-2x+2)

This remainder is nonzero, so we continue (note that 1/2 = 4)

x+6= (-4)(-2x+2)+0

This remainder is zero, so the last non-zero remainder is the gcd.

Thus gcd(x²-3x+2,x+6)=-2x+2.

If you want the gcd to be monic (this is usual), then you will want to divide by -1 and obtain:

gcd(x²-3x+2,x+6)=x-1.

 

[Tedjn]

This seems to be right. Observe that x-1 = x+6 (mod 7).

 

[Hurkyl]

I'm having trouble with the Z/7Z aspect of it. Where would that come into play?

It doesn't come into play in the Euclidean algorithm. It doesn't care what arithmetic is, just that it satisfies the property of a Euclidean domain.

The fact you're working in the polynomial ring over Z/7Z is only relevant to actually computing the results of arithmetic operations like division with remainder, subtraction, or testing for equality.

 

[silvermane]

No, 56=0 is already to late. You'll need the first non-zero polynomial to be the gcd.

Correct me if I'm wrong:

x²-3x+2=x(x+6)+(-2x+2)

This remainder is nonzero, so we continue (note that 1/2 = 4)

x+6= (-4)(-2x+2)+0

This remainder is zero, so the last non-zero remainder is the gcd.

Thus gcd(x²-3x+2,x+6)=-2x+2.

If you want the gcd to be monic (this is usual), then you will want to divide by -1 and obtain:

gcd(x²-3x+2,x+6)=x-1.

Yeah that's correct! I did my Euclidean Algorithm via matrices, and row reduced incorrectly, thus the 56! Thanks everyone for your extensive help! :)