24
$\begingroup$
  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?

$\endgroup$
  • $\begingroup$ Do you know the answer to this question? $\endgroup$ – greenturtle3141 Dec 31 '16 at 15:43
  • $\begingroup$ I am voting to close this question as off topic. $\endgroup$ – Matsmath Dec 31 '16 at 16:02
  • 13
    $\begingroup$ Before you close this question, please consider that there is a clever approach (using modular arithmetic) and I'm currently writing the answer. $\endgroup$ – wythagoras Dec 31 '16 at 19:45
  • 2
    $\begingroup$ 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?" $\endgroup$ – Henning Makholm Jan 2 '17 at 1:49
  • 1
    $\begingroup$ @Matsmath Why? You should never VTC a question without explaining exactly why it's off-topic. $\endgroup$ – Rand al'Thor Jan 4 '17 at 0:56
34
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Wonderfully clever! $\endgroup$ – Joseph O'Rourke Jan 1 '17 at 1:00
  • $\begingroup$ 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 $\endgroup$ – The Great Duck Jan 1 '17 at 3:09
  • $\begingroup$ @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. $\endgroup$ – wythagoras Jan 1 '17 at 13:17
  • $\begingroup$ Great work there, kudos :) $\endgroup$ – ABcDexter Jan 1 '17 at 18:41
  • $\begingroup$ @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. $\endgroup$ – The Great Duck Jan 1 '17 at 20:59
13
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Very nice! Just a wait of $9300$ years :-). $\endgroup$ – Joseph O'Rourke Dec 31 '16 at 16:17
  • 5
    $\begingroup$ Yay for cryogenic sleep! :) $\endgroup$ – M Oehm Dec 31 '16 at 16:19
  • $\begingroup$ So, did you use some code? $\endgroup$ – Sid Dec 31 '16 at 16:32
  • 1
    $\begingroup$ 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). $\endgroup$ – Ant Jan 1 '17 at 3:17
  • 1
    $\begingroup$ @JohnChessant: I wonder if there are an infinite number of such primes? I just posed that question on MSE. $\endgroup$ – Joseph O'Rourke Jan 1 '17 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.