Let $n \ge 3$ be an integer such that $4n+1$ is a prime number. Prove that $4n+1$ divides $n^{2n}-1$.
Problem
Source: Baltic Way 2018, Problem 18
Tags: number theory, prime numbers
RagvaloD
06.11.2018 13:02
$4^{2n}( n^{2n}-1)=(p-1)^{2n}-2^{4n} =(p-1)^{2n}-2^{p-1} \equiv 0 \pmod{p}$
Kimchiks926
20.10.2020 13:20
Note that $4n \equiv -1 \pmod p \implies (2n)^2 \equiv -n \pmod p$. So we deduce that $n$ is quadratic residue $\pmod p$. Consequently:
$$ (-n)^{\frac{p-1}{2}} \equiv 1 \pmod p$$But since $\frac{p-1}{2} =2n$ we have that:
$$ (-n)^{2n} \equiv n^{2n} \equiv 1 \pmod p $$and we are done.
Aimingformygoal
26.05.2021 16:43
Let $4n+1=p$, hence $n=\frac{p-1}{4}$. So, it suffices to show that $p$ divides $(\frac{p-1}{4})^\frac{p-1}{2}-1$
By binomial theorem, $$(\frac{p-1}{4})^\frac{p-1}{2}-1= \frac{p^{\frac{p-1}{2}}- \binom{p-1}{2}p^{\frac{p-3}{2}} \cdots +1}{4^\frac{p-1}{2}}-1$$$$(\frac{p-1}{4})^\frac{p-1}{2}-1 = \frac{p^{\frac{p-1}{2}}- \binom{p-1}{2}p^{\frac{p-3}{2}} \cdots +1-2^\frac{2(p-1)}{2}}{4^\frac{p-1}{2}} = \frac{p^{\frac{p-1}{2}}- \binom{p-1}{2}p^{\frac{p-3}{2}} \cdots +1-2^{(p-1)}}{4^\frac{p-1}{2}} $$$$(\frac{p-1}{4})^\frac{p-1}{2}-1 =\frac{p^{\frac{p-1}{2}}- \binom{p-1}{2}p^{\frac{p-3}{2}} \cdots +1-2^{(p-1)}}{4^\frac{p-1}{2}} \equiv \frac{1 - 2^{(p-1)}}{4^\frac{p-1}{2}} \pmod p$$By FLT, $2^{(p-1)} \equiv 1 \pmod p$. Hence, $(\frac{p-1}{4})^\frac{p-1}{2}-1 \equiv \frac{1 - 2^{(p-1)}}{4^\frac{p-1}{2}} \equiv 0 \pmod p$, as desired. $\blacksquare$
MatBoy-123
14.08.2021 14:16
This problem is too ezzy , Let $4n+1 = p$ Note that from Euler's Criterion, the problem is equivalently to prove that $\frac{p-1}{4}$ is q QR $mod$ $p$ , but as $4 = 2^2$ , it is equivalently to prove that $p-1$ is a QR , which is true , as $p = 4n+1$
CrazyInMath
21.10.2023 15:44
as $4n+1$ is prime, $n^{2n}\equiv 1\pmod{4n+1}\Longleftrightarrow \left(\frac{n}{4n+1}\right)=1$. by quadratic reciprocity, and $n(n-1)$ is even for all $n$, and $\left(\frac{4n+1}{n}\right)=\left(\frac{1}{n}\right)=1$, we have \[\left(\frac{n}{4n+1}\right)=\left(\frac{4n+1}{n}\right)\left(\frac{n}{4n+1}\right)=(-1)^{\frac{4n(n-1)}{4}}=(-1)^{n(n-1)}=1.\]