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.

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)$ 
