Crazy Math

O.k., back to factoring. Chances are you're familiar with at least one set of figurate numbers -- the squares:

1, 4, 9, 16, 25, 36, 49, etc...

The sequence of squares can be generated very easily through addition; simply add up x number of odd numbers (starting with 1) to find x^2:

1^2 = 1
2^2 = 1 + 3
3^2 = 1 + 3 + 5
4^2 = 1 + 3 + 5 + 7
etc...

There are many other "kinds" of figurate numbers, but they all have the same simple rule for generating them. Here are a couple of examples:

triangle numbers:
-----------------
1 = 1
3 = 1 + 2
6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
etc... (see http://www.research.att.com/~njas/sequences/A000290)

square numbers:
---------------
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
etc... (see http://www.research.att.com/~njas/sequences/A000290)

pentagonal numbers:
-------------------
1 = 1
5 = 1 + 4
12 = 1 + 4 + 7
22 = 1 + 4 + 7 + 10
etc... (see http://www.research.att.com/~njas/sequences/A000326)

And so on. Essentially, if you successively add any sequences of constant-spaced integers starting at 1, you'll get some sort of figurate number.

Why are figurate numbers important? First off, most modern factoring methods rely on a simple observation by Fermat, namely that if you can solve:

x^2 - y^2 = N

Where N is some number you want to factor, then you can find the factors of N directly using x and y, since x^2 - y^2 factors into (x+y)(x-y). This has been modified slightly for current factoring methods to read:

x^2 = y^2 mod N

Which means "x^2 is congruent to y^2 modulo N". One way to think of it is if you divide x^2 and y^2 by N then you get the same remainder:

16 = 25 mod 9 --> 16/9 = 1 remainder 7, 25/9 = 2 remainder 7.

Then plug in:

(4+5) = 9; (5-4) = 1

In this case we discovered a "trivial" solution; all integers have them. Here's an example of a non-trivial case:

64 = 4 mod 15 --> 4/15 = remainder 4, 64/15 4 remainder 4.

Plugging in we get:

(8 - 2) = 6; (8 + 2) = 10;

Ack, you may be thinking, neither of those numbers divide 15! This is true, but they each share at least one divisor with 15. So we compute the Greatest Common Divisor (gcd):

gcd(15,6) = 3; gcd(10,15) = 5

I won't go into it here but computing the gcd is very easy (it's based on the Chinese Remainder Theorem).


What about all of those other figurate numbers? Let's examine for a moment what x^2 - y^2 = N represents in terms of the "figurate representations" of x, y, and N. For instance, let x = 8, y = 2, and N = 60:


1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
1 + 3 = 4
-
----------------------------------------
5 + 7 + 9 + 11 + 13 + 15 = 60


Notice that the figurate representation of 60 consists of 6 integers. That number 6 isn't a coincidence -- the length of any figurate representation that's greater than 2 will be a number that shares a divisor with N. In other words 6 and 60 share a divisor (in this case 6 divides 60). So do 8 and 64. Some other examples:

5+7+9+11 = 32, 32 shares a divisor with 4
4+5+6+7 = 22, 22 shares a divisor with 4
4+7+10+13+16+19+22 = 91, 91 shares a divisor with 7

Hence if we can find any figurate representation of N with length greater than 2, we can factor N. That is, essentially, what x^2 - y^2 = N means; you're finding a "difference of squares" that represents a valid representation of N with a length greater than 2. So we can then replace any other figurate number into Fermat's equation and it still holds true. Let F_a(n) represent the nth figurate number of "order" a; F_1(n) is the nth triangle number, F_2(n) is the nth square number, and so on. Then Fermat's equation can be rewritten as:

F_a(x) - F_a(y) = N

And, (I believe, I have yet to write out the proof although it should be fairly trivial) the modern modification of Fermat's equation should also hold for all F_a(n):

F_a(x) = F_a(y) mod N

The inclusion of other figurate numbers in these two equations is the basis for my various attempts at cracking the factoring problem.