GCD in F5

**Maccaman** · May 6th 2009, 03:12 AM

Calculate gcd $(2x^{5} + 2x^{4} + x^{3} + 3x^{2} + 1, -x^3 - x^2 + 2x + 2)$ in $\mathbb{F}_5x$

**NonCommAlg** · May 6th 2009, 05:35 AM

Originally Posted by Maccaman

Calculate gcd $(2x^{5} + 2x^{4} + x^{3} + 3x^{2} + 1, -x^3 - x^2 + 2x + 2)$ in $\mathbb{F}_5x$

do you know how Euclidean algorithm works? it's a general way to find the gcd of 2 polynomials. in your example you just need to remember that you're doing everything modulo 5.

so let $f(x)=2x^{5} + 2x^{4} + x^{3} + 3x^{2} + 1$ and $g(x)=-x^3 - x^2 + 2x + 2.$ use long division to get: $f(x)=(-2x^2)g(x) + 2x^2 + 1.$ here you can replace $-2x^2$ by $3x^2,$ if you like,

because 2 and -3 are equal modulo 5. next we use long division to divide $g(x)$ by $2x^2+1: \ g(x)=(2x+2)(2x^2 + 1).$ the remainder here is 0. so we're done and the gcd is $2x^2+1.$

Thread: GCD in F5

LinkBack

Thread Tools

Display

GCD in F5

Search Tags