# Aurifeuillean factorization

(Redirected from Aurifeuillian factorization)

In number theory, an aurifeuillean factorization, named after Léon-François-Antoine Aurifeuille, is a special type of algebraic factorization that comes from non-trivial factorizations of cyclotomic polynomials over the integers. Although cyclotomic polynomials themselves are irreducible over the integers, when restricted to particular integer values they may have an algebraic factorization, as in the examples below.

## Examples

• Numbers of the form $a^{4}+4b^{4}$ have the following aurifeuillean factorization (see also Sophie Germain's identity):
$a^{4}+4b^{4}=(a^{2}-2ab+2b^{2})\cdot (a^{2}+2ab+2b^{2})$ • Setting $a=1$ and $b=2^{k}$ , one obtains the following aurifeuillean factorization of $2^{4k+2}+1$ :
$2^{4k+2}+1=(2^{2k+1}-2^{k+1}+1)\cdot (2^{2k+1}+2^{k+1}+1)$ • Numbers of the form $b^{n}-1$ or $\Phi _{n}(b)$ , where $b=s^{2}\cdot t$ with square-free $t$ , have aurifeuillean factorization if and only if one of the following conditions holds:
• $t\equiv 1{\pmod {4}}$ and $n\equiv t{\pmod {2t}}$ • $t\equiv 2,3{\pmod {4}}$ and $n\equiv 2t{\pmod {4t}}$ Thus, when $b=s^{2}\cdot t$ with square-free $t$ , and $n$ is congruent to $t$ modulo $2t$ , then if $t$ is congruent to 1 mod 4, $b^{n}-1$ have aurifeuillean factorization, otherwise, $b^{n}+1$ have aurifeuillean factorization.
• When the number is of a particular form (the exact expression varies with the base), Aurifeuillian factorization may be used, which gives a product of two or three numbers. The following equations give Aurifeuillian factors for the Cunningham project bases as a product of F, L and M:
If we let L = CD, M = C + D, the Aurifeuillian factorizations for bn ± 1 of the form F * (CD) * (C + D) = F * L * M with the bases 2 ≤ b ≤ 24 (perfect powers excluded, since a power of bn is also a power of b) are:

(for the coefficients of the polynomials for all square-free bases up to 199 and up to 998, see )

b Number (CD) * (C + D) = L * M F C D
2 24k + 2 + 1 $\Phi _{4}(2^{2k+1})$ 1 22k + 1 + 1 2k + 1
3 36k + 3 + 1 $\Phi _{6}(3^{2k+1})$ 32k + 1 + 1 32k + 1 + 1 3k + 1
5 510k + 5 - 1 $\Phi _{5}(5^{2k+1})$ 52k + 1 - 1 54k + 2 + 3(52k + 1) + 1 53k + 2 + 5k + 1
6 612k + 6 + 1 $\Phi _{12}(6^{2k+1})$ 64k + 2 + 1 64k + 2 + 3(62k + 1) + 1 63k + 2 + 6k + 1
7 714k + 7 + 1 $\Phi _{14}(7^{2k+1})$ 72k + 1 + 1 76k + 3 + 3(74k + 2) + 3(72k + 1) + 1 75k + 3 + 73k + 2 + 7k + 1
10 1020k + 10 + 1 $\Phi _{20}(10^{2k+1})$ 104k + 2 + 1 108k + 4 + 5(106k + 3) + 7(104k + 2)
+ 5(102k + 1) + 1
107k + 4 + 2(105k + 3) + 2(103k + 2)
+ 10k + 1
11 1122k + 11 + 1 $\Phi _{22}(11^{2k+1})$ 112k + 1 + 1 1110k + 5 + 5(118k + 4) - 116k + 3
- 114k + 2 + 5(112k + 1) + 1
119k + 5 + 117k + 4 - 115k + 3
+ 113k + 2 + 11k + 1
12 126k + 3 + 1 $\Phi _{6}(12^{2k+1})$ 122k + 1 + 1 122k + 1 + 1 6(12k)
13 1326k + 13 - 1 $\Phi _{13}(13^{2k+1})$ 132k + 1 - 1 1312k + 6 + 7(1310k + 5) + 15(138k + 4)
+ 19(136k + 3) + 15(134k + 2) + 7(132k + 1) + 1
1311k + 6 + 3(139k + 5) + 5(137k + 4)
+ 5(135k + 3) + 3(133k + 2) + 13k + 1
14 1428k + 14 + 1 $\Phi _{28}(14^{2k+1})$ 144k + 2 + 1 1412k + 6 + 7(1410k + 5) + 3(148k + 4)
- 7(146k + 3) + 3(144k + 2) + 7(142k + 1) + 1
1411k + 6 + 2(149k + 5) - 147k + 4
- 145k + 3 + 2(143k + 2) + 14k + 1
15 1530k + 15 + 1 $\Phi _{30}(15^{2k+1})$ 1514k + 7 - 1512k + 6 + 1510k + 5
+ 154k + 2 - 152k + 1 + 1
158k + 4 + 8(156k + 3) + 13(154k + 2)
+ 8(152k + 1) + 1
157k + 4 + 3(155k + 3) + 3(153k + 2)
+ 15k + 1
17 1734k + 17 - 1 $\Phi _{17}(17^{2k+1})$ 172k + 1 - 1 1716k + 8 + 9(1714k + 7) + 11(1712k + 6)
- 5(1710k + 5) - 15(178k + 4) - 5(176k + 3)
+ 11(174k + 2) + 9(172k + 1) + 1
1715k + 8 + 3(1713k + 7) + 1711k + 6
- 3(179k + 5) - 3(177k + 4) + 175k + 3
+ 3(173k + 2) + 17k + 1
18 184k + 2 + 1 $\Phi _{4}(18^{2k+1})$ 1 182k + 1 + 1 6(18k)
19 1938k + 19 + 1 $\Phi _{38}(19^{2k+1})$ 192k + 1 + 1 1918k + 9 + 9(1916k + 8) + 17(1914k + 7)
+ 27(1912k + 6) + 31(1910k + 5) + 31(198k + 4)
+ 27(196k + 3) + 17(194k + 2) + 9(192k + 1) + 1
1917k + 9 + 3(1915k + 8) + 5(1913k + 7)
+ 7(1911k + 6) + 7(199k + 5) + 7(197k + 4)
+ 5(195k + 3) + 3(193k + 2) + 19k + 1
20 2010k + 5 - 1 $\Phi _{5}(20^{2k+1})$ 202k + 1 - 1 204k + 2 + 3(202k + 1) + 1 10(203k + 1) + 10(20k)
21 2142k + 21 - 1 $\Phi _{21}(21^{2k+1})$ 2118k + 9 + 2116k + 8 + 2114k + 7
- 214k + 2 - 212k + 1 - 1
2112k + 6 + 10(2110k + 5) + 13(218k + 4)
+ 7(216k + 3) + 13(214k + 2) + 10(212k + 1) + 1
2111k + 6 + 3(219k + 5) + 2(217k + 4)
+ 2(215k + 3) + 3(213k + 2) + 21k + 1
22 2244k + 22 + 1 $\Phi _{44}(22^{2k+1})$ 224k + 2 + 1 2220k + 10 + 11(2218k + 9) + 27(2216k + 8)
+ 33(2214k + 7) + 21(2212k + 6) + 11(2210k + 5)
+ 21(228k + 4) + 33(226k + 3) + 27(224k + 2)
+ 11(222k + 1) + 1
2219k + 10 + 4(2217k + 9) + 7(2215k + 8)
+ 6(2213k + 7) + 3(2211k + 6) + 3(229k + 5)
+ 6(227k + 4) + 7(225k + 3) + 4(223k + 2)
+ 22k + 1
23 2346k + 23 + 1 $\Phi _{46}(23^{2k+1})$ 232k + 1 + 1 2322k + 11 + 11(2320k + 10) + 9(2318k + 9)
- 19(2316k + 8) - 15(2314k + 7) + 25(2312k + 6)
+ 25(2310k + 5) - 15(238k + 4) - 19(236k + 3)
+ 9(234k + 2) + 11(232k + 1) + 1
2321k + 11 + 3(2319k + 10) - 2317k + 9
- 5(2315k + 8) + 2313k + 7 + 7(2311k + 6)
+ 239k + 5 - 5(237k + 4) - 235k + 3
+ 3(233k + 2) + 23k + 1
24 2412k + 6 + 1 $\Phi _{12}(24^{2k+1})$ 244k + 2 + 1 244k + 2 + 3(242k + 1) + 1 12(243k + 1) + 12(24k)

• Lucas numbers $L_{10k+5}$ have the following aurifeuillean factorization:
$L_{10k+5}=L_{2k+1}\cdot (5{F_{2k+1}}^{2}-5F_{2k+1}+1)\cdot (5{F_{2k+1}}^{2}+5F_{2k+1}+1)$ where $L_{n}$ is the $n$ th Lucas number, $F_{n}$ is the $n$ th Fibonacci number.

## History

Before the discovery of Aurifeuillean factorizations, Landry [fr; es; de], through a tremendous manual effort, obtained the following factorization into primes:

$2^{58}+1=5\cdot 107367629\cdot 536903681.$ Then in 1871, Aurifeuille discovered the nature of this factorization; the number $2^{4k+2}+1$ for $k=14$ , with the formula from the previous section, factors as:

$2^{58}+1=(2^{29}-2^{15}+1)(2^{29}+2^{15}+1)=536838145\cdot 536903681.$ Of course, Landry's full factorization follows from this (taking out the obvious factor 5). The general form of the factorization was later discovered by Lucas.

536903681 is an example of a Gaussian Mersenne norm.