Editing Cunningham Project (section)

==Factors of Cunningham number==
Two types of factors can be derived from a Cunningham number without having to use a [[Integer factorization#Factoring algorithms|factorization algorithm]]: [[algebra]]ic [[factorization|factors]] of [[binomial number]]s (e.g. [[difference of two squares]] and [[sum of two cubes]]), which depend on the exponent, and [[Aurifeuillean factorization|aurifeuillean factors]], which depend on both the base and the exponent.

===Algebraic factors===
{{main|Binomial number#Factorization}}
From elementary algebra,
:<math>(b^{kn}-1) = (b^n-1) \sum_{r=0}^{k-1} b^{rn}</math>
for all ''k'', and
:<math>(b^{kn}+1) = (b^n+1) \sum_{r=0}^{k-1} (-1)^r \cdot b^{rn}</math>
for [[parity (mathematics)|odd]] ''k''. In addition,  {{math|1=''b''<sup>2''n''</sup> − 1 = (''b''<sup>''n''</sup> − 1)(''b''<sup>''n''</sup> + 1)}}. Thus, when ''m'' [[divides]] ''n'', {{math|1=''b''<sup>''m''</sup> − 1}} and {{math|1=''b''<sup>''m''</sup> + 1}} are factors of {{math|1=''b''<sup>''n''</sup> − 1}} if the quotient of ''n'' over ''m'' is [[parity (mathematics)|even]]; only the first number is a factor if the quotient is odd. {{math|1=''b''<sup>''m''</sup> + 1}} is a factor of {{math|1=''b''<sup>''n''</sup> − 1}}, if ''m'' divides ''n'' and the quotient is odd.

In fact, 
:<math>b^n-1 = \prod_{d \mid n} \Phi_d(b)</math>
and
:<math>b^n+1 = \prod_{d \mid 2n,\, d \nmid n} \Phi_d(b)</math>

See [https://stdkmd.net/nrr/repunit/repunitnote.htm#repunit_factorization this page] for more information.

===Aurifeuillean factors===
{{main|Aurifeuillean factorization}}
When the number is of a particular form (the exact expression varies with the base), aurifeuillean factorization may be used, which gives a product of two or three numbers. The following equations give aurifeuillean factors for the Cunningham project bases as a product of ''F'', ''L'' and ''M'':<ref>{{cite web|title=Main Cunningham Tables|url=https://homes.cerias.purdue.edu/~ssw/cun/pmain125.txt|accessdate=15 January 2025}} At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ there are formulae detailing the aurifeuillean factorizations.</ref>

Let ''b'' = ''s''<sup>2</sup>{{times}}''k'' with [[squarefree]] ''k'', if one of the conditions holds, then <math>\Phi_n(b)</math> have aurifeuillean factorization.
: (i) <math>k\equiv 1 \pmod 4</math> and <math>n\equiv k \pmod{2k};</math>
: (ii) <math>k\equiv 2, 3 \pmod 4</math> and <math>n\equiv 2k \pmod{4k}.</math>
{{table alignment}}
{| class="wikitable col2right col3right col4center col5center"
!''b''
!Number
!''F''
!''L''
!''M''
!Other definitions
|-
!2
|2<sup>4''k''+2</sup> + 1
|1
|2<sup>2{{itco|''k''}}+1</sup> − 2<sup>{{itco|''k''}}+1</sup> + 1
|2<sup>2{{itco|''k''}}+1</sup> + 2<sup>{{itco|''k''}}+1</sup> + 1
|
|-
!3
|3<sup>6''k''+3</sup> + 1
|3<sup>2{{itco|''k''}}+1</sup> + 1
|3<sup>2{{itco|''k''}}+1</sup> − 3<sup>{{itco|''k''}}+1</sup> + 1
|3<sup>2{{itco|''k''}}+1</sup> + 3<sup>{{itco|''k''}}+1</sup> + 1
|
|-
!5
|5<sup>10''k''+5</sup> − 1
|5<sup>2{{itco|''k''}}+1</sup> − 1
|{{itco|''T''}}<sup>2</sup> − 5<sup>{{itco|''k''}}+1</sup>''T'' + 5<sup>2{{itco|''k''}}+1</sup>
|{{itco|''T''}}<sup>2</sup> + 5<sup>{{itco|''k''}}+1</sup>''T'' + 5<sup>2{{itco|''k''}}+1</sup>
|''T'' = 5<sup>2{{itco|''k''}}+1</sup> + 1
|-
!6
|6<sup>12''k''+6</sup> + 1
|6<sup>4''k''+2</sup> + 1
|{{itco|''T''}}<sup>2</sup> − 6<sup>{{itco|''k''}}+1</sup>''T'' + 6<sup>2{{itco|''k''}}+1</sup>
|{{itco|''T''}}<sup>2</sup> + 6<sup>{{itco|''k''}}+1</sup>''T'' + 6<sup>2{{itco|''k''}}+1</sup>
|''T'' = 6<sup>2{{itco|''k''}}+1</sup> + 1
|-
!7
|7<sup>14''k''+7</sup> + 1
|7<sup>2{{itco|''k''}}+1</sup> + 1
|''A'' − ''B''
|''A'' + ''B''
|''A'' = 7<sup>6''k''+3</sup> + 3(7<sup>4''k''+2</sup>) + 3(7<sup>2{{itco|''k''}}+1</sup>) + 1<br/>''B'' = 7<sup>5''k''+3</sup> + 7<sup>3''k''+2</sup> + 7<sup>{{itco|''k''}}+1</sup>
|-
!10
|10<sup>20{{itco|''k''}}+10</sup> + 1
|10<sup>4''k''+2</sup> + 1
|''A'' − ''B''
|''A'' + ''B''
|''A'' = 10<sup>8''k''+4</sup> + 5(10<sup>6''k''+3</sup>) + 7(10<sup>4''k''+2</sup>) + 5(10<sup>2{{itco|''k''}}+1</sup>) + 1<br/>''B'' = 10<sup>7''k''+4</sup> + 2(10<sup>5''k''+3</sup>) + 2(10<sup>3''k''+2</sup>) + 10<sup>{{itco|''k''}}+1</sup>
|-
!11
|11<sup>22{{itco|''k''}}+11</sup> + 1
|11<sup>2{{itco|''k''}}+1</sup> + 1
|''A'' − ''B''
|''A'' + ''B''
|''A'' = 11<sup>10''k''+5</sup> + 5(11<sup>8''k''+4</sup>) − 11<sup>6''k''+3</sup> − 11<sup>4''k''+2</sup> + 5(11<sup>2{{itco|''k''}}+1</sup>) + 1<br/>''B'' = 11<sup>9''k''+5</sup> + 11<sup>7''k''+4</sup> − 11<sup>5''k''+3</sup> + 11<sup>3''k''+2</sup> + 11<sup>{{itco|''k''}}+1</sup>
|-
!12
|12<sup>6''k''+3</sup> + 1
|12<sup>2{{itco|''k''}}+1</sup> + 1
|12<sup>2{{itco|''k''}}+1</sup> − 6(12<sup>''k''</sup>) + 1
|12<sup>2{{itco|''k''}}+1</sup> + 6(12<sup>''k''</sup>) + 1
|
|}

===Other factors===
Once the algebraic and aurifeuillean factors are removed, the other factors of {{math|''b''<sup>''n''</sup> ± 1}} are always of the form {{math|2''kn'' + 1}}, since the factors of {{math|''b''<sup>''n''</sup> − 1}} are all factors of <math>\Phi_n(b)</math>, and the factors of {{math|''b''<sup>''n''</sup> + 1}} are all factors of <math>\Phi_{2n}(b)</math>. When ''n'' is [[prime number|prime]], both algebraic and aurifeuillean factors are not possible, except the trivial factors ({{math|''b'' − 1}} for {{math|''b''<sup>''n''</sup> − 1}} and {{math|''b'' + 1}} for {{math|''b''<sup>''n''</sup> + 1}}). For [[Mersenne numbers]], the trivial factors are not possible for {{nowrap|prime ''n''}}, so all factors are of the form {{math|2''kn'' + 1}}. In general, all factors of {{math|(''b''<sup>''n''</sup> − 1)&hairsp;/(''b'' − 1)}} are of the form {{math|2''kn'' + 1,}} where {{math|''b'' ≥ 2}} and ''n'' is prime, except when ''n'' divides {{math|''b'' − 1}}, in which case {{math|(''b''<sup>''n''</sup> − 1)&hairsp;/(''b'' − 1)}} is divisible by ''n'' itself.

Cunningham numbers of the form {{math|''b''<sup>''n''</sup> − 1}} can only be prime if ''b'' = 2 and ''n'' is prime, assuming that ''n'' ≥ 2; these are the Mersenne numbers. Numbers of the form {{math|''b''<sup>''n''</sup> + 1}} can only be prime if ''b'' is even and ''n'' is a [[power of 2]], again assuming {{math|''n'' ≥ 2;}} these are the generalized Fermat numbers, which are [[Fermat number]]s when ''b'' = 2. Any factor of a Fermat number {{math|2<sup>2<sup>''n''</sup></sup> + 1}} is of the form {{math|''k''&middot;2<sup>''n''+2</sup> + 1}}.