A prime $p$ of the form $4k+1$ implies that $k^k \equiv 1 \mod p$?

364 Views Asked by At

I can not prove this statement that seems related to Fermat's little theorem. I would appreciate indications to prove this result (suggestions, links, etc.)

Following @mark-bennet hints:
$4k \equiv -1 \implies (4k)^k \equiv (-1)^k$
We use the fact that $k = \frac{p-1}{4}$, then
$4^{\left(\frac{p-1}{4}\right)} k^k \equiv (-1)^k \implies 2^{\left(\frac{p-1}{2}\right)} k^k \equiv (-1)^k$
We use the Legendre symbol $\left(\frac{a}{p}\right) \equiv a^{\left(\frac{p-1}{2}\right)}$ to express $2^{\left(\frac{p-1}{2}\right)}$
$\left(\frac{2}{p}\right) k^k \equiv (-1)^k$
We know that (see Legendre symbol in wikipedia)
$\left(\frac{2}{p}\right) \equiv \left\{\begin{array}[ll] +1 & \text{if } p \equiv 1 \text{ or } 7 \mod 8\\ -1 & \text{if } p \equiv 3 \text{ or } 5 \mod 8\end{array}\right.$
If $k$ is odd, then $k=2r+1 \implies p=4k+1=8r+5 \implies \left(\frac{2}{p}\right)=-1$
If $k$ is even, then $k=2r \implies p=4k+1=8r+1 \implies \left(\frac{2}{p}\right)=1$
In both cases, $k^k\equiv 1$

1

There are 1 best solutions below

0
On BEST ANSWER

Here is a hint for how you might start:

$$4k\equiv -1$$

so

$$(4k)^k\equiv (-1)^k$$and that should be enough to get you $k^k$ in terms of something else you might know how to work with.


To develop my comments a bit, we have that $2$ is a square mod $p$ for $p\equiv \pm 1\bmod 8$ and otherwise is not a square.

Also $(-1)^k=\pm 1$ depending whether $k$ is even or odd.

If $k=2r+1$ is odd, then $p=4k+1=8r+5$ and $2$ is not a square mod $p$. If $k$ is even then $2$ is a square.

There is still a bit of work to do - to check that my assertions about $2$ as a square are true, for example, and to work out how that can be used.