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

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 ) • Did you recognize that$x^2+2x+1=(x+1)^2$? This means that$\gcd (a(x), x^2+2x+1)=1$if and only if$a(-1) \neq 0$. – Crostul Aug 9 at 14:06 • In equations one can produce$\operatorname{gcd}(f, g)$(in particular with$\operatorname{gcd}$in the Roman script usually used for operator names) with the$\LaTeX$$\operatorname{gcd}(f, g)$. – Travis Aug 9 at 14:14 • It might also help readers to know that what you're talking about is more usually denoted$GF(3)[x]/(x^2+2x+1)$or maybe even just$F_3[x]/(x^2+2x+1)\$. I would not have known what you were doing with the asterisk and subscript if the rest of your context had not made it clearer. – rschwieb Aug 9 at 14:21

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.