Let $z$ be a complex number, s.t. $z^2-z+1=0$. Find $z^5 + z$. 
Let $z$ be a complex number, s.t. $z^2-z+1=0$.
Find $z^5 + z$.

As $z= z^2+1$, so $z\neq 0$, also $z^2\neq 0$, as $z\neq 1$.
Anyway, we can divide $z^2-z+1=0$ by $z$ to get:
$z+\frac1z-1=0$
We need to derive $z^5 + z$ in terms of $z+\frac1z$, so on division get the quotient.
$$
\require{enclose}
\begin{array}{rll}
    z^4 -z^2 +2 && \hbox{} \\[-3pt]
   z+\frac1z \enclose{longdiv}{z^5 + z}\kern-.2ex \\[-3pt]
      \underline{z^5+ z^3} && \hbox{} \\[-3pt]
      -z^3 +z && \hbox{} \\[-3pt]
      \underline{-z^3-z} && \hbox{} \\[-3pt]
      2z && \hbox{} \\[-3pt]
      \underline{2z+\frac2z} && \hbox{} \\[-3pt]
      -\frac2z
  \end{array}
$$
So, $z^5 + z= (z+\frac1z)(z^4 -z^2 +2)-\frac2z$
Seems it needs to further find division of $(z^4 -z^2 +2)$ too by $z+\frac1z$. Still remainders at each step (like, $\frac2z$) will be a further issue.
Alternatively (second approach), multiply by $(z+1)$ to get: $(z+1)(z^2-z+1)= z^3 +1=0\implies z^3=1$
$z(z^4+1)= z((z^2+1)(z^2 -1)+2)$
This approach fails too as remainder $2$ is obtained.
Next (third approach), $z+\frac1z=1\implies z^2 +\frac1{z^2}= -1$
This too fails to be useful in solving $z^5+z$.
Next (fourth approach)
, $z^2=z-1\implies z^4 = z^2-2z +1\implies z^4+1= z^2-2z +2\implies z(z^4+1)= z^3-2z^2 +2z$.
Can use value of $z^3=1$, to get:
$z^3-2z^2 +2z\implies 1-2z^2+2z\implies 1-2(z^2 -z) = 3$.
Seems the least intuitive approach works only.
Alternatively (fifth approach) to have a working intuitive approach, use the trigonometric /polar form approach:
the roots of $z^2-z+1$ are: $z=\frac12 \pm \frac{\sqrt3}{2}i$, with two roots $z_1, z_2$.
$e^{i x} = \cos(x) + i \sin(x)$
$z_1 = \frac12 + \frac{\sqrt3}{2}i = e^{ i\pi/3}$
$z_2 = \frac12 - \frac{\sqrt3}{2}i = e^{- i\pi/3}$
\begin{align}
z_1^5 + z_1 &= e^{5 i\pi/3} + e^{i\pi/3} \\
&= (sin(-\pi/3)+\cos (\pi/3))+(sin(\pi/3)+\cos (\pi/3))
 = 2\cos (\pi/3)
 = 1
\end{align}
\begin{align}
z_2^5 + z_2 &= e^{-5 i\pi/3} + e^{-i\pi/3} \\
&= (sin(\pi/3)+\cos (\pi/3))+(sin(-\pi/3)+\cos (\pi/3))
 = 2\cos (\pi/3)
 = 1
\end{align}
Now, the answer differs from earlier of $3$.
 A: $z^2 - z + 1 = 0$ implies $$z^2 = z-1,$$ hence
$$\begin{align}
z^5 + z &= z((z^2)^2 + 1) \\
&= z((z-1)^2 + 1) \\
&= z(z^2 - 2z + 2) \\
&= z(z-1 - 2z + 2) \\
&= z(-z+1) \\
&= -z^2 + z \\
&= 1-z + z \\
&= 1.
\end{align}$$

All your other calculations either have errors or are essentially failing to simplify the expression.  The only one that is correct is your fifth approach.  The aim is to reduce the power of $z^5$, so the above method is how you would do it.
Multiplying $z^2 - z + 1$ by $z+1$ also works, which gives you $z^3 = -1$, thus
$$z + z^{-1} = 1$$ implies $$z^5 + z = z^3 (z^2 + z^{-2}) = -(z^2 + z^{-2}) = -(z + z^{-1})^2 + 2 = -1 + 2 = 1.$$
A: Your first four approaches fail because you either use $z^3+1=0\implies z^3=1$ which should actually be $z^3=-1$ or you divided by $z+\frac1z$ rather than $z+\frac1z-1$ - the divisor didn't vanish on putting the value, and so you have to deal with the quotient which essentially brought you back to the problem. Dividing by $z+\frac1z-1$ yields the correct answer, which btw is equivalent to the following approach.
You could directly divide $z^5+z$ by $z^2-z+1$ to get
$$z^5+z=(z^3+z^2-1)(z^2-z+1)+1$$
from where you get the correct answer as by the polar form (that approach was correct).
This division can also be simplified if you repeatedly apply $z^2=z-1$ to reduce powers, e.g. $$z^5+z=z^3(z-1)+z=z^4-z^3+z$$

Alternatively, notice that if $\omega$ is a (non-real) cube root of unity then $z=-\omega$ so $z^5+z=(-\omega)^5-\omega=-\omega^2-\omega=1$ as desired.
Hope this helps. :)
