Dividing and conquering

By Burkard Polster and Marty Ross

The Age, 13 October 2008

Recently, we left you with the number 4187 to factorise. That was mean: factorising is very hard work. And it is good that it is so hard, as the difficulty of factorising is the basis of common encryption systems, used by banks and so forth. If you ever find an easy method, you could become an extremely rich outlaw.

However, though factorising is difficult there are tricks that can help. First of all, how high do we need to search? Suppose we look to write 4187 = A x B. Then A and B cannot both be bigger than √4187, since then their product would be too big. So, we need only hunt for factors up to just below the square root, in our case up to 64.

The second, easy observation is that we only have to check prime numbers. We might stumble upon a factor that is not prime, but this factor would always give rise to prime factors that are even smaller.

So, we’ve reduced our problem to checking 2, 3, 5, 7, 11, the primes up to 61. And some primes are easy. Since the last digit is a 7, we know immediately that 4187 is not divisible by 2 or 5.

Divisibility by 3 also has an easy trick: we sum the digits and check whether that sum is divisible by 3. So, 4+1+8+7=20: then, since 20 is not divisible by 3, neither is 4187.

Why do these divisibility tricks work? They all depend upon our base ten system of writing numbers. Since 2 and 5 go evenly into 10, all that matters is the last digit. For divisibility by 3, the key fact is that when 3 divides into any power of 10, the remainder is 1. This fact is also the key to “casting out nines”, a very old and very famous method for checking arithmetic.

Let’s postpone 7. For 11, the divisibility trick is to add the digits in the odd places, add the digits in the even places, and subtract the second number from the first. So, for 4187, we calculate (4+8) – (1+7) = 4: then 4 is not divisible by 11, and so neither is 4187.

In fact, any number has a divisibility trick, but some are messy and strange. Returning to divisibility by 7, the trick is to remove the last digit, double it and subtract from the remaining number. That’s a mouthful, but our example will make it clear.

For 4187, double the last digit 7 to give 14, and then subtract 14 from 418. This gives 404. Now repeat the process on 404: double 4 is 8, which subtracted from 40 gives 32. Since 32 is not divisible by 7, neither is 404, and in turn neither is 4187. Contact us if you want to know the explanation of this amazing process.

These beautiful divisibility tricks cannot disguise the reality that factorising is plain hard work. As it happens, 4187 = 53 x 79, a difficult one. But now that you are experts, you can definitely do some factorising of the famous number on Professor Euler’s credit card. And if you can factorise it completely? Then your life as a mathematical outlaw beckons.