$k^n +1 \equiv 0 \pmod{n^2}$ 
Find $n>1$ such that $k^n +1 \equiv 0 \pmod{n^2}$ where $k$ is a prime.

I didn't know how to deal with $n^2$ and the fact that $k$ is prime. Should we split this into the cases that $\gcd(k,n) = 1$ and $\gcd(k,n) \neq 1$?
 A: I will show that there are infinitely many solutions, i.e., pairs $(p,n)$ such that $p$ is prime, $n\ge 2$ is integer, and $p^n \equiv -1\pmod{n^2}$. Note that $p\nmid n$.
By Euler's theorem we know that $p^{\varphi(n^2)} \equiv 1\pmod{n^2}$, and by the above also $p^{2n} \equiv 1\pmod{n^2}$. It follows by Knuth lemma that
$$
p^{\mathrm{gcd}(\varphi(n^2),2n)} \equiv 1\pmod{n^2}.
$$
At this point, suppose $n=q^m$, for some odd prime $q\neq p$. Then there exists a primitive root $g$ in $\mathbf{Z}/n^2\mathbf{Z}$, and let us denote by $j$ the unique exponent in $\{1,\ldots,\varphi(n^2)\}$ such that $p\equiv g^j\pmod{q^{2m}}$. It follows that
$$
j \mathrm{gcd}(\varphi(q^{2m}),2q^m) \text{ divides }\varphi(q^{2m}),
$$
that is equivalent to
$
2jq^{2m-1} \text{ divides }(q-1)q^{2m-1},
$
i.e., $j$ divides $\frac{q-1}{2}$. 
To obtain our solutions, let $q$ be a prime $\equiv 1\pmod{4}$ and choose $j=\frac{q-1}{4}$. Then, by Dirichlet's theorem there exist infinitely many primes $p\equiv g^j\pmod{q^{2m}}$.
