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.
As you have already observed, $p^k\mid (x-1)(x+1)$. In particular $p\mid (x-1)(x+1)$, so either $p\mid x-1$ or $p\mid x+1$. In any case, we cannot have both since $p\not\mid 2$. This implies that $p^k\mid x-1$ or $p^k \mid x+1$. Why?
This works in general: $x^2=n\mod p^k$ has at most two incongruent solutions.
Best Answer
Since $d \mid p-1$, $x^d \mid x^{p-1}$ as polynomial, hence $x^d -1 \mid x^{p-1} -1$.
Suppose $p-1 = kd$, then $x^{p-1} -1 = x^{kd} - 1 = (x^d-1)(x^{(k-1)d}+...+1)$. Since $x^d-1$ is factored out, we have $x^d-1 \mid x^{kd}-1$, then $x^d-1 \mid x^{p-1} -1$, which implies $x^d-1 \mid x(x^{p-1} -1)$ so $x^d-1 \mid x^p-x$.
Next, we need a theorem saying that $f(x) \equiv 0 \pmod{p}$ has exactly $n$ distinct solutions if and only if $f(x) \mid x^p-p\pmod{p}$. For a proof of this theorem, please consult https://ocw.mit.edu/courses/mathematics/18-781-theory-of-numbers-spring-2012/lecture-notes/MIT18_781S12_lec7.pdf