0
$\begingroup$

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 )

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Crostul Aug 9 at 14:06
  • $\begingroup$ 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)$. $\endgroup$ – Travis Aug 9 at 14:14
  • $\begingroup$ 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. $\endgroup$ – rschwieb Aug 9 at 14:21
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.