How to use Euclidian Algorithm to find multiplicative inverse of a polynomial??

Printable View

December 11th 2009, 08:31 PM
elninio

How to use Euclidian Algorithm to find multiplicative inverse of a polynomial??

For example, finding the multiplicative inverse of $[x] in Z_5[x]/<x^2+x+1>$

or even something like

$[a+bx] in R[x]/<x^2+1>$

I cant seem to figure out this concept.

Thank you!
December 11th 2009, 11:49 PM
tonio

Quote:

Originally Posted by elninio

For example, finding the multiplicative inverse of $[x] in Z_5[x]/<x^2+x+1>$

or even something like

$[a+bx] in R[x]/<x^2+1>$

I cant seem to figure out this concept.

Thank you!

Divide $x^2+1$ by $bx+a$ with residue:

$x^2+1=(bx+a)(dx+c)+r$ , with $r=0\,\,\,or\,\,\,\deg(r)<1\Longrightarrow r\in\mathbb{R}\setminus{0}$ .

As $x^2+1$ has no real roots, it can't be $r=0\Longrightarrow 0\ne r\in\mathbb{R}$ , and thus $(bx+a)\left(\frac{d}{r}x+\frac{c}{r}\right)=1\!\!\ !\pmod{x^2+1}\Longrightarrow (bx+a)^{-1}=\frac{d}{r}x+\frac{c}{r}\,\,\,in\,\,\,\mathbb{R }[x]\slash<x^2+1>$

Tonio
December 12th 2009, 01:48 AM
Shanks

Tonio, I think, the inverse of bx+a should be -(dx+c)/r.
December 12th 2009, 07:26 AM
tonio

Quote:

Originally Posted by Shanks

Tonio, I think, the inverse of bx+a should be -(dx+c)/r.

Yes, of course: forgot the sign. Thanx

Tonio
March 4th 2010, 12:09 PM
Krahl

Can we not write it in terms of a and b like

$(bx+a)^{-1}=\frac{a}{a^2+b^2}-\frac{b}{a^2+b^2}x$ ?