Show that prime $p=4n+1$ is a divisor of $n^{n}-1$

Question

Show that the prime number $p=4n+1$ is a divisor of $n^{n}-1$

---

Ok, the question itself is simple as hell, but I couldn't think of a simple way to solve this question. I tried to solve the question by using $p\equiv 1 \pmod n$ but only to fail miserably... I couldn't use quadratic residue concept neither since n could be odd.

It would be really glad if some could figure it out using methods of elementary number theory such as primitive root, Jacobian symbols and so on (since I'm just a beginner for number theory stuff).

Thanks!

Answer 1

We know that $n$ is a quadratic residue modulo $p$, since $1 = \left( \frac{-1}{p}\right) = \left(\frac{4n}{p}\right) = \left(\frac{n}{p}\right)$. Let $k^2 \equiv n \pmod{p}$. Then

$$(k+2n)^2 = k^2 + 4nk + 4n^2 \equiv n -k - n \equiv -k \pmod{p},$$

so $n$ is in fact a fourth power, $n \equiv (k+2n)^4 \pmod{p}$. Hence

$$n^n \equiv (k+2n)^{4n} = (k+2n)^{p-1} \equiv 1 \pmod{p}.$$

Answer 2

We'll use this lemma which I'll leave for you to prove:

Ic $p=4n+1$ is prime, then $a^n\equiv 1\pmod {p}$ if and only if $a\equiv x^4\pmod p$ for some $x$ not divisible by $p.$

We'll show that $-4$ is always a fourth power, $\pmod p$.

If $n$ is even, then $p\equiv 1\pmod 8,$ so $2$ is a square, and hence $4$ is a fourth power. Also $(-1)^n\equiv 1\pmod p$, $-1$ is a fourth power modulo $p$ by our lemma, and so $-4$ is a fourth power.

If $n$ is odd, then $-1\equiv x^2$ where $x$ is not a square. This is because if $x$ were a square, then $x^4=1$ and $x^{(p-1)/2}=1$, and hence $x^2=1,$ since $\gcd\left(4,\frac{p-1}{2}\right)=2.$

Similarly, $2$ is not a square modulo $p,$ So $2x$ is a square, $\pmod p$. So $4x^2\equiv -4\pmod p$ is a fourth power.

---

Knowing that $-4$ is a fourth power is all you need, since:

$$-4n\equiv 1\pmod p$$

So $n$ is a fourth power, too, so, again by our lemma, $n^n\equiv 1\pmod p$.

---

An alternative approach to showing that $x^4+4\equiv 0\pmod{p}$ for some $x$ is to use that:

$$x^4+4 = (x^2+2)^2-(2x)^2=(x^2-2x+2)(x^2+2x+2)=((x-1)^2+1)((x+1)^2+1)$$

Thus we have that $x^4+4\equiv 0\pmod p$ when $(x\pm 1)^2\equiv -1\pmod p.$ But since $p\equiv 1\pmod{4},$ $-1$ is a square modulo $p$, we know such $x$ exists.

---

Using that last approach as a jumping off point, we can start with $y$ such that $y^2\equiv -1\pmod{p}.$

Then $$\begin{align}(y+1)^4 &= y^4+4y^3+6y^2+4y+1 \\&\equiv 1+4y(-1)+6(-1)+4y+1\pmod{p}\\&=1+(-6)+1\\&=-4\pmod{p}\end{align}$$