<s>[INST] GgT, (polynomial) division and finite fields... Exercise: Let $f,g \in \mathbb{Z}_2[x]$ be the polynomials $f = x^6 + x^5 + x^4 + 1$ and $g = x^5 + x^4 + x^3 + 1$. Has the diophantic equation $f u + g u = x^4 + 1$ solutions $u,v \in \mathbb{Z}[x]$? If so, determine them all.
My Solution: First I observed that in $\mathbb{Z}_2$ the relations
\begin{align}
  -x & = x \\
   x + x & = 0 \\
   x^n = x
\end{align}
hold. From this the polynomials $f,g$ reduce to $f = g = x + 1$, so they are the same and so $ggT(f,g) = x + 1$. Now $x^4 + 1 = x + 1$, so $u = 0, v = 1$ is a special solution. To get all solutions, I add solutions of the homogenous part $fu + gv = 0$, i.e. $fu = gv$ with my relations. But because $f = g$, this forces $u = v$, so I could choose for $u$ and $v$ some arbitrary polynomial. So all solutions $(u,v)$ are of the form
\begin{align}
  u & = p \\
  v & = 1 + p
\end{align}
for some polynomial $p \in \mathbb Z_2$.
Reference Solution: First it has to be checked if $x^4 + 1$ is a multiple of
the ggT of $f$ and $g$, then the equation has a solution (criterium for lineare diophantic equations). The euclidean algorithms yields the ggT. It is $f = (x+1)g + x^4 + x^3 + x^2 + x = (x+1)g + r_1$, $g = xr_1 + x^2 + 1$ and $r_1 = (x^2 + x)(x^2 + 1)$. So $ggT(f,g) = x^2 + 1$, and because of $(x^2+1)^2 = x^4 + 1$ the diophantic equation has a solution.
The general solution is given by the sum of a special solution and the general solution of the homogenous part $fu + gv = 0$. The special solution could be obtained by the euclidean algorithm (Lemma of Bezout). With $1 = -1$ we got
$$
  x^2 + 1 = g + xr_1 = g + x(f + (x+1)g)) = xf + (x^2 + x + 1)g.
$$
One special solution for the representation of the ggT is therefore $(x, x^2 + x + 1)$, one special solution of the original equation $(x(x^2+1), (x^2+x+1)(x^2+1)) = (x^3 + x, x^4 + x^3 + x + 1)$.
For the homogenous part $fu = gv$ we divide by the ggT. It is $f = (x^4+1)(x^2+1)$ and $g = (x^3+x^2+1)(x^2+1)$, a solution $(u,v)$ thus has the property $x^2+x^2+1 | u$ and $x^4+1 | v$. Therefore $u = p \cdot (x^3 + x^2 + 1)$. Substitution yields $v = p\cdot (x^4 + 1)$ and furthermore every $u = p\cdot (x^3 + x^2 + 1)$ and $v = p\cdot (x^4 + 1)$ are solutions. Therefore $\{ (p\cdot (x^3+x^2+1), p\cdot (x^4+1)) : p \in \mathbb Z_2[x]\}$ is the solution set of the homogenous part. The solution set is therefore
$$
 \{ (x^3 + x + p\cdot (x^3 + x^2 + 1), x^4 + x^3 + x + 1 + p\cdot (x^4+1)) : p \in \mathbb Z_2[x] \}.
$$
Now I understand the reference solution, it is the standard way of solving the problem. But my solution seems much simpler to mean, so I wonder why they didn't consider it, or maybe my solution is just wrong? But then why should it be wrong?
 [/INST] You are taking polynomials, so it is incorrect to say that $x^n = x$ in $\Bbb{Z}_{2}[x]$. Actually you have that
$$
a_{0} + a_{1} x + \dots + a_{n} x^{n} 
=
b_{0} + b_{1} x + \dots + b_{n} x^{n} 
$$
for two elements of $\Bbb{Z}_{2}[x]$
if and only if $a_i = b_i$ for all $i$.
Most likely you are mixing up polynomials and polynomial functions.
</s>