Prove: $\text{$n$ is even} \iff n^n\equiv 1\mod{(n+1)}$ 
Prove: $\text{$n$ is even} \iff n^n\equiv 1\mod{(n+1)}$

where $n\in\mathbb{N}$.
First, to prove $n^n\equiv 1\mod{(n+1)}\implies\text{$n$ is even}$, I supposed $n^n\equiv 1\mod{(n+1)}$ is true.
It goes like this:
The supposed proposition could be rewriten in the form of:
$$\forall k\in\mathbb{Z}:n^n=1+k(n+1)\tag{1}$$
Assume $n$ is odd, then, $n=2p+1$ so $n^n$ too. Hence, $n^n=2q+1$ where $p,q\in\mathbb{N}$.
Applying this to $(1)$ we get:
\begin{align}
\forall k&:2q+1=1+k(2p+2)\\
\forall k&:2q=2k(p+1)\\
\forall k&:q=k(p+1)\\
\end{align}
Assume $k=-1$ then $q=-p-1\implies q+p=-1$ and because the sum of two naturals will always be greater than 1, then this conclusion is false, then we've got a contradiction. So $n$ must be even.

The problem is the other way around, to prove $\text{$n$ is even} \implies n^n\equiv 1\mod{(n+1)}$. I don't even know where to start. I tried assuming $n$ is even, then $n^n$ too but I don't know when to insert the modulo operator. Any hint or solution would be fine.
 A: Hint $\ {\rm mod}\ n\!+\!1\!:\,\ n+1\equiv 0\,\Rightarrow\,\color{#c00}{n\equiv -1}\,\Rightarrow\, \color{#c00}n^{\large n}\equiv (\color{#c00}{-1})^{\large n}\ $ by the Congruence Power Rule.
A: The reverse direction is false for the counterexample of $n=1$.  It happens to be true however for all other values of $n\geq 2$.
Note that $1^1\equiv 1\pmod{1+1}$ however $1$ is not even.
To prove the reverse direction is true for all $n\geq 2$ we can do the same as when we prove the forward direction except this time we begin by assuming $n$ is odd.  Begin by noticing that $n\equiv -1\pmod{n+1}$, so we have
$n^n \equiv (-1)^{2k+1}\equiv -1\pmod{n+1}$ which is not equivalent to $1\pmod{n+1}$ (except in the case that $0\equiv 2\pmod{n+1}$, i.e. when $n=1$)
A: For the $\,\Longrightarrow\,$, there is an interesting trick:
Let $\,n=2m\,$ for $\,m\in\mathbb N\,$, then we have
$$n^n-1\ =\ n^{2m}-1\ =\ (n^m+1)(n^m-1)$$
Take this as a polynomial of $\,n\,$, hence 
($1$) If $\,m\,$ is odd, then $\,(n+1)\,$ divides $\,(n^m+1)$, so $\,n^n-1\equiv0\ \,\rm mod\ (n+1)$ 
($2$) If $\,m\,$ is even, then $\,(n+1)\,$ divides $\,(n^m-1)$, so $\,n^n-1\equiv0\ \,\rm mod\ (n+1)$ 
