At a careers fair I was given a test to see how good I am at mental maths, And I was given multiple questions, asking whether a number was a prime.
Example question:
Which of these numbers isn't a prime?
$$257,317,287,263$$
Well, my first insentive is to check the 10s digit, so I added y to my answers and divided it by that y value, (Like $\frac{k+3}{3}$ is proved when $k$ is a multiple of $3$)
Turns out, none of the worked, not even the correct answer. (Which is $287$)
Which begs the question, how do you find a prime number mentally?, On a calculator it's as simple as displaying it's prime factors, but even then the computer inside is dividing it by $1,2,3,4,5,\ldots$ until its square root
My only guess is that there is a sequence that can be used to list a few primes, that knocks off $2$ of the candidates…
Edit: My technique was half right, rather than sticking to 3 i should have gone further up the prime numbers up to 20.
Best Answer
If you know about quadratic reciprocity, that can sometimes be helpful. In this case, you might notice that $287$ is close to $289 = 17^{2}.$ It follows that if $p$ is a prime divisor of $287,$ then $2$ is a quadratic residue (mod $p$), so that $p \equiv \pm 1$ (mod $8$). The first prime congruent to $1$ (mod $8$) is $17$, so no prime divisor of $287$ is congruent to $1$ (mod $8$). The only prime congruent to $7$ (mod $8$) which is small enough to have a chance of dividing $287$ is $7$ itself, which does indeed work. In this case, the strategy is not quicker than trial and error, but for larger numbers, quadratic reciprocity can prune possibilities.