Prime divisibility concerning primes of the form $4k+1$ Let $p=4k+1$ be a prime number.
I need to  prove that $p$ divides $k^k-1$.
Could anyone give me some hint?
Thank
 A: Since you asked for only a hint: $$p \mid k^k-1 \Leftrightarrow p \mid (-4)^k(k^k-1) \Leftrightarrow p \mid 1-(-4)^k$$
Now prove that $-4$ is a quartic residue $\pmod{p}$, using a primitive root $\pmod{p}$ to check when $-1$ is a quartic residue, and relevant conditions for $2$ to be a quadratic residue.
Edit: To finish off, let $r$ be a primitive root $\pmod{p}$. Then $r^{2k} \equiv -1 \pmod{p}$. 
If $k$ is even, then $-1$ is a quartic residue, and since $p \equiv 1 \pmod{8}$, $2$ is a quadratic residue, so $4$ is a quartic residue. Combining, $-4$ is a quartic residue.
If $k$ is odd, then $p \equiv 5 \pmod{8}$ so $2$ is a non-quadratic residue. Put $r^{2l+1} \equiv 2 \pmod{p}$, then $(-4) \equiv r^{2k+4l+2} \pmod{p}$. Since $k$ is odd, this implies that $-4$ is again a quartic residue.
A: Note,  mod $\,p = 4k\!+\!1,\ $ that $\,-1\,$ is a square, say $\, -1 \equiv i^2,\ $ by $ $ Euler's criterion. $\phantom{I_{I_{I_I}}}$
$\!\begin{eqnarray}
\text{Therefore}\quad\ {-4}k\equiv 1\,\Rightarrow\,\color{#c00}{k^{-1}\ \equiv\ {-}4}&&\equiv \color{#c00}{(1+i)^4}\ \  {\rm by\ squaring}\ \ 2i \equiv (1+i)^2 \\[0.1em]
\ {\rm Thus\ prior}^k\Rightarrow\, k^{-k}\equiv (\color{#c00}{k^{-1}})^{k} \equiv (\color{#c00}{-4})^{k}\!\!\! &&\equiv \color{#c00}{(1+i)}^{\color{#c00}4k}\!\equiv (1+i)^{p-1}\!\equiv 1\, \Rightarrow\, k^k \equiv 1^{-1}\!\equiv 1.\ \ \, {\rm QED}
\end{eqnarray}$
A: Here's a way with QR. Using $\displaystyle\rm a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)\bmod p$, derive
$$\rm\quad k^k\equiv\left(\frac{p-1}{4}\right)^{(p-1)/4}\equiv(-1)^k\left(\frac{2}{p}\right)\equiv\cdots\pmod p$$
(what does QR's supplement tell us about $\rm\left(\frac{2}{p}\right)$?)
