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$
8
  • $\begingroup$ Do you know the answer to this question? $\endgroup$ Dec 31, 2016 at 15:43
  • $\begingroup$ I am voting to close this question as off topic. $\endgroup$
    – Matsmath
    Dec 31, 2016 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, 2016 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$ Jan 2, 2017 at 1:49
  • 1
    $\begingroup$ @Matsmath Why? You should never VTC a question without explaining exactly why it's off-topic. $\endgroup$ Jan 4, 2017 at 0:56

2 Answers 2

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$
7
  • 5
    $\begingroup$ Wonderfully clever! $\endgroup$ Jan 1, 2017 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$
    – user64742
    Jan 1, 2017 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, 2017 at 13:17
  • $\begingroup$ Great work there, kudos :) $\endgroup$
    – ABcDexter
    Jan 1, 2017 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$
    – user64742
    Jan 1, 2017 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$
8
  • 3
    $\begingroup$ Very nice! Just a wait of $9300$ years :-). $\endgroup$ Dec 31, 2016 at 16:17
  • 5
    $\begingroup$ Yay for cryogenic sleep! :) $\endgroup$
    – M Oehm
    Dec 31, 2016 at 16:19
  • $\begingroup$ So, did you use some code? $\endgroup$
    – Sid
    Dec 31, 2016 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, 2017 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$ Jan 1, 2017 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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