General: $n^n | (n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}$ if $n$ is odd and squarefree. Proof: If $p$ is an odd prime and $p^k|a-b$ ($k \geq 1$), we get that $p^{k+m}|a^{s p^m}-b^{s p^m}$ for all $m,s$. Set $a=(n-1)^{n^2}$ and $b=-(n+1)$, then $a^{n^{n-1}}+(-b)^{n^{n-1}}$ is the desired number. Since $a-b = (n-1)^{n^2} + (n+1) \equiv (-1)^\text{odd} +1 = 0 \mod n$, thus $p|a-b$ for all primes $p|n$. This now gives: $p^n|a^{s p^{n-1}}-b^{s p^{n-1}}=(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}$ with $s=\left(\frac{n}{p}\right)^{n-1}$. the result follows.

If $ n$ is even or not square-free, is there contradiction?

If $ n$ is even, then $ 4|n^n$, but $ (n\pm1)^{n^{n\mp1}}$ are both 1 mod 4, so their sum is not divisible by $ 4$. So $ n$ must be odd, but the square-free condition is unnecessary. By binomial expansion it suffices to show that for $ 1\leq k < n$, $ \left(n^{n\pm1}\atop k\right)$ are divisible by $ n^{n - k}$. Let $ \alpha = \nu_p(n)$, i.e., $ p^\alpha || n$. Then $ \left(n^{n\pm1}\atop k\right) = \frac {n^{n\pm1}}{k}\left(n^{n\pm1} - 1\atop k - 1\right)$, so it suffices to show $ \alpha(n - k) \leq \alpha(n - 1) - \nu_p(k)$, and for this it suffices to observe $ \nu_p(k) \leq \log_p(k) \leq \log_2(k) \leq k - 1 \leq \alpha(k - 1)$. So the result is true for all odd $ n$ (Mathematica 5's buggy PowerMod notwithstanding).

Isn't this trivial, after some simple algebra to make the exponents equal, by LTE?

@Wolstenholme That's essentially what ZetaX's solution is doing.