75th NMO Selection Tests

We check by direct computation that $n=2,3,4$ are solutions. We will prove that these are the only ones. We may assume $n\ge 5$ after checking all smaller cases. We distinguish two cases.

(I) If $n$ is even, write $n=2t$ (then $t\ge 3$). One can prove that $$(2^t-1{)}^2<2^n-n^2+1<(2^t{)}^2=2^n,$$ which means that in this case, $2^n-n^2+1$ cannot be a perfect square. Indeed, the second inequality is obvious, and the first can be proven easily by induction for $t\ge 7$, with the base cases $t=3,4,5,6$ verified directly.

(II) If $n$ is odd, let $p$ be the largest (necessarily odd) prime dividing $n$. If $p=3$, then $n=3^k$, and since $n\ge 5$, it follows that $k\ge 2$, so in particular $9\mid n$. But then $2^9+1$ divides $2^n+1$, hence $19\mid 2^n+1$ (since $2^9+1=512+1=513=27\cdot 19$). If $2^n-n^2+1=a^2$, then $2^n+1=n^2+a^2$. Since $19\mid 2^n+1$, and $19\equiv 3(\mathrm{mod}4)$, it follows that $19\mid n^2+a^2$. But then $19\mid n$, which contradicts the assumption that $n=3^k$.

Therefore, we must have $p>3$. Since $2^p+1\equiv 1(\mathrm{mod}4)$, it follows that $3\mid 2^p+1$, but $3^2$ does not divide $2^p+1$ (this follows immediately from factoring $2^p+1$ or applying LTE for $p=3$). This implies that there exists a prime $q>3$, with $q\equiv 3(\mathrm{mod}4)$ such that $q\mid 2^p+1$. Using the statement below, we obtain that $q>p$. Since $q\mid 2^p+1\mid 2^n+1$, and assuming $2^n-n^2+1=a^2$, we get $2^n+1=n^2+a^2$. By the same reasoning as above, $q\mid n$, which contradicts the maximality of $p$ as the largest prime dividing $n$. This completes the proof that for $n\ge 5$, the expression $2^n-n^2+1$ is not a perfect square.

Claim. If $p$ is a prime with $p\ge 5$, then any odd prime factor $q$ of $2^p+1$, different from 3, satisfies $q>p$. Proof. Let $q>3$ be a prime dividing $2^p+1$. Then $2^p\equiv -1(\mathrm{mod}q)$, so the order of 2 modulo $q$ is $2p$. Indeed, the order of 2 (mod $q$) must divide $2p$, so it could be 1, 2, $p$, or $2p$. It cannot be 1 or $p$ (as $2^p\equiv -1\not\equiv 1(\mathrm{mod}q)$), and if it were 2, then $2^2\equiv 1(\mathrm{mod}q)$ implies $q=3$, contradicting $q>3$. Since $(2,q)=1$, by Fermat's Little Theorem we have $2^{q-1}\equiv 1(\mathrm{mod}q)$. But the order of 2 modulo $q$ is $2p$, so $2p\mid q-1$, which implies $p<q$.