Primitive element of $\mathbb{F}_{16}^{\times}$

Question

I have to find a primitive element of $\mathbb{F}_{16}^{\times}$. I defined $\mathbb{F}_{16} = \frac{\mathbb{F}_{2}[a]}{\langle a^4+a+1 \rangle}$.

I tried to prove that $a^3$ and $a^5 \neq 1$.

I got $a^3=a^3 \neq 1$ and $a^5 = a^2 + a \neq 1$.

But, when I try to check if $a^{15} = 1$, I get $a^{15} = a^3 + a^2 \neq 1$. I checked several times and can not get it, it may be something I am missing.

Are my calculations right?

How can I find the primitive element? Which is the primitive element?

Answer 1

in ${GF(2^4)}$ The polynomial ${1+x+x^4}$ has 8 primitive elements.

• Condition: ${x^i \in GF(2^r)}$ is primitive iff ${gcd(i, 2^{n}-1)=1)}$, Here, ${2^4-1=15}$ ,so we've possible candidates are ${\{1,2,4,7,8,11,13,14\}}$.
• you can check, an element ${\alpha \in GF(2^r)}$ is primitive iff ${\alpha ^m \ne 1}$ for ${1 \leq m < 2^r -1}$
• Let's take ${x^4=\alpha}$ then ${\alpha^2=x^8=1+x^2, \alpha^{14}=1+x^3,\alpha^{15}=x+x^4=x+1+x=1}$, so we don't have any exponent m less than 15 which gives 1. So, 4 is a primitive element.
• Now, lets check ${x^5=\alpha}$, now ${\alpha^2=1+x+x^2, \alpha^3= x^{15}=1}$, here m=3 (<15), hence 5 in not a primitive element.