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?
 A: 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.
A: I immediately spotted one problem that you have. You have confused the notions of a polynomial and that of a polynomial function. Consequently your claim that $x^n=x$ for all positive integers $n$ is simply false.
A (univariate) polynomial over a field $F$ is simply a formal sum $\sum_{i=0}^na_ix^i$ with $i$ ranging over a finite set of non-negative integers, and $a_i$ are elements of $F$ for all $i$. Two polynomials $\sum_ia_ix^i$ and $\sum_ib_ix^i$ are the same polynomial, if (this is the definition!!) $a_i=b_i$ for all $i$. The set of polynomials over the field $F$ forms a ring $F[x]$ known as the ring of polynomials over $F$. This ring has many nice algebraic properties such as greatest common divisors and such.
A polynomial $p(x)\in F[x]$ gives rise to a polynomial function. This is a function $p$ from $F$ to itself gotten by evaluating $p$ at all the elements of $F$. In other words, $p:z\mapsto\sum_i a_i z^i$ for all $z\in F$. We sometimes do not make the distinction between polynomials and polynomial functions, but in the case of finite fields not making the distinction leads to problems.
So you have noticed that all the polynomials $p_n(x)=x^n$, with $n$ any positive integer, give rise to the same polynomial function $p_n$ from $\mathbb{Z}_2$ to itself. Your exercise, however, resides in the universe of polynomials - not in the universe of polynomial functions.
Polynomial functions from a field to itself also form a ring. But this ring is kind of ugly, in particular when $F$ is finite. For example, it has zero divisors and such. 
