Cunningham Numbers

I've come across Cunningham Chains before and written about them in several posts. However, I've not written about Cunningham Numbers before. These numbers always occur in pairs and the previous such pair was 25920 and 25922 that can be represented as \(161^2-1\) and \(161^2+1\) respectively. Today I turned 26243 days old and this is equal to \(162^2-1\) and the other member of the pair is 26245 equal to \(162^2+1\). So what defines such numbers. 

Here is a definition: Cunningham numbers are a simple type of binomial number, they are of the form$$b^n\pm1 \text{ where }b \text{ and } n \text{ are integers and }\\b \text{ is not a perfect power. They are denoted by }C^±(b,n)$$

Establishing whether or not a given Cunningham number is prime has been the main focus of research around this type of number. Two particularly famous families of Cunningham numbers in this respect are the Fermat numbers, which are those of the form \(C^+(2,2m) \), and the Mersenne numbers, which are of the form \( C^−(2,n) \).

Primes of the form \(C^±(b,n)\) are very rare. To quote from WolframAlphaMathWorld:

A necessary (but not sufficient) condition for \( C^+(2,n)=2^n+1\) to be prime is that \(n\) be of the form \(n=2^m\). Numbers of the form \(F_m=C^+(2,2^m)=2^{2^m}+1\) are called Fermat numbers, and the only known primes occur for:

• \(C^+(2,1)=3\)
• \(C^+(2,2)=5\) 
• \(C^+(2,4)=17\) 
• \(C^+(2,8)=257\)
• \(C^+(2,16)=65537\)

In other words for \(m=0, 1, 2, 3, 4 \). The only other primes \(C^+(b, n)\) for nontrivial \(b \leq 11\) and \(2 \leq n\leq 1000\) are:

• \(C^+(6,2)=37\) 
• \(C^+(6,4)=1297\) 
• \(C^+(10,2)=101\) 

\(C^+(2,n)=2^n+1\) is always divisible by 3 when \(n\) is odd. The Mersenne numbers \(M_n=C^-(2,n)=2^{n}-1\) are known to be prime only for 44 values, the first few of which are \(n=2, 3, 5, 7, 13, 17, 19, ... \) (OEIS A000043). Such numbers are known as Mersenne primes. There are no other primes \(C^-(b,n)\) for nontrivial \(b \leq 20\) and \(2\leq n\leq 1000\).

If primes are rare amongst the Cunningham numbers, then most are composite and thus factorable which leads us into the Cunningham Project:

The Cunningham project is a project, started in 1925, to factor numbers of the form \(b^n ± 1\) for \(b\) = 2, 3, 5, 6, 7, 10, 11, 12 and large \(n\). The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall. There are three printed versions of the table, the most recent published in 2002, as well as an online version.

Figure 1 shows the current limits of the exponents:

Figure 1

Two types of factors can be derived from a Cunningham number without having to use a factorisation algorithm: algebraic factors, which depend on the exponent, and Aurifeuillian factors, which depend on both the base and the exponent.

Perhaps, I'll explore the topic of factorisation of Cunningham numbers in more detail at a later date. For the moment, it can be noted that:

Once the algebraic and Aurifeuillian factors are removed, the other factors of \(b^n ± 1\) are always of the form \(2kn + 1\), since they are all factors of \(\displaystyle \Phi _{n}(b) \). 

When \(n\) is prime, both algebraic and Aurifeuillian factors are not possible, except the trivial factors \(b − 1\) for \(b^n − 1\) and \(b + 1\) for \(b^n + 1\).

In general, all factors of $$ \frac{b^n − 1}{b − 1}$$ are of the form \(2kn + 1\), where \(b ≥ 2\) and \(n\) is prime, except when \(n\) divides \(b − 1\), in which case $$ \frac{b^n − 1}{b − 1}$$ is divisible by \(n\) itself.

Of course, for the pairs of Cunningham numbers mentioned earlier ((25920, 25922) and (26243, 26245)), the value of \(n\) is 2 and hence prime. This means that there are no algebraic or Aurifeuillian factors, only the trivial factors and factors to the form \(4k+1\). The factorisations are:

• \(25920 =161^2-1=160 \times 162=2^6 \times 3^4 \times 5\) 
• \(25922 =161^2+1=2 \times 13 \times 997\) 
• \(26243 = 162^2-1=161 \times 163=7 \times 23 \times 163 \)
• \(26245 = 162^2+1=5 \times 29 \times 181\)