The Universe of Discourse

This ONE WEIRD TRICK for primality testing… doesn't work

This morning I was driving Lorrie to the train station early and trying to factor the four digit numbers on the license plates as I often do. Along the way I ran into the partial factor 389. Is this prime?

The largest prime less than !!\sqrt{389}!! is !!19!!, so I thought I would have to test primes up to !!19!!. Dividing by !!19!! can be troublesome. But I had a brain wave: !!389 = 289+100!! is obviously a sum of two squares. And !!19!! is a !!4k+3!! prime, not a !!4k+1!! prime. So if !!389!! were divisible by !!19!! it would have to be divisible by !!19^2!!, which it obviously isn't. Tadaa, I don't have to use trial division to check if it's a multiple of !!19!!.

Well, that was not actually useful, since the trial division by !!19!! is trivial: !!389 = 380 + 9!!.

Maybe the trick could be useful in other cases, but it's not very likely, because I don't usually notice that a number is a sum of two squares.

[ Addendum 20230323: To my surprise, the same trick came in handy again. I wanted to factor !!449 = 400 + 49!!, and I could skip checking it for divisibility by !!19!!. ]

[Other articles in category /math] permanent link