How to evaluate $x^6+x^4+x^3+x^2+1=0$? There is a hint in the question, use the factorization of $x^5+x+1$.

How about first multiplying by $(x-1)$ ?
$$(x-1)(x^6+x^4+x^3+x^2+1)= x^7-x^6+x^5 - x^2+x-1= (x^2-x+1)(x^5-1)$$ 
and carry on from there? 
Added: Not sure if worth mentioning, but doing the same on $x^5+x+1$ requires an extra little trick:
$$ (x-1)(x^5+x+1)= x^6-x^5 (+x^3 - x^3) +x^2-1=(x^3-x^2+1)(x^3-1)$$
