Aurifeuillean 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 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})}$

• Setting ${\displaystyle a=1}$ and ${\displaystyle b=2^{k}}$, one obtains the following aurifeuillean factorization of ${\displaystyle 2^{4k+2}+1}$:[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}$ modulo ${\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 = C − D, M = C + D, the Aurifeuillian factorizations for bⁿ ± 1 of the form F * (C − D) * (C + D) = F * L * M with the bases 2 ≤ b ≤ 24 (perfect powers excluded, since a power of bⁿ 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 [4][5][6])

b	Number	(C − D) * (C + D) = L * M	F	C	D
2	2^4k + 2 + 1	${\displaystyle \Phi _{4}(2^{2k+1})}$	1	2^2k + 1 + 1	2^k + 1
3	3^6k + 3 + 1	${\displaystyle \Phi _{6}(3^{2k+1})}$	3^2k + 1 + 1	3^2k + 1 + 1	3^k + 1
5	5^10k + 5 - 1	${\displaystyle \Phi _{5}(5^{2k+1})}$	5^2k + 1 - 1	5^4k + 2 + 3(5^2k + 1) + 1	5^3k + 2 + 5^k + 1
6	6^12k + 6 + 1	${\displaystyle \Phi _{12}(6^{2k+1})}$	6^4k + 2 + 1	6^4k + 2 + 3(6^2k + 1) + 1	6^3k + 2 + 6^k + 1
7	7^14k + 7 + 1	${\displaystyle \Phi _{14}(7^{2k+1})}$	7^2k + 1 + 1	7^6k + 3 + 3(7^4k + 2) + 3(7^2k + 1) + 1	7^5k + 3 + 7^3k + 2 + 7^k + 1
10	10^20k + 10 + 1	${\displaystyle \Phi _{20}(10^{2k+1})}$	10^4k + 2 + 1	10^8k + 4 + 5(10^6k + 3) + 7(10^4k + 2) + 5(10^2k + 1) + 1	10^7k + 4 + 2(10^5k + 3) + 2(10^3k + 2) + 10^k + 1
11	11^22k + 11 + 1	${\displaystyle \Phi _{22}(11^{2k+1})}$	11^2k + 1 + 1	11^10k + 5 + 5(11^8k + 4) - 11^6k + 3 - 11^4k + 2 + 5(11^2k + 1) + 1	11^9k + 5 + 11^7k + 4 - 11^5k + 3 + 11^3k + 2 + 11^k + 1
12	12^6k + 3 + 1	${\displaystyle \Phi _{6}(12^{2k+1})}$	12^2k + 1 + 1	12^2k + 1 + 1	6(12^k)
13	13^26k + 13 - 1	${\displaystyle \Phi _{13}(13^{2k+1})}$	13^2k + 1 - 1	13^12k + 6 + 7(13^10k + 5) + 15(13^8k + 4) + 19(13^6k + 3) + 15(13^4k + 2) + 7(13^2k + 1) + 1	13^11k + 6 + 3(13^9k + 5) + 5(13^7k + 4) + 5(13^5k + 3) + 3(13^3k + 2) + 13^k + 1
14	14^28k + 14 + 1	${\displaystyle \Phi _{28}(14^{2k+1})}$	14^4k + 2 + 1	14^12k + 6 + 7(14^10k + 5) + 3(14^8k + 4) - 7(14^6k + 3) + 3(14^4k + 2) + 7(14^2k + 1) + 1	14^11k + 6 + 2(14^9k + 5) - 14^7k + 4 - 14^5k + 3 + 2(14^3k + 2) + 14^k + 1
15	15^30k + 15 + 1	${\displaystyle \Phi _{30}(15^{2k+1})}$	15^14k + 7 - 15^12k + 6 + 15^10k + 5 + 15^4k + 2 - 15^2k + 1 + 1	15^8k + 4 + 8(15^6k + 3) + 13(15^4k + 2) + 8(15^2k + 1) + 1	15^7k + 4 + 3(15^5k + 3) + 3(15^3k + 2) + 15^k + 1
17	17^34k + 17 - 1	${\displaystyle \Phi _{17}(17^{2k+1})}$	17^2k + 1 - 1	17^16k + 8 + 9(17^14k + 7) + 11(17^12k + 6) - 5(17^10k + 5) - 15(17^8k + 4) - 5(17^6k + 3) + 11(17^4k + 2) + 9(17^2k + 1) + 1	17^15k + 8 + 3(17^13k + 7) + 17^11k + 6 - 3(17^9k + 5) - 3(17^7k + 4) + 17^5k + 3 + 3(17^3k + 2) + 17^k + 1
18	18^4k + 2 + 1	${\displaystyle \Phi _{4}(18^{2k+1})}$	1	18^2k + 1 + 1	6(18^k)
19	19^38k + 19 + 1	${\displaystyle \Phi _{38}(19^{2k+1})}$	19^2k + 1 + 1	19^18k + 9 + 9(19^16k + 8) + 17(19^14k + 7) + 27(19^12k + 6) + 31(19^10k + 5) + 31(19^8k + 4) + 27(19^6k + 3) + 17(19^4k + 2) + 9(19^2k + 1) + 1	19^17k + 9 + 3(19^15k + 8) + 5(19^13k + 7) + 7(19^11k + 6) + 7(19^9k + 5) + 7(19^7k + 4) + 5(19^5k + 3) + 3(19^3k + 2) + 19^k + 1
20	20^10k + 5 - 1	${\displaystyle \Phi _{5}(20^{2k+1})}$	20^2k + 1 - 1	20^4k + 2 + 3(20^2k + 1) + 1	10(20^3k + 1) + 10(20^k)
21	21^42k + 21 - 1	${\displaystyle \Phi _{21}(21^{2k+1})}$	21^18k + 9 + 21^16k + 8 + 21^14k + 7 - 21^4k + 2 - 21^2k + 1 - 1	21^12k + 6 + 10(21^10k + 5) + 13(21^8k + 4) + 7(21^6k + 3) + 13(21^4k + 2) + 10(21^2k + 1) + 1	21^11k + 6 + 3(21^9k + 5) + 2(21^7k + 4) + 2(21^5k + 3) + 3(21^3k + 2) + 21^k + 1
22	22^44k + 22 + 1	${\displaystyle \Phi _{44}(22^{2k+1})}$	22^4k + 2 + 1	22^20k + 10 + 11(22^18k + 9) + 27(22^16k + 8) + 33(22^14k + 7) + 21(22^12k + 6) + 11(22^10k + 5) + 21(22^8k + 4) + 33(22^6k + 3) + 27(22^4k + 2) + 11(22^2k + 1) + 1	22^19k + 10 + 4(22^17k + 9) + 7(22^15k + 8) + 6(22^13k + 7) + 3(22^11k + 6) + 3(22^9k + 5) + 6(22^7k + 4) + 7(22^5k + 3) + 4(22^3k + 2) + 22^k + 1
23	23^46k + 23 + 1	${\displaystyle \Phi _{46}(23^{2k+1})}$	23^2k + 1 + 1	23^22k + 11 + 11(23^20k + 10) + 9(23^18k + 9) - 19(23^16k + 8) - 15(23^14k + 7) + 25(23^12k + 6) + 25(23^10k + 5) - 15(23^8k + 4) - 19(23^6k + 3) + 9(23^4k + 2) + 11(23^2k + 1) + 1	23^21k + 11 + 3(23^19k + 10) - 23^17k + 9 - 5(23^15k + 8) + 23^13k + 7 + 7(23^11k + 6) + 23^9k + 5 - 5(23^7k + 4) - 23^5k + 3 + 3(23^3k + 2) + 23^k + 1
24	24^12k + 6 + 1	${\displaystyle \Phi _{12}(24^{2k+1})}$	24^4k + 2 + 1	24^4k + 2 + 3(24^2k + 1) + 1	12(24^3k + 1) + 12(24^k)

• Lucas numbers ${\displaystyle L_{10k+5}}$ have the following aurifeuillean factorization:[7]

${\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

Before the discovery of Aurifeuillean factorizations, Landry, through a tremendous manual effort,[8][9] obtained the following factorization into primes:

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

Then in 1871, Aurifeuille discovered the nature of this factorization; the number ${\displaystyle 2^{4k+2}+1}$ for ${\displaystyle k=14}$, with the formula from the previous section, factors as:[2][8]

${\displaystyle 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.[2]

536903681 is an example of a Gaussian Mersenne norm.[9]

References

1. A. Granville, P. Pleasants (2006). "Aurifeuillian factorization" (PDF). Math. Comp. 75 (253): 497–508. doi:10.1090/S0025-5718-05-01766-7.
2. Weisstein, Eric W. "Aurifeuillean Factorization". MathWorld.
3. "Main Cunningham Tables". At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ are formulae detailing the Aurifeuillian factorisations.
4. List of Aurifeuillean factorization of cyclotomic numbers (square-free bases up to 199)
5. Coefficients of Lucas C,D polynomials for all square-free bases up to 199
6. Coefficients of Lucas C,D polynomials for all square-free bases up to 998
7. Lucas Aurifeuilliean primitive part
8. Integer Arithmetic, Number Theory – Aurifeuillian Factorizations, Numericana
9. Gaussian Mersenne, the Prime Pages glossary

External links

• Aurifeuillian Factorisation, Colin Barker
• Online factor collection