I picked up Isaac Asimov’s Realm of Algebra, just since it’s been so long since school and I feel I need a refresher. In it, he says this (emphasis mine):
OK, the digits do add up to 39, which is divisible by 3, and 3 is indeed a factor of 24,577,761. But the digits in the other factor add up to 40, which is divisible by 4; but 8,192,587 is not evenly divisible by 4 (or 2).
I don’t remember ever hearing that a non-prime number could be factored by adding up its digits. (I haven’t bothered to figure out if 8,192,587 is prime or not.) But it seems to work. For example, I chose at random 2,055. The digits add up to 12. 3 and 4 are factors of 12, and 3 is a factor of 2,055. Using the same method, I found that 3 is also a factor of 3,558.
Is the ‘add up the digits’ method of factoring a number something that is taught? I just don’t remember hearing of this method.
The digits summing to a multiple of 3 works for 3. It is not a general method for factoring. Edit: it also works for 9. Other numbers have different rules. See Divisibility rule - Wikipedia .
That rule works for 3 and 9, not just any number. There are various divisibility tests for other numbers, see Divisibility rule - Wikipedia .
I’m not sure if it was ever part of a school syllabus, but certainly mathematics teachers mentioned in passing the thing about the digits adding up to 3.
That’s a lot of different rules. No wonder they were never taught.
Of course there’s the rule that even numbers are divisible by 2, numbers ending in 0 or 5 are divisible by 5, and numbers ending in 0 are divisible by 10. But in my imperfect (and aging) recollection, the others were not taught. But Asimov mentions it so casually that it seems that teaching more of the rules was common before I was born.
Here’s a quick argument why it works. For clarity, let’s assume it’s a four digit number abcd, though the same idea applies no matter how many digits there are.
The actual value of the number with digits a, b, c, and d is
1000a + 100b + 10*c + d
= (999 + 1)*a + (99 + 1)*b + (9 + 1)*c + d
= 999a + a + 99b + b + 9c + c + d
= 999a + 99b + 9c + a + b + c + d
= 9(111a + 11b + c) + (a + b + c + d).
In this last line, we have two things multiplied together. The first part is obviously a multiple of 9 (and hence, also of 3). If the second part, which is the sum of the digits, is also a multiple of 9 (or 3), then the whole thing is.
Another, related fact: If you add together the digits of any whole number, and then add together the digits of that, and so on, until you’re down to a single digit, then that digit will either be 9, indicating that the original number is evenly divisible by 9, or it will be the remainder left over from dividing that number by 9.
This is the basis for the arithmetic-checking procedure known as “Casting Out Nines.” Interestingly, the page I linked to introduces the topic with a complaint from a math student who was never taught the technique and had to stumble across it in a book by Isaac Asimov.
The reason it works is because 9 is one less than 10, which is the base for the decimal system. Any divisor of 9 will have this property, so 3 and 9 (and, trivially, 1) all have this property.
If you used base 13, for example: 12 is one less than the base, so 2, 3, 4, 6, and 12 will all have this property in base 13.
Also, the reason you can just look at the last digit to test for divisibility by 2 or 5 (or 10) is because they all divide the base (10).
If you used base 12, for example, you could tell if 2, 3, 4, 6, or 12 divide an integer simply by looking at the last digit.
Another interesting tidbit, involving numbers with 4 or more digits:
Write down the last 3 digits, then subtract whatever is before it. (The simplest cases are when there are no more than 6 digits altogether.) For example, 17,724. 724 minus 17 is 707. This is evenly divisible by 7, and so we can be sure that 17,724 is also divisible by 7. 17,725 would have 1 left over, and so would its result: 708.
But it gets more interesting.
The same thing can be done with 11 and 13!
The reason? 1001 is the product of 7, 11, and 13!
(Eleven is a special case. There are actually two other methods for checking divisibility by 11, but I don’t want to confuse people anymore than they are already confused.)
The way I think about the “divisible by 3” trick is that, mod 3, any power of 10 is congruent to 1. This means that an integer is congruent to the sum of its digits mod 3. For example, 7182 = 7000 + 100 + 80 + 2 = 7 * (1000) + 1 * (100) + 8 * (10) + 2 * (1). Taking this mod 3 we have 7 + 1 + 8 + 2 = 18 which is 0 mod 3, so the original number is also 0 mod 3 (i.e. divisible by 3).
Note, by the way, that these clever little tricks only apply for relatively small factors. If I were to ask you to factor, say, 629804429, you would have to check each and every prime number up to 16747 as a potential factor before you discovered that 629804429 = 16747 * 37607 . There aren’t any major shortcuts known for factoring in general, which makes it a very difficult problem to solve, but such a problem can be set up relatively easily (I set up that example in about five minutes just now, using a non-programmable pocket calculator). Because of this, the problem of factoring is used in most modern secure encryption schemes: Basically, you can quickly encrypt a message by setting up a factorization problem, and if someone knows the correct factors in advance they can quickly solve the problem to read the message, but anyone who doesn’t know the answer in advance has an extremely difficult time solving the problem and thus reading the message.
I’m not sure how much of simplification you are intending in your post here, so pardon me if I’m “correcting” something that’s just you being terse.
You don’t “have” to test all primes up to the square root. The most efficient known factoring method, the general number field sieve only tests a small subset of special primes in the range. Which is a major shortcut, but still not polynomial time.
Actually, I wasn’t aware of that algorithm. It’s still a pretty ugly problem, though.
And I take it for granted that folks around here will correct oversimplifications, so you shouldn’t have to beg pardon even if I had already known about that method.