Aurifeuillean factorization

(Redirected from Aurifeuillian factorization)

In number theory, an aurifeuillean factorization, or aurifeuillian 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.[1] 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 ${\displaystyle 2^{4k+2}+1}$ have the following aurifeuillean factorization:[2]
${\displaystyle 2^{4k+2}+1=(2^{2k+1}-2^{k+1}+1)\cdot (2^{2k+1}+2^{k+1}+1)}$
• Numbers of the form ${\displaystyle b^{n}-1}$ or ${\displaystyle \Phi _{n}(b)}$, where ${\displaystyle b=s^{2}\cdot t}$ with square-free ${\displaystyle t}$, have aurifeuillean factorization if and only if one of the following conditions holds:
• ${\displaystyle t\equiv 1{\pmod {4}}}$ and ${\displaystyle n\equiv t{\pmod {2t}}}$
• ${\displaystyle t\equiv 2,3{\pmod {4}}}$ and ${\displaystyle n\equiv 2t{\pmod {4t}}}$
Thus, when ${\displaystyle b=s^{2}\cdot t}$ with square-free ${\displaystyle t}$, and ${\displaystyle n}$ is congruent to ${\displaystyle t}$ mod ${\displaystyle 2t}$, then if ${\displaystyle t}$ is congruent to 1 mod 4, ${\displaystyle b^{n}-1}$ have aurifeuillean factorization, otherwise, ${\displaystyle 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:[3]
If we let L = CD, M = C + D, the Aurifeuillian factorizations for bn ± 1 with the bases 2 ≤ b ≤ 24 (perfect powers excluded, since a power of bn can also be regarded as a power of b) are: (for the coefficients of the polynomials for all square-free bases up to 199, see [4])
(Number = F * (CD) * (C + D) = F * L * M)
b Number (CD) * (C + D) = L * M F C D
2 24k + 2 + 1 ${\displaystyle \Phi _{4}(2^{2k+1})}$ 1 22k + 1 + 1 2k + 1
3 36k + 3 + 1 ${\displaystyle \Phi _{6}(3^{2k+1})}$ 32k + 1 + 1 32k + 1 + 1 3k + 1
5 510k + 5 - 1 ${\displaystyle \Phi _{5}(5^{2k+1})}$ 52k + 1 - 1 54k + 2 + 3(52k + 1) + 1 53k + 2 + 5k + 1
6 612k + 6 + 1 ${\displaystyle \Phi _{12}(6^{2k+1})}$ 64k + 2 + 1 64k + 2 + 3(62k + 1) + 1 63k + 2 + 6k + 1
7 714k + 7 + 1 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \Phi _{6}(12^{2k+1})}$ 122k + 1 + 1 122k + 1 + 1 6(12k)
13 1326k + 13 - 1 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \Phi _{4}(18^{2k+1})}$ 1 182k + 1 + 1 6(18k)
19 1938k + 19 + 1 ${\displaystyle \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 ${\displaystyle \Phi _{5}(20^{2k+1})}$ 202k + 1 - 1 204k + 2 + 3(202k + 1) + 1 10(203k + 1) + 10(20k)
21 2142k + 21 - 1 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \Phi _{12}(24^{2k+1})}$ 244k + 2 + 1 244k + 2 + 3(242k + 1) + 1 12(243k + 1) + 12(24k)
(See [5] for more information (square-free bases up to 199))
• Numbers of the form ${\displaystyle a^{4}+4b^{4}}$ have the following aurifeuillean factorization:
${\displaystyle a^{4}+4b^{4}=(a^{2}-2ab+2b^{2})\cdot (a^{2}+2ab+2b^{2})}$
• Lucas numbers ${\displaystyle L_{10k+5}}$ have the following aurifeuillean factorization:[6]
${\displaystyle 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 ${\displaystyle L_{n}}$ is the ${\displaystyle n}$th Lucas number, ${\displaystyle F_{n}}$ is the ${\displaystyle n}$th Fibonacci number.

History

In 1871, Aurifeuille discovered the factorization of ${\displaystyle 2^{4k+2}+1}$ for k = 14 as the following:[2][7]

${\displaystyle 2^{58}+1=536838145\cdot 536903681.}$

The second factor is prime, and the factorization of the first factor is ${\displaystyle 5\cdot 107367629}$.[7] The general form of the factorization was later discovered by Lucas.[2]

References

1. ^ A. Granville, P. Pleasants (2006). "Aurifeuillian factorization" (PDF). Math. Comp. 75: 497–508. doi:10.1090/S0025-5718-05-01766-7.
2. ^ a b c
3. ^ "Main Cunningham Tables". Retrieved 21 December 2015. At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ are formulae detailing the Aurifeuillian factorisations.
4. ^ Coefficients of Lucas C,D polynomials for all square-free bases up to 199
5. ^ List of Aurifeuillean factorization
6. ^ Lucas Aurifeuilliean primitive part
7. ^ a b