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:
- Add or subtract any multiple of P.
- Multiply or divide by any number that isn't a multiple of P.
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.
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:
- 2? 8507 ends in 7, so it's not divisible by 2.
- 3? 8+5+7 = 20, which is not a multiple of 3, so 8507 isn't divisible by 3.
- 5? 8507 ends in 7, so it's not divisible by 7.
- 7? 8507 ends in 7, so we subtract 7*1 = 7, and remove the 0's to get 85. I know this is 5*17 and thus not divisible by 7, but if you don't, you can subtract 7*5 = 35 and remove the 0 to get 5, so 8507 is not divisible by 7.
- 11? 8507 ends in 7, so subtract 11*7 = 77 and remove the 0 to get 843. That ends in 3, so subtract 11*3 = 33 and remove the 0 to get 81. I know that's 3^4, but you could also subtract 11*1 = 11 to get 7. 8507 is not divisible by 11.
- 13? Subtract 13*9 = 117 and remove the 0 to get 839. Then subtract 13*3 = 39 and remove the 0s to get 8, which is not divisible by 13. 8507 is not divisible by 13.
- 17? There's actually a trick we can use here: 17*5 = 85, so we can actually subtract 85 from the left of the number (equivalent to subtracting 8500) to get 7. That is of course not divisible by 17, so neither is 8507.
- 19? Subtract 19*3 = 57 to get 845. Subtract 19*5 = 95 to get 75. You can know that 75 = 3*5*5, or notice that 75 is smaller than 19*10, so it can only be divisible by 19 if it is equal to the multiple that ends in 5 (that is, 95), and it isn't. 8507 is not divisible by 19.
- 23? Subtract 23*9 = 207 to get 83 (remove an extra 0). Remove 23 to get 6. 8507 is not divisible by 23.
- 29? Subtract 29*3 = 87 to get 842. Subtract 29*8 = 232 to get 61, which is prime. 8507 is not divisible by 29.
- 31? Subtract 31*7 = 217 to get 829. Subtract 31*9 = 279 to get 55, which is 5*11. 8507 is not divisible by 31.
- 37? Subtract 37*1 = 37 to get 847. Subtract 37*1 = 37 to get 81, which is 3^4. 8507 is not divisible by 37.
- 41? Subtract 41*7 = 287 to get 822. Subtract 41*2 = 82 to get 74, which is 2*37. 8507 is not divisible by 41.
- 43? Subtract 43*9 = 387 to get 812. Subtract 43*4 = 172 to get 64, which is 2^6. 8507 is not divisible by 43.
- 47? Subtract 47*1 = 47 to get 846. Subtract 47*8 = 376 to get 47. Aha! 8507 is divisible by 47! And what is the quotient? We can just assemble the numbers we multiplied by 47 in reverse order to get it: 1, 8, and the implied 1 at the end gives 181. 8507 = 47 * 181. And, since 181 is much smaller than 47^2, and we have checked every smaller prime already, we can immediately conclude that 181 is prime and we are done.
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:
- The method I've described, as written, involves subtracting a multiple of P with the same last digit, getting a number that ends with 0, and then dividing by 10. This can be done a bit faster by just ignoring the last digit from the start. For instance, 8507 minus 287 and then divided by 10 should be calculated as 850 minus 28, or 822. And when you're working out or remembering a product like 41*7, you don't need to worry about the last digit since you know what it's going to be - think 28, not 287.
- Learn all the primes up to at least 100, to prevent having to check them as you go along. There are only 25 of them (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) so it's not that bad. It's also doable to memorize the factorization of numbers up to 100, or at least which primes greater than 5 divide each number, since that's what matters here.
- Note that you can add a multiple of P instead of subtracting one. In some cases, this can be quite a bit easier. Ffor instance, instead of subtracting 9*P, you can add P, or instead of subtracting 8*P, you can add 2*P. If you do find a factor this way, though, it can be a little more confusing to find the quotient. For instance, let's divide 8507 by 47 again. We subtract 47 to get 846, then add 2*47 = 94 to get 94, which is 2*47. But then the quotient has to be worked out as 200 - 20 + 1 or 181 - the minus 20 is because 2*P was added, not subtracted.
- Some primes have slightly faster divisibility methods or tricks that you can learn to save a little time. Here are a few tricks: (a) Ffor divisibility by 11, you can use the alternating digit sum: add one digit, subtract the next, add the next, and so on, and see if the result is divisible by 11 or not. For 8507 it would be 8 - 5 + 0 - 7 = -4 which is not divisible by 11. (b) For dividing by 37, since 111 is divisible by 37, you can always subtract a multiple of 111 instead of the smallest multiple of 37. For numbers like 6551 that can save a lot of time. (c) 1001 is 7*11*13, so when P is one of those primes you can subtract a multiple of 1001 from N.
- Learn more tricks to tell when N is clearly not divisible by P. For instance, if N is less than 10*P, and the multiple of P ending with the same digit as N is not equal to N, N is not divisible by P. Or, if N differs by any one digit from a multiple of P, and P is at least 11, N is not divisible by P.
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.