Find smallest prime $p$ such that all primes $q < 40$ are quadratic non-residues $\pmod p$

This is just a tiny bit more involved than Wolfram Alpha can handle:

Select[Prime[Range[100]], Union[JacobiSymbol[Prime[Range[12]], #]] == {-1} &]

The answer is $163$. You could have gotten the answer a lot quicker if you had just asked a wood nymph.

Oh, right, you don't know how to talk to wood nymphs. Okay, so if in Mathematica you change 100 to 4096, the only answer is $163$. However, go up a little higher to find $74093$.

Why so few? That might be a more interesting question. Or not.


Probabilities are very useful when you know very little. But in this particular case, you actually know a lot. Like what the positive primes less than 40 actually are. Plus hopefully also some basic facts about quadratic reciprocity.

The primes modulo 12 are 1, 5, 7, 11. So, given a prime $p \equiv 1 \pmod{12}$, we have $$\left(\frac{p}{3}\right) \equiv p^1 \pmod 3 = 1,$$ and correspondingly by quadratic reciprocity $$\left(\frac{3}{p}\right) = 1,$$ so this rules out primes of the form $12k + 1$. Contrast this to a prime $p \equiv 5 \pmod{12}$, we have $$\left(\frac{p}{3}\right) \equiv p^1 \pmod 3 = -1,$$ and correspondingly by quadratic reciprocity $$\left(\frac{3}{p}\right) = -1.$$

For a prime $p \equiv 7 \pmod{12}$, we have $$\left(\frac{p}{3}\right) \equiv p^1 \pmod 3 = 1,$$ but there's no reciprocity in this case and hence $$\left(\frac{3}{p}\right) = -1.$$ Contrast this to a prime $p \equiv 11 \pmod{12}$, for which we have $$\left(\frac{p}{3}\right) \equiv p^1 \pmod 3 = -1$$ but $$\left(\frac{3}{p}\right) = 1.$$

This means we're looking for primes congruent to 5 or 7 modulo 12. This only rules out roughly half the primes.

Now going modulo 60, our primes are 5, 7, 17, 19, 29, 31, 41, 43, 53, 55... wait a minute, we can strike out 5 and 55 so our list is just 7, 17, 19, 29, 31, 41, 43, 53, which still seems a bit long and inelegant. Please bear with me.

If $p \equiv 7 \pmod{60}$, then $$\left(\frac{p}{5}\right) \equiv p^2 \pmod 5 \equiv 49 \equiv -1$$ and $$\left(\frac{5}{p}\right) = -1$$ also, so 7 stays on our list. Likewise $p \equiv 17 \pmod{60}$ gives us $$\left(\frac{p}{5}\right) \equiv p^2 \pmod 5 \equiv 49 \equiv -1$$ and $$\left(\frac{5}{p}\right) = -1.$$

And if $p \equiv 19 \pmod{60}$, then $$\left(\frac{p}{5}\right) \equiv p^2 \pmod 5 \equiv 1$$ and $$\left(\frac{5}{p}\right) = 1$$ also, so we cross 19 off our list. Likewise $p \equiv 29 \pmod{60}$ gives us $$\left(\frac{p}{5}\right) \equiv p^2 \pmod 5 \equiv 1$$ and $$\left(\frac{5}{p}\right) = 1.$$

Proceeding in this manner, we whittle our list down to 7, 17, 43, 53. I think this narrows things down enough to go back to the wider world of $\mathbb Z$.

At this point it seems reasonable to use Wolfram Alpha to move things along. JacobiSymbol[Prime[Range[12]], 43] gives us some 1s, and so does 53, as well as 67, we skip 77 on account of its not being prime, to see that 103 and 113 also give us a bunch of 1s... well, 113 just gives us two 1s, so it's a little closer to what we're looking for.

127 and 137 give us more 1s than 113. And then 163 gives us all $-1$s, like Interstellar Probe and the Short One already told us. A quick check tells us that 74093 is congruent to 53 modulo 60.