We give an extremely detailed argument. Sorry about the length!
Suppose first that $p\equiv 1\pmod{6}$. So $p=6k+1$ for some $k$.
We will use a primitive root argument. Let $g$ be a primitive root of $p$. In group-theoretic terms, let $g$ be a generator of the multiplicative group modulo $p$.
Then $g$ has order $p-1$ modulo $p$. Note that $g^{p-1}=(g^{2k})^3\equiv 1\pmod{p}$ by Fermat's Theorem. Also, $(g^{4k})^3\equiv 1\pmod{p}$. Neither $g^{2k}$ nor $g^{4k}$ is congruent to $1$ modulo $p$, since the order of $g$ is $6k$. And they are not congruent to each other.
Thus the congruence $z^3\equiv 1\pmod{p}$ has at least $3$ (and therefore exactly $3$ solutions, namely $1$, $g^{2k}$, and $g^{4k}$.
So if $b^3\equiv a\pmod{p}$, then we also have $(g^{2k}b)^3\equiv a\pmod{p}$ and $(g^{4k}b)^3\equiv a\pmod{p}$. It follows that the congruence $x^3\equiv a \pmod{p}$ has $3$ solutions if it has a solution.
Now suppose that $p\equiv 5\pmod{6}$. Let $p=6k+5$. Let $x$ and $y$ be non-zero integers, and suppose that $x^3\equiv y^3\pmod{p}$. This is the case if and only if $(xy^{-1})^3\equiv 1\pmod{p}$. We show that this forces $x\equiv y\pmod{p}$.
To do this, it is enough to show that the congruence $z^3\equiv 1\pmod{p}$ has only the obvious solution $z\equiv 1\pmod{p}$.
Again let $g$ be a primitive root of $p$. Any $z$ is congruent to $g^m$ for some $m$ with $1\le m\le p-1$. Ig $z^3\equiv 1\pmod{p}$ then $g^{3m}\equiv 1\pmod{p}$. It follows that $3m$ divides the order of $g$, that is, $3m$ divides $6k+4$. Since $3$ and $6k+4$ are relatively prime, it follows that $m$ divides $6k+4=p-1$. Thus $g^m\equiv 1\pmod p$, and therefore $z\equiv 1\pmod{p}$.
Now consider the mapping $\psi$ that takes any number $x$ between $1$ and $p-1$ into the remainder when $x^3$ is divided by $p$. By the calculation above, the function is one to one (injective). A one to one function from a finite set to itself must be onto (surjective). It follows that every number between $1$ and $p-1$ is $\psi(x)$ for some $x$. This says that every number between $1$ and $p-1$ is congruent to $1$ modulo $p$. That is what we wanted to prove.
Best Answer
Problem 1. We are facing the situation $n^4 \equiv -1$ (mod $p$) which implies $n^8 \equiv 1$ (mod $p$).
The order of $n$ modulo $p$ (that I denote as $\operatorname{ord}_p(n)$) is a divisor of $8$ namely $\operatorname{ord}_p(n) \in \{\, 1,2,4,8 \, \}$. However $(a^1)^4 = (a^2)^2 = a^4 \not\equiv 1$ (mod $p$) so it forces $\operatorname{ord}_p(n) = 8$. Then you are well aware that $8 \mid \phi(p)=p-1$ implies $p=8k+1,\ k \in \mathbb{Z}$.
Problem 2. We are facing the situation $n^2+n+1 \equiv 0 $ (mod $p$). Yet let's look at an apparently "weaker" problem by introducing an additional factor $(n-1)(n^2+n+1) = n^3 -1 \equiv 0 $ (mod $p$); in other words $n^3 \equiv 1$ (mod $p$).
We see that the order of $n$ modulo $p$ is a divisor of $3$ namely $\operatorname{ord}_p(n) \in \{\, 1,3 \, \}$.