Factoring Integers Using Digit Strings

September 21, 2013

I have been interested in the integer factorization problem for some time. There is a large variety of very interesting algorithms that have been proposed to factor integers. Despite the research done, it remains a very difficult problem. Recently I have been thinking about how the digits of a number are related to what divisors it has. I wrote a short paper exploring this.

What I considered was quite simple. As everyone knows, integers ending in a 0, 2, 4, 6, or an 8 are always divisible by 2. Integers ending in 0 or 5 are always divisible by 5. Nonzero integers ending in 0 are always divisible by 10. I was able to show why this is true. I also explored how this notion related to numbers in bases other than 10. I showed that numbers whose base is divisible by their rightmost digit are divisible by that digit. Interestingly, any nonzero integer ending in a 0 is divisible by the base it is represented in. I also found that a number is always divisible by the greatest common divisor of all of its digits. This idea also holds when strings of digits instead of individual digits are used.

You can view the paper I wrote here. There is really nothing novel or surprising about what I found. Indeed, the results are of very limited practical value. However, I found the process of showing the various properties interesting. I also found the generality of some of the properties surprising.