Re: GCD in Z[x]_5
From: LD (spam_at_go.home)
Date: 12/15/04
- Next message: hyazan_at_provide.net: "Re: Velocity problem"
- Previous message: B Loggins: "Re: Arithmetic question"
- In reply to: Mkajuma: "GCD in Z[x]_5"
- Next in thread: Marcel Martin: "Re: GCD in Z[x]_5"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 15 Dec 2004 20:34:10 +0100
Mkajuma wrote:
> Hi,
> I need to find the gcd of f(x) = x^5 +3x^3 +x^2 +2x+ 2 and g(x) = x^4+
> 3x^3 +3x^2 +x +2 in Z[x]_5 and express it in the form a(x)f(x) + b(x)g(x)
> for some a(x), b(x) in Z[x]_5.
One way to do this is to first determine the gcd via Euclid's algorithm:
f=g*q_1+r_1
g=r_1*q_2+r_2
r_1=r_2*q_3+r_3
...
Stop when you get r_k=0; then gcd(f,g)=r_(k-1) (can you see why?).
Now rewrite the bottom line as r_(k-1)=r_(k-3)-r_(k-2)*q_(k-1), and
substitute r_(k-2) with its value given by the previous line, then r_(k-3)
from the line before, etc., working all the way up to the top line. If you
look at it right, you should see your answer!
Computationally speaking, it looks cumbersome, but I don't think solving for
the coefficients of a and b would be any less so.
LD
- Next message: hyazan_at_provide.net: "Re: Velocity problem"
- Previous message: B Loggins: "Re: Arithmetic question"
- In reply to: Mkajuma: "GCD in Z[x]_5"
- Next in thread: Marcel Martin: "Re: GCD in Z[x]_5"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
