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

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!

• It's pretty clear that $n^{2n}\equiv 1\pmod p$, since $-1$ is a square modulo $p$ and $4n\equiv -1$ so $n$ is a square, so $n^{2n}=n^{\frac{p-1}{2}}\equiv 1\pmod p$.Not sure how that helps. – Thomas Andrews Nov 5 '13 at 20:31
• By direct calculation, $n^n\equiv1\mod{p}$ iff $(-4)^n\equiv1\mod p$.Which is obvious since $-4$ is a forth power. – asatzhh Nov 5 '13 at 20:48

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}.$$

• Thinking of (k+2n) is kind of a hard thing, I guess. I still wonder if there might be a more easy way to solve this. But your proof is concrete enough! – Taxxi Nov 6 '13 at 3:47

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}

• It's just my fault that I don't know very well about the concept (nth-power). I think I have to check it out. Thanks! – Taxxi Nov 6 '13 at 3:48
• Now... I've got understood what you meant now... Thanks. – Taxxi Nov 8 '13 at 5:00

Here is one more proof that $-4$ is a fourth power modulo $p$ (for $p \equiv 1 \bmod 4$.) Let $i$ be a square root of $-1$. Then $(1+i)^4=-4$.

Recall from the Law of Quadratic Reciprocity that

$$\left(2\over p\right)=(-1)^{(p^2-1)/8}$$

for any odd $p$. If $p=4n+1$, then $(p^2-1)/8=(2n+1)n$, so that

$$\left(2\over p\right)=(-1)^{(2n+1)n}=(-1)^n$$

But since $({a\over p})\equiv a^{(p-1)/2}$ mod $p$ in general, we also have

$$\left(2\over p\right)\equiv2^{(p-1)/2}=2^{2n}=4^n\mod p$$

It follows that

$$(-1)^n\equiv(p-1)^n=(4n)^n=4^nn^n\equiv\left(2\over p\right)n^n\equiv(-1)^nn^n\mod p$$

Cancelling the $(-1)^n$'s, we are left with $n^n\equiv1$ mod $p$.