Complex factoring

From Math

Revision as of 14:20, 20 February 2015 by JoDu (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

In progress

I factored a recent Composite of the day by using imaginary numbers, which I think is pretty cool.

The number was 9509, which I noticed immediately is 972+102. Once I know this, I know how to factor it in the "complex plane" (that is, using numbers that have an imaginary part): 9509=(97+10i)*(97-10i), where i=-1. Numbers like 97+10i are called Gaussian integers. If you don't understand why 9509=(97+10i)*(97-10i), but are still interested in this post, you should take a minute to figure it out.

Once I noticed that 9509=972+102, I thought that if I could find another way to write it as the sum of two squares, this would give me an easy way to factor the Composite of the day (which is of course an important goal). You'll see below why two decompositions allow me to find the factors.

I found 9509=952+222=(95+22i)*(95-22i) pretty easily, using a counting trick that I happen to know.

Once I had these two decompositions, I was very happy, because I also happen to know that the Gaussian integers have "unique factorization": each Gaussian integer can be written as the product of Gaussian integers in a unique(-ish) way. So it must be possible to break down the two products above — (97+10i)*(97-10i) and (95+22i)*(95-22i) — into the same list of smaller factors, which can then be rearranged and multiplied to find the real factors.

This means, in turn, that (for example) 97+10i must be factorable. We write 9509=(95+22i)(95-22i)=xx¯, where the bar refers to the complex conjugate (that is, the relationship between 95+22i and 95-22i). Then we know that xx¯ can be factored into aa¯bb¯, and that these factors can be rearranged to make the product (97+10i)(97-10i)=ab¯*ba¯, or to make the unknown real factors of 9509 (which will come out as aa¯*bb¯, since we know that we can always get a real by multiplying a complex number by its conjugate.

So if 95+22i is ab, and 97+10i is ab¯ (for example), then we should be able to find a by finding their common factor. The way to find common factors is by using linear combinations to make smaller numbers. For example, we can subtract one number from the other to get 2-12i. From there, we could keep going to get the common factor (this is called the Division algorithm), but we're really already done. 2-12i is 2*(1-6i) Since we know 2 doesn't divide 9509, the common factor must be in 1-6i. And since that number times its complex conjugate is 37, a prime, 37 must be the factor we're looking for.

We could now divide 9509 by 37, to finish factoring the composite of the day. But that would be a bit boring. The other thing we could do is the same trick over again. Starting instead with 95-22i and 97+10i, we subtract to get 2+32i. Factoring out 2 again, we notice we have a prime product again: 1+16i times its complex conjugate is 257. So we conclude that 9509=37*257.

I find it pretty cool that this works