Show that there exist infinitely many composite positive integers $n$ such that $n$ divides $2^{\frac{n-1}{2}}+1$
Problem
Source: Kazakhstan National Olympiad 2017, P6, March 16
Tags: number theory, Kazakhstan
BarishNamazov
16.03.2017 15:18
Prove all numbers such that are in form of $\frac{4^p + 1}{5}$ where $p > 5$ is prime number.
Puzzled417
13.05.2017 15:45
We prove that $n = \dfrac{4^p+1}{5}$ where $p > 5$ is a prime number satisfies the question. Note that $2^{2p} = 4^p = 5n-1 \equiv -1 \pmod{n}$, so the result follows if $2p \mid \frac{n-1}{2}$ since $n-1$ is divisible by $4$ but not $8$. Since $n-1$ is divisible by $4$, we just need to show that $p$ divides $n-1$. By Fermat's Little Theorem we have $p \mid 4^p-4 = 5(n-1)$, and since $p > 5$, it follows that $p \mid (n-1)$.
There are other solutions besides $n = \dfrac{4^p+1}{5}$ for a prime $p > 5$. Let $m = \frac{4^p+1}{5}+k$. Then $k = 8p$ gives another solution for $p = 11$.
guangzhou-2015
18.06.2017 07:42
How to prove $n$ is a composite number
Jjesus
08.11.2020 19:48
How to prove that $n=\frac{4^p+1}{5}$ is composite?
grupyorum
09.11.2020 02:48
Guys above: I think you must need $p\equiv 1\pmod{4}$. If $p=4\ell+1$, then $4^p = 4\cdot (4^\ell)^2 = 4a^4$ for some $a$, and we can use the well-known identity $4a^4+1 = 4a^4+4a^2+1 - 4a^2 = (2a^2-2a+1)(2a^2+2a+1)$ to deduce $\frac{4^p+1}{5}$ is not a prime.