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

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?

• Do you know the answer to this question? – greenturtle3141 Dec 31 '16 at 15:43
• I am voting to close this question as off topic. – Matsmath Dec 31 '16 at 16:02
• Before you close this question, please consider that there is a clever approach (using modular arithmetic) and I'm currently writing the answer. – wythagoras Dec 31 '16 at 19:45
• Seeing this in the supercollider list, my first thought was that it would be, "here are the first and third condition; what is the second condition?" – hmakholm left over Monica Jan 2 '17 at 1:49
• @Matsmath Why? You should never VTC a question without explaining exactly why it's off-topic. – Rand al'Thor Jan 4 '17 at 0:56

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.

• Wonderfully clever! – Joseph O'Rourke Jan 1 '17 at 1:00
• Perhaps narrowing the list further before testing primes might make it more easily doable! I mean cause 10 numbers might be considered annoying to certain people not good at factoring (like me). XD – user64742 Jan 1 '17 at 3:09
• @TheGreatDuck I don't think there are easy ways to exclude more numbers, but see my last remark: it isn't really necessary to factor these numbers. – wythagoras Jan 1 '17 at 13:17
• Great work there, kudos :) – ABcDexter Jan 1 '17 at 18:41
• @wythagoras I meant that maybe by cross-referencing there might only be one number (out of all natural numbers) greater than 2017 that fulfills these properties so factoring might not be necessary period. – user64742 Jan 1 '17 at 20:59

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.

• Very nice! Just a wait of $9300$ years :-). – Joseph O'Rourke Dec 31 '16 at 16:17
• Yay for cryogenic sleep! :) – M Oehm Dec 31 '16 at 16:19
• So, did you use some code? – Sid Dec 31 '16 at 16:32
• I also used Python! Just for kicks, the next few numbers (with a and b in parentheses) after 2017 (44 | 3) and 11317 (106 | 3) are: 172021 (414 | 5) (don't hold your breath waiting for that year! :D), 188017 (409 | 12), 367321 (605 | 6), 438001 (660 | 7), 489337 (651 | 16), 509797 (714 | 1), 560017 (321 | 26), 705097 (611 | 24), and 926437 (54 | 31). [Brute-force search limited by a < 1000 and b < 50, so these next few are probably incomplete] 1434217 (621 | 32), 1501921 (36 | 35), 1746697 (259 | 36), 2007097 (819 | 34), 2085217 (9 | 38), 4901257 (651 | 46), and 4914277 (186 | 47). – Ant Jan 1 '17 at 3:17
• @JohnChessant: I wonder if there are an infinite number of such primes? I just posed that question on MSE. – Joseph O'Rourke Jan 1 '17 at 20:39