June 26th, 2007

Factoring numbers

Non-math-geeks: Now is the time to turn away and shun this post. Math Geeks: Read on.

Today at lunch my friend Ojo, of The Collective Noun Page fame, was telling me how to "easily" tell if a number was divisible by a prime. He had a trick all the way up to 31, and was telling me there was a formula to figure it out.

First take a number N.

We can write N as (10x + y) where x = N/10 and y = N%10.

Next you can say for any prime P, N is divisible by P iff 10x + y is divisible by P.

Furthermore you can say (10x + y) is divisible by P iff (ax + by) is divisible by P then solve for a and b.

For example for P = 3 a = 1 and b = 1. So if we take 132 we get ((1)13 + (1)2) = (13 + 2) = 15, which is divisible by 3, so 132 is divisible by 3.

I was trying to figure out how you solve for a and b, but he had done it so long ago that he had forgotten the general formula. He did remembered that a was always 1 or -1.

I was wondering if there was more math behind this, so I chatted later with the best math geek I know, Veloso, and discovered the wonderful world of modulo arithmetic.

To use my expression from above.
N = (10x + y)
Now we want to say, in our fancy new modulo arithmetic that, (10x + y) is congruent to 0 mod P, where P, again, is the prime we care about. In short hand we can write: (10x + y) == 0 mod P.

This gives us the form we care about, mainly (ax + by) == 0 mod P, where a and b are 10 and 1 respectively.

Since we have the proper form all we need to do is figure out what number to multiple both sides of the equation such that 10 turns into 1.

This is where multiplicative inverses come in. It turns out that if J < K, and J and K are coprime, then there exists an M such that J*M == 1 mod K.

Going back to our problem of (10x + y) == 0 mod P, we plug it in and get 10*M == 1 mod P, now we just need to solve for M once we know P.

This is easily done with the Extended Euclidean Algorithm (EEA).

The EEA takes two integers and returns you two integers
EEA(r,t) returns c,d which means
r*c + t*d = 1
When you take this equation modulo t you get:
r*c + t*d == 1 mod t
Which can be simplified to
r*c == 1 mod t

This is great for us. We can just use EEA(10, P) the first number returned will be M.

Now we can say the following. For any P which is prime. N is divisible by P iff x + My == 0 mod P, where x = N/10, y = N%10, and M,Q = EEA(10,P), and we don't care about Q.

Well almost. If P is 2 or 5, it doesn't work. Remember that for the multiplicative inverse to work the numbers have to be coprime. Obviously 2 and 5 are not coprimes with 10. No problem though for 2 and 5 we can just brute force the answer. Again using the equation (ax + by) == 0 mod 2, we can just set a = 0, and b = 1. The same for 5. Which is saying that if the last digit of the number is divisible by 2 or 5, then the number is divisible by 2 or 5.