The Clever Way

When I give talks on factoring, I often repeat an incident that happened to me long ago in high school. I was involved in a math contest, and one of the problems was to factor the number 8051. A time limit of five minutes was given. It is not that we were not allowed to use pocket calculators; they did not exist in 1960, around when this event occurred! Well, I was fairly good at arithmetic, and I was sure I could trial divide up to the square root of 8051 (about 90) in the time allowed. But on any test, especially a contest, many students try to get into the mind of the person who made it up. Surely they would not give a problem where the only reasonable approach was to try possible divisors frantically until one was found. There must be a clever alternate route to the answer. So I spent a couple of minutes looking for the clever way, but grew worried that I was wasting too much time. I then belatedly started trial division, but I had wasted too much time, and I missed the problem. …

The trick is to write 8051 as 8100 – 49, which is 902 – 72, so we may use algebra, namely, factoring a difference of squares, to factor 8051. It is 83 × 97.

— Carl Pomerance, “A Tale of Two Sieves,” Notices of the AMS 43:12 (December 1996), 1473-1485