Questions about the algebra $A = GF(3)[x]^*_{x^2+2x+1}$

Question

Consider the algebra $A = GF(3)[x]^*_{x^2+2x+1}$. I want to systematically determine all elements of this set. I know that $GF(3) = \{0,1,2\}$ and $GF(3)[x]_{x^2+2x+1} = \{a(x) \in GF(3)[x]: deg(a(x)) < deg(x^2+2x+1) \} = \{1,2,x,2x,x+1,x+2,2x+1,2x+2\}$

And $GF(3)[x]^*_{x^2+2x+1} = \{a(x) \in GF(3)[x]_{x^2+2x+1} : gcd(a(x),x^2+2x+1) = 1 \}$. But i don't know how to decide $gcd(a(x),x^2+2x+1) = 1$ efficiently ?

I am also interested in how I can efficiently find a generator in $A$ and for example the inverse of $x+2$ in A ( i think the inverse is $2x - but i have found it with try and error and have no idea how to do it systematically )

Answer 1

Hint We have $\operatorname{gcd}(f, g) = 1$ iff $f$ and $g$ have no common factors. In our case, factoring gives $x^2 + 2 x + 1 = (x + 1)^2$.

So, $\operatorname{gcd}(a(x), x^2 + 2 x + 1) = 1$ iff $a(x)$ is not divisible by $x + 1$. Thus, we can test whether any polynomial $a(x)$ is divisible by $x + 1$ by checking whether $a(-1) = 0$. Alternatively, the noninvertible elements of $a(x) \in \operatorname{GF}(3)[x]_{x^2 + 2 x + 1}$ are precisely those of the form $(x + 1) b(x)$, and we can compute these directly.