Determine all positive integers $n$ such that $4k^2 +n$ is a prime number for all non-negative integer $k$ smaller than $n$.
Problem
Source: 2019 Romania JBMO TST 6.2
Tags: number theory, prime numbers, prime
10.03.2024 20:46
Splendid problem. I claim $n=3,7$ are the only possibilities. Taking $k=0$, we find $n$ is a prime, so $n$ is odd ($n>2$). We first show $n$ is a Mersenne prime, that is, $n=2^p-1$ for some $p$. Let $r\mid n+1$ be an odd prime. Then, notice that $r\le (n+1)/2<n$, and furthermore, there is a $k\le r-1$ such that $r\mid 4k^2-1$ (simply take $k\equiv 1/2\pmod{r}$). For this $k$, $r\mid 4k^2+n$, whereas $4k^2+n>r$, so it cannot be a prime, a contradiction. Hence, $n$ is indeed a Mersenne prime. Now set $n=2^p-1$ for some prime $p$ and assume $p\ge 5$ (handle $p<5$ manually). We now show this is impossible. To that end, we inspect $n+9 = 2^p + 8 = 8(2^{p-3}+1)$. Check that $2^{p-3}+1$ is odd, so there is a prime $r\mid 2^{p-3}+1$. Furthermore, $r\mid (n+9)/8<n$, so $r\le n-1$. Now, observe that there is a $k$ such that $4k^2\equiv 9\pmod{r}$ (it suffices to choose $k\equiv 3/2\pmod{r}$). As $r\le n-1$, for this choice we find $r\mid 4k^2+n$ but $4k^2+n>r$, again a contradiction.
17.06.2024 09:09
Amazing problem! Actually, I solved it only with the requirement that $k$ is a positive integer (i.e. $k=0$ is forbidden to work with, so $n$ need not be prime), ignoring $n=1$. (EDIT: nvm, actually $n$ must be prime by picking $k$ to be a prime divisor, but I do not really need this in my solution and it does not simplify anything, I think.) For even $n$ the integer $4k^2 + n > 2$ is also even and hence not prime. For $n = 4a + 1$ for a positive integer $a$ pick $k = a < n$, then $4k^2 + n = (2a+1)^2$ is not prime. Let $n = 4a - 1$ for some $a \geq 3$ (direct verification shows that $n=3$ and $n=7$ satisfy the requirements, the primes are $7$, $19$, $11$, $23$, $43$, $71$, $107$, $151$). Then $4k^2 + n = 4k^2 + 4a - 1$. If $k^2+a = x^2$ for some $x\geq 2$, then the expression is $4x^2 - 1 = (2x-1)(2x+1)$ with multipliers greater than $1$, hence composite. The latter is always possible for odd $a\geq 3$, e.g. with $k = \frac{a-1}{2}$. Write the main expression as $(2k-1)(2k+1) + 4a$. If $a$ is not a power of $2$, then by considering an odd prime divisor $q$ and picking $k = \frac{q+1}{2}$, the expression is divisible by $q$ and greater than $q$, hence it is composite. If $a = 2^m$ for $m\geq 3$, $k^2 + 2^m = x^2$ has a solution if we e.g. pick $x - k = 2$ and $x + k = 2^{m-1}$, i.e. $k = 2^{m-2} - 1$. Finally, if we pick $a=4$, then the expression is divisible by $3$ for $k=3$. In conclusion, all solutions are $n=3$ and $n=7$.
17.06.2024 16:26
Here is a good idea by @africanboy, which unfortunately falls down and we cannot fix it. Write $k=n-a$ for $1 \leq a\leq n$, then we want $4(n-a)^2 + n = 4n^2 + (1-8a)n + a^2$ to be prime for all $a$. A natural way to make this composite is to be able to factor it - for that, the quadratic must have two rational roots, i.e. $(1-8a)^2 - 16a^2 = 48a^2 - 16a + 1$ to be a perfect square, i.e. $4(6a-1)^2 - 3m^2 = 1$ for some $m$. However, all solutions of the Pell equation $4x^2 - 3m^2 = 1$ turn out to be NOT congruent to $5$ mod $6$, so positive $a$ are not solutions here (though there are infinitely many negative working...). EDIT: Even worse, $48a^2 - 16a + 1 = (12a-1)(4a-1)$ and since the factors are coprime, they must both be perfect squares (if $a>0$; else they can also be minus perfect squares). But a perfect square cannot be $3$ mod $4$.
18.06.2024 12:51
Here's a significantly simpler solution. If $n$ is even, then $4k^2+2 > 2$ is even and not prime. If $n=4a+1$, then $k=a$ gives $(2a+1)^2$ which is not prime. If $n=8a+3$, then $k=a$ gives $4a^2+8a+3 = (2a+1)(2a+3)$, not prime for $a\geq 1$. If $n = 16a+7$, then $k=a$ gives $4a^2+16a+7 = (2a+1)(2a+7)$, not prime for $a\geq 1$. If $n=16a+15$, then $k=a$ gives $4a^2+16a+15 = (2a+3)(2a+5)$, not prime. Finally, direct check shows that $n=3$ and $n=7$ are solutions.