2017 is the 1st prime satisfying three conditions. What is the 2nd?

Question

1. $2017$ is prime, and so is $(2017+1)/2=1009$.

2. $2017$ can be written as $a^2 + b^4$: $2017 = 44^2 + 3^4 = 1936 + 81$.

3. $2017 \equiv 2 \bmod 31$.

What is the next prime (if any) that satisfies these same three conditions?

Answer 1

Actually, with a bit of modular arithmetic and patience, you can find a solution without code.

Looking $\mod 3$:

Note that neither $p$, nor $p+1$ can be divisible by 3. Hence $p \equiv 1 \mod 3$.

Looking $\mod 4$:

Squares and hence fourth powers are 0 or 1 mod 4, so their sum is 0, 1 or 2 mod 4.
Clearly only 1 mod 4 is possible, hence $p \equiv 1 \mod 4$.

Looking $\mod 5$:

Squares are 0, 1 or 4 mod 5, fourth powers 0 or 1 mod 5. Note that neither $p$, nor $p+1$ can be divisible by 5. This gives as the only possibilities that $p \equiv 1 \mod 5$ or $p \equiv 2 \mod 5$.

Looking $\mod 31$:

It is given that $p \equiv 2 \mod 31$.

Combining with Chinese remainder theorem:

$3 \cdot 4 \cdot 5 \cdot 31 = 1860$, so we need to look mod 1860. Note that $2017 \equiv 2 \mod 5$, so $p \equiv 2 \mod 5$ gives with the other congruences that $p \equiv 2017 \equiv 157 \mod 1860$. The other possibility gives $p \equiv 1 \mod 60$ and $p \equiv 2 \mod 31$. This gives $p \equiv 901 \mod 1860$.

Now, we have only a few possibilities left:

• $p=157$ and $p=901$ are discarded because it is given that $2017$ is the smallest.
• $p=2761$ is divisible by 11 (alternating sum test).
• $p=3877$ gives $(p+1)/2=1939$, which is divisible by 7.
• $p=4621$ is more difficult. For this, we need to check all possible fourth powers. However, it can be made a little easier by noting that either the square or the fourth power is divisible by 5. (Edit: this one is actually easier; looking mod 16: all squares are 0, 1, 4 or 9 mod 16, fourth powers 0 or 1 mod 16, hence their sum can't be 13 mod 16, but $4621 \equiv 13 \mod 16$)
• $p=5737$ gives $(p+1)/2=2869$, which is divisible by 19.
• $p=6481$ gives $(p+1)/2=3241$, which is divisible by 7.
• $p=7597$ gives $(p+1)/2=3799$, which is divisible by 29.
• $p=8341$ is divisible by 19.
• $p=9457$ is divisible by 7.
• $p=10201$, which can be recognized as $101^2$.
• $p=11317$, finally, satisfies.

The most difficult thing is proving (by hand) that $p=11317$ and $p=5659$ are prime, but other than that, it is actually doable. I did use a number factorizer in the proces, to be honest, but the largest prime I used was 29, so it can be done by hand.

Alternatively, one could check every fourth power to see if $p$ can be written as $a^2+b^4$.
There are only 10 below $10^4=10000$, so that should also be doable.

Answer 2

I think the next number that satisfies these conditions is:

11317.

(1)   It is prime and 11318 / 2 = 5659 is also prime.
(2)   It can be written as 106² + 3⁴.
(3)   It has a remainder of 2 when divided by 31.