Calculations on $GF(16)$ find $0111/1111$

Question

It's my first time doing finite field arithmetics. As an exercise, I want to find $0111/1111 \in GF(16)$ generated by $\Pi(\alpha)=1+\alpha +\alpha^4$ that is an irreducible polynomial.

In polynomial form we have:

• $0111 \rightarrow \alpha+\alpha^2+\alpha^3$
• $1111 \rightarrow 1+\alpha+\alpha^2+\alpha^3$

If I perform the polynomial division, I obtain $-1$ (that is the same result obtained writing $0111 \equiv -1 \pmod {1111}$).

How can I compute this result $-1$ in the right element of the field? Or perhaps this some kind of sign that the result $\not \in GF(16)$?

Answer 1

As it happens, the discrete logarithm table for $GF(16)$ that I prepared for referrals like this, uses the same minimal polynomial of the primitive element. The only difference is that in the linked thread I denote by $\gamma$ the element that you refer to as $\alpha$.

Anyway, consulting that table, we see that $$1111=1+\alpha+\alpha^2+\alpha^3=\alpha^{12},$$ and $$ 0111=\alpha+\alpha^2+\alpha^3=\alpha^{11}. $$ Therefore $$ \begin{aligned} \frac{0111}{1111}&=\frac{\alpha^{11}}{\alpha^{12}}=\frac{\alpha^{11}}{\alpha^{12}}\cdot\frac{\alpha^3}{\alpha^3}\\ &=\frac{\alpha^{14}}{\alpha^{15}}=\frac{\alpha^{14}}1\\ &=\alpha^{14}=\alpha^3+1=1001. \end{aligned} $$

Answer 2

$GF(16)$ has characteristic 2. That is, each coefficient of $\alpha$ is either $0$ or $1$. And $-1=1$.

However, the polynomial division does not just result in $-1$ or $1$. Instead we have: $$\frac{\alpha^3+\alpha^2+\alpha}{\alpha^3+\alpha^2+\alpha+1} = 1 + \frac{1}{\alpha^3+\alpha^2+\alpha+1} $$

As an alternative to the answers in the comments, we can write each element (except $0$) as a power of $\alpha$. After all, $GF(16)$ has a cyclic multiplicative group and $\alpha^{15}=1$.

Over the polynomial $X^4+X+1$ we have $0111 = \alpha^{11}$ and $1111=\alpha^{12}$. Therefore: $$0111/1111=\alpha^{11}/\alpha^{12}=\alpha^{11+15-12}=\alpha^{14}=1001$$

This is consistent with your result: $$1 + \frac{1}{\alpha^3+\alpha^2+\alpha+1}=1+\frac{1}{\alpha^{12}} =1+\frac{\alpha^{15}}{\alpha^{12}}=1+\alpha^3 $$