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$.

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. :)
