# Find gcd

• May 4th 2013, 08:34 PM
kayabi5
Find gcd
How to find the gcd of f(x)=x2 - x-2 and g(x)= x3-7x+6 in F3[x]. Expressed as a linear combination of f,g.
• May 4th 2013, 09:22 PM
ibdutt
Re: Find gcd
factorize f(x) and g(x) .
the product of common factors will be the gcd.
• May 5th 2013, 03:13 AM
abualabed
Re: Find gcd
hello every one
• May 5th 2013, 06:18 PM
kayabi5
Re: Find gcd
Ok, but what throws me off is the F3[x]. I know its (0,1,2), but how to you apply it?
• May 6th 2013, 06:20 AM
HallsofIvy
Re: Find gcd
So we are dealing in modulo 3. The first thing I would do is simplify $x^3- 7x+ 6$: 7= 1 (mod 3) and 6= 0 (mod 3). So $x^3- 7x+ 6= x^2- x= x(x^2- 1)= x(x- 1)(x+ 1)$ which we could also write as x(x+2)(x+1). To factor $x^2- x- 2= x^2+ 2x+ 1 (mod 3)$, look at the general $(x+ a)(x+ b)= x^2+ (a+b)x+ ab$. We need to find a and b such that a+ b= 2 (mod 3) and ab= 1 (mod 3). a= b= 1 should be obvious.