A Method for Mentally Factoring

This is a method I independently came up with for factoring numbers of three, four, or even five digits in your head, often in just a few minutes. It doesn't require large amounts of memorization or extreme mathematical ability. The ideas behind this technique are not new, and I am almost certainly not the first to think of it, but it probably isn't known to very many people.

The general idea is to check every possible prime divisor, a process known as trial division. We check if our number is divisible by 2, by 3, by 5, and so on, and if we find a factor, we divide it out and try it again, only moving to the next prime when the current one doesn't evenly divide our number anymore. We stop when we are at or above the square root of the current number, because that means the number is too small to be the product of two or more primes. So far this is all pretty standard. For a quick example, let's take 140; we can divide by 2 to get 70, and then divide by 2 to get 35, which isn't divisible by 2, so we move to the next prime, 3. It also isn't divisible by 3, so we move to 5, and 35 is indeed divisible by 5, so we divide it by 5 to get 7. The square root of 7 is less than 5 (or alternately, 5^2 is more than 7) so we know 7 is prime and we can stop factoring. The factorization is 140 = 2*2*5*7.

The special part in my method is the way I do the division. First, some quick notation: the number we are currently checking is N, the prime we are using is P, and the | symbol means "divides", as in 3 | 6 (that is, 6 is a multiple of 3). So, let's start checking our number N for divisibility. We can immediately tell if N is divisible by 2 or 5 by looking at the last digit. As for 3, you can just add up the digits and see if the sum is divisible by 3 or not. (The way I actually do that is to add a 1 for each 1, 4, or 7 and a -1 for each 2, 5, or 8, and see if the sum is divisible by 3.) But for larger values of P there is no easy way to check if P | N, other than long division, right?

Making N Smaller and Smaller

We will see if P | N for a relatively large N by making N smaller and smaller until the question is obvious. But wouldn't using a smaller N just give you a different answer? The trick is that, as long as P is a prime number - and it always will be in this method - there are several things we can do to N, without affecting whether it is divisible by P or not. The important ones are the following two:

So, all we have to do to find out if P | N is to apply those two operations, specifically subtracting some multiple of P and dividing by a non-multiple, to N over and over. When it gets small enough that the answer is obvious, we are done. By obvious, I just mean you know it without too much thought, and for me that usually means that N is smaller than P, or too close to (less than P away from) a multiple of P you know, or when I know the prime factors of N and they don't include P.

Dividing From the Right

The process for checking if P | N is a mechanical algorithm which is similar to long division, except that it goes from right to left and involves less guessing. Because P is a prime and not 2 or 5 (we're only using this method for primes 7 or larger), it must end with a 1, 3, 7, or 9. And that means that for every digit from 1 to 9, there is exactly one number from 1 to 9 that P can be multiplied by to make it end in that digit. Specifically, you can use the following table to find that number. The topmost row is the digit you want, and the leftmost column is the last digit of P.

123456789
1123456789
3741852963
7369258147
9987654321

To do a right-to-left division, start with the number N and look at the last digit. Find the multiple of P that ends with the same digit, and subtract it out. Now the new N ends in 0, so we can divide by 10 until it doesn't - since P is not 2 or 5, 10 is not a multiple of P. The new N is at least one digit smaller than the old one, so we can just keep doing this until it is small enough to tell if it is a multiple of P or not. Since those operations we did don't affect whether P divides our number, we know whether P | N or not, because it's the same answer we just got.

Let's Do an Example

Let's see this in practice. We'll use a moderately large number: 8507. You can quickly tell that it's less than 100^2 (10000) and more than 90^2 (8100), so without having to do an exact square root we know that if we check all the primes up to 100 we can be sure the number is prime. So let's check them, starting from 2:

Speeding Up the Process

This is a pretty decently fast process already, once you get used to it. However, there are also some quick changes that will make this a bit faster without much work:

Prime Tables

If you want to get really fast at this, for some sort of mental math competition or performance, the best way (short of memorizing the factors of every number you might be given) would be to construct and memorize a table like this. The topmost row is the last digit of N, and the leftmost column is the prime P. You only need to remember the underlined part, since the last digit is the same every time.

123456789
7214263143556072849
11112233445566778899
1391521310465261177839
175110215334851361768119
191711521331149576573819
2316192231841154620713869
29261232203174145116875829
31316293124155186217248279
371112223337418529637148259