On this page I will analyse the factorization of 2^{m}  1. This page is not in chronological order.
On January 12th 2007, I wrote down the factorization of 2^{m}  1 for m=2...16 because I was interested to see where a factor of the form 2^{n} + 1 would appear. I took the piece of paper to bed with me, to study it, when suddenly I saw structure (conjecture 1, with n equal zero). I got out of bed again and copied the factorization of 2^{m}  1 for m=17...36 as well. Back in bed, I verified that my conjecture still held and discovered the structure of conjecture 1 with n=1 (and a single data point with n=2). I studied the remaining factors and discovered they all had the form (c m + 1) (conjecture 2). I didn't sleep much that night.
The next day I wrote a program (factorization2.cc) that used conjecture 1, and refined this conjecture in it's current form (still without proof). Then I extended the program to find the factorization of the remaining factors using brute force, which worked extremely fast till m=58 and reached m=82 over night. Studying 2^{11}  1, I realized that the binomial expansion of (1+1)^{11} might be relevant and I thought that if I understood why the remaining factors were all of the form (c m + 1) then I might discover a way to find those factors a lot faster. In the next few days I extended the program to use the Cunningham tables in order to have the factors up till 2^{787}  1 available, giving me a large control set. I also proved conjecture 1 to hold for n=0 and n=1.
Larger values turned out to be very hard to prove. I downloaded a trial version of Mathematica on January 17th, and started to learn how to use it. After a few days I could calculate the remainder of (x^{km}  1) / (x^{m}  1)^{n}, but only for fixed values of k, m and n. Nevertheless, by using a few prime values for m and very large values for k, I was able to guess a form for the remainders as polynomials in k for n=2...6. This remainder contained a lot of fixed numbers that I couldn't place for several days until finally I plotted the polynomials of k, that I had fit to the data, and found that for constant n they all crossed the same n+1 points. Rearranging things a bit I then formulated the "Pink polynomials" and the next couple of days derived a general form for them.
Having this general form, I was able to prove the correctness of conjecture 1 for n=2...5. A day later I added the last part and finished the proof for arbitrary n. Conjecture 1 was now proved. This was today January 23th, at which point I started to write this document. Anything else will be chronological, adding it as I move forwards.
The actual proof of conjecture 1 is impossible if you do not first know the answer. It took three weeks to find that answer (it is now Februari 17th). It would take too long to show the path followed that lead to the answer. However, I wish to thank Neil Sloane for an important contribution that led to this result, by finding a way to generate a pyramid of integers that I had generated along the way.
Let k, m, n be nonnegative integers, x an integer larger than 0, and p prime. If and then .
If x = 1, k = 0 or m = 0 there is nothing to prove. Therefore consider the case where x > 1, k > 0 and m > 0.
Let u = x^{m}, thus u > 1. It won't be used that u is a power of x until at the end of the proof.
Let n be a nonnegative integer, and recall that
 (1) 
and
 (2) 
Consider the equation
 (3) 
which defines the function R_{n,k}(u),
 (4a) 
Using (1), we can work out the sum
 (5a) 
This sums over 0 <= j <= n and 0 <= i < kn.
What we'd like is to sum over i+j. Let r = i+j with a total range of 0 <= r < k. Because the binomial is zero for values of j < 0 and j > n, we can savely replace the sum over j with a sum over r, so that (5a) becomes,
 (5b) 
Where the first binomial will be nonzero only when 0 <= ri <= n and the second binomial will be nonzero only when n <= k1i. In otherwords, the only nonzero terms are those when max(0,rn) <= i <= min(r,kn1). If kn1 < r but we sum till r anyway, then this is no problem because for values of i > kn1, the second binomial is zero anyway. Therefore we can sum over max(0,rn) <= i <= r. This then suggests we should split the sum into two parts, one where r < n and one where r >= n.
 (5c) 
Using the identity [KNUTH, 5.43], we can rewrite the inner sum of the second term as
 (6) 
Now we can rewrite (4), using (2), (5c) and (6) to read
 (4b) 
where is the Heaviside step function,
 (7) 
Define for nonnegative k and 0 <= i < n, the family of functions
 (8) 
Then we can write R_{n,k}(u) as
 (4c) 
Note that because the sum in (8) is empty for k <= n, we found that
 (9) 
We can rewrite the sum in (8) a bit. Note that, using [KNUTH, 5.43] again,
 (10) 
and thus, if kn1 <= i,
 (11) 
Then note that the value of k1j in the last binomial factor of the last sum is maximal when j is minimal. This minimal value is kn, thus the maximum value of the k1j is k1(kn) = n1, rendering this binomial, and therefore the whole sum, zero provided that k1j >= 0 for all values of j. The minimal value of k1j is obtained for j = i, so that we can conclude that the second sum is zero if k > i.
While if kn1 >= i then (10) can be written as
 (12) 
because for all values of j.
Hence, we have
 (13) 
And, with k >= 0, we can write (8) as
 (14) 
Lets try to write P_{i,n}(k) as a finite sum of powers of k. We can find the highest power by using the finite difference method. This method shows that we can write a sequence as a polynomial of degree n, if the nth difference gives a constant sequence. As we can learn from this wikipedia reference about the nth difference operator , there exists a formula that will give us directly the dth difference:
 (15) 
Because of (9) we known that the degree is at least n. Experimentally fitting polynomials to calculated data gives polynomials of exactly degree n that are correct up till very large k. This motivates us to try d = n and calculate , using (9) and the identity from wikipedia for the last step, to get
 (16) 
If this is to be a constant (with fixed i and n) for larger values of k, then we have proven that P_{i,n}(k) can actually be written as a polynomial in k of degree n. That is, we have to show that for k >= n, , where is given by the recurrence
 (17) 
As follows directly from (9), . In fact, P_{i,n}(k) = 1, if i < k <= n, and as follows directly from (15), depends only on the values of P_{i,n}(r) with k <= r <= k+d, so that , if i < nd <= n. Moreover, as also follows directly from (9), P_{i+1,n+1}(k+1) = P_{i,n}(k), for 0 <= k <= n, because if you add one to k and n then k is still less than or equal n so that (9) still holds, and H[k1i] doesn't change. Thus we have the identity , if 0 <= k <= n  d, which translates into , if d > 0 and i >= nd. Note that d = 0 fails because (9) demands that i < n, thus n > 0, and (16), which we'll need, puts d = n. Combining, we find that
 (18) 
Thus, using (16), and realizing that if d > 0 and i < n  d, we can rewrite (17) as
 (19) 
where as usual, 0 <= i < n and k >= 0.
Actually, if the binomial was correctly defined for negative values, the separation for d = 0 wouldn't have been necessary. According to me, the correct definition of a binomial of two negative values is , and thus, for d = 0, we have .
As an example, consider the following solution to D_{3,8}(d, k).
where k runs from left to right from 0 till 11, and d runs from top to bottom from 0 till n = 8. The top row is therefore P_{3,8}(k) and the first n+1 = 9 values equal H[k1i] = H[k4]. The bottom row is D_{3,8}(8,k) = (1)^{n1i} = (1)^{(813)} = 35.
Since the last identity of (19) holds everywhere, it is actually easiest to generate D from the bottom line and the first column. The first column is
 (20) 
If binomial had been defined correctly for negative values, then the special case for d = 0 would not have been necessary. Unfortunately, it is. Therefore things are easier if we redefine D as
 (21) 
This obviously has no influence on the values of D for d > 0, while the top row is simply reduced with 1.
It's not hard to see that this will make life a lot easier. The recurrence rules that generate D^{1} do not have any special cases.
 (22) 
It's not hard to construct D^{1}_{i,n}(d,k) from this. Each value in the left column gives an independent contribution that adds up to the rest. Consider a single 1 in the left column (with a row of zeroes below it). This would lead to:
from which we clearly see that a 1 in row j contributes to D^{1}_{i,n}(d,k). Moreover, since it's all addition, every additional 1 that is added to the same row in the first column gives the same contribution. Hence, a value x in row j contributes to D^{1}_{i,n}(d,k). "Summing it all up" gives us the result
 (23) 
And thus we found that
 (24) 
which proves that P_{i,n}(k) can be written as a polynomial in k of degree n. In fact, we can write it as a product of k and a polynomial of degree n1 because P_{i,n}(0) = 0 for any i and n. Define
 (25) 
with coefficients c(s,i,n) that later will turn out to be integers (thanks to the wise choice of deviding by n! outside the sum).
Filling this in into (4c) gives
 (26) 
where
 (27) 
 (1) 
p devides x^{m}1, thus p^{n+1} devides the first term. What remains is to prove that p^{n} devides the second sum. As was shown before, k devides and thus the second sum, and p^{n}  k, so we are done.
I ran into these functions, basically by first finding the polynomials for n=1...6 given below and then discovering a structure in them. I named them "Pink" polynomials for an obvious reason. The 'P' stands for Polynomial.
The canonical definition of the Pink polynomial is that they are polynomials in the variable k, of degree n, defined for , where
 (1) 
The polynomials can be constructed in the following "brute force" way,
 (2) 
where the first product takes care of the zeroes between 0 and i, while the sum takes care of the ones between i and n.
If 0 k i, then one of the factors of is zero, and therefore (2) is zero, while if i < k n, then each of the terms of the sum is zero except the one where j = k. Therefore (2) becomes k!/(k(i+1))! (1)^{n+k} n!/(k! (nk)!) (k(i+1))! (1)^{nk} (kn)! /n! = 1.
Here is a list of all Pink polynomials for n <= 6,

The Pink polynomials have the following properties.
, as follows directly from the definition (1). In other words, they all have k=0 as zero and thus k as factor.
The polynomials can be written as k/n! Q(k) where Q(k) is a polynomial of degree n1 over . This follows trivially from (2).
 (3) 
Since Q(k) is a polynomial of degree n1, we should also be able to write this as,
 (4) 
Where the c_{s} are the coefficients of the polynomial.
For , define
 (5a) 
Since this function is my own invention, allow me to give a quick overview of some of it's characteristics,
 (5b) 
P.S. It turns out that the are known as the unsigned Stirling numbers of the first kind: .
It can be derived that
 (6) 
from which we can conclude that for
 (7) 
Hence, we can rewrite (3) as,
 (8) 
and thus found an expression of the of (4),
 (9a) 
Map j > j+i+1, r > r+s+i+1n, l > l+f then z > z+j+i+1n, then h > h+sz to get,
 (9b) 
We might as well start the sum over f from ((n1i)j)h because for smaller f, zhf > z((n1i)j) and the subsequent binomial is zero anyway. Map f > f+((n1i)j)h to get something that starts at 0 again and we have,
 (9c) 
Apparently it makes more sense to number i and s the other way around. Let , . Also inverse j and r, and replace some binomials with .
 (9d) 
where the last (actually, non trivial) transformation makes sure that is never called with negative arguments. Nevertheless, now it is apparent that we can simplify this even more by also inverting r (relative to ). This then gives
 (9e) 
Filling in k = 0 in (7), and replacing a with a gives the relationship:
 (10) 
The sum over i of the constant term of each Pink function, , equals n factorial.
where the last step is due to the wellknown fact that for .
and therefore k devides , where the c_{i} are integer constants, for any value of (and any n).

New identity used: Integers n,m,a
if a > 0.