A prime is called perfect if there is a permutation $a_1, a_2, \cdots, a_{\frac{p-1}{2}}, b_1, b_2, \cdots, b_{\frac{p-1}{2}}$ of $1, 2, \cdots, p-1$ satisfies $$b_i \equiv a_i + \frac{1}{a_i} \pmod p$$for all $1 \le i \le \frac{p-1}{2}$. Show that there are infinitely many primes that are not perfect. Proposed By - CSJL
Problem
Source: IMOC 2021 N10
Tags: number theory, IMOC
16.08.2021 14:09
We will prove that all primes $p>5$ with $$p\equiv 1\pmod 4\quad\text{and}\quad p\not\equiv\pm1\pmod 5\qquad (*)$$are not perfect. First of all let us generate such infinitely many primes. We can use Dirichlet's theorem, but this is unnecessary. Instead, we mimic Euclid's proof. Consider a sequence $\{p_n\}$ of prime numbers with $p_1=13$ and recursively for each $n\ge 2$, $p_n$ is a prime factor of $\frac{25\left(\prod_{i=1}^{n-1}p_i\right)^2+1}{2}$ with $p_n\not\equiv\pm1\pmod 5$. Let us prove that all $p_n$ are mutually distinct and satisfy $(*)$. Note that $13$ satisfies $(*)$ so assume $n\ge 2$. By construction, $$\frac{25\left(\prod_{i=1}^{n-1}p_i\right)^2+1}{2}\equiv 3\not\equiv\pm 1\pmod 5$$so such $p_n$ exists. Note that for all $n\ge 2$ the number $p_n$ is prime to $\prod_{i=1}^{n-1}p_i$, so all $p_i$ are mutually distinct. Obviously, $p_n$ is odd. Since $p_n$ divides a number of the form $x^2+1$ we obtain $p\equiv 1\pmod 4$. Now assume a prime $p$ satisfies $(*)$. Since $p\equiv 1\pmod 4$, there exists $x\in\{1,\dots,p-1\}$ such that $p\mid x^2+1$. Then $x$ cannot be in the $a_i$ since otherwise $b_i\equiv 0\pmod p$. So assume WLOG $b_1=x$. Hence \begin{align*} &a_1+\frac{1}{a_1}\equiv b_1\pmod p\\ &\implies a_1^2-a_1b_1+1\equiv 0\pmod p\\ &\implies\left(a_1-\frac{b_1}{2}\right)^2\equiv\frac{b_1^2}{4}-1\pmod p\\ &\implies\left(a_1-\frac{b_1}{2}\right)^2\equiv -\frac{5}{4}\pmod p \end{align*}Hence $\left(\frac{-5}{p}\right)=1$. Since $\left(\frac{-1}{p}\right)=1$ we have $\left(\frac{5}{p}\right)=1$. By quadratic reciprocity, $$\left(\frac{p}{5}\right)=\left(\frac{5}{p}\right)\cdot (-1)^{\frac{5-1}{2}\cdot\frac{p-1}{2}}=\left(\frac{5}{p}\right)$$Since $p\not\equiv\pm1\pmod 5$ we have $\left(\frac{p}{5}\right)=-1$. Hence $\left(\frac{5}{p}\right)=-1$, contradiction.
01.03.2022 12:09
First, observe that a number $y$ can be written as $x+x^{-1}$ must satisfy $y^2-4$ not a quadratic nonresidue. Therefore, if $y,\frac 1y$ fails to satisfy this criterion then $p$ is not perfect because $y,\frac 1y$ both must appear on the $a$ side, paired with $y+y^{-1}$ Set $y=4$. We need $y^2-4$ NQR so 3 is NQR. Also, $\frac{1}{y^2}-4=\frac{-63}{16}$ is also a QNR. Thus 3 and -7 are both QNR. By QR, any prime that is 1 mod 4, -1 mod 3 and -1 mod 7 works. THere are infinitely many such primes by dirichlet.