Aurifeuillean factorization explained

In number theory, an aurifeuillean factorization, named after Léon-François-Antoine Aurifeuille, is factorization of certain integer values of the cyclotomic polynomials.^[1] Because cyclotomic polynomials are irreducible polynomials over the integers, such a factorization cannot come from an algebraic factorization of the polynomial. Nevertheless, certain families of integers coming from cyclotomic polynomials have factorizations given by formulas applying to the whole family, as in the examples below.

Examples

• Numbers of the form

a ^{4} + 4 b ^{4} have the following factorization (Sophie Germain's identity): $$a^4\; +\; 4b^4\; =\; (a^2\; -\; 2ab\; +\; 2b^2)\backslash cdot\; (a^2\; +\; 2ab\; +\; 2b^2).$$ Setting a =1 and b =2 ^{k} , one obtains the following aurifeuillean factorization of \Phi ^{2 k +1} _{4 ( 2} ) =2 ^{4k+2} +1 , where \Phi ^{2+1} _{4 (x) = x} is the fourth cyclotomic polynomial: $$2^+1\; =\; (2^-2^+1)\backslash cdot\; (2^+2^+1).$$

• Numbers of the form

a ^{6} + 27 b ^{6} have the following factorization, where the first factor (a ^{2} + 3 b ^{2} ) is the algebraic factorization of sum of two cubes: $$a^6\; +\; 27b^6\; =\; (a^2\; +\; 3b^2)\backslash cdot\; (a^2\; -\; 3ab\; +\; 3b^2)\backslash cdot\; (a^2\; +\; 3ab\; +\; 3b^2).$$ Setting a =1 and b =3 ^{k} , one obtains the following factorization of 3 ^{6k+3} +1 : $$3^+1\; =\; (3^+1)\backslash cdot\; (3^-3^+1)\backslash cdot\; (3^+3^+1).$$ Here, the first of the three terms in the factorization is \Phi ^{2 k +1} _{2 ( 3} ) and the remaining two terms provide an aurifeuillean factorization of \Phi ^{2 k +1} _{6 ( 3} ) , where \Phi ^{2- x +1} _{6 (x) = x} .

• Numbers of the form

b ^{n} - 1 or their factors \Phi _{n(b)} , where b = s ^{2} ⋅ 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{ 2 t} t\equiv 2 , 3 \pmod 4 and n\equiv 2 t \pmod{ 4 t}

Thus, when

b = s ^{2 ⋅} t with square-free t , and n is congruent to t modulo 2 t , 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), 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:^[2]

If we let L = C − D, M = C + D, the aurifeuillean 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 ^{[3] [4] [5]})

b	Number	(C − D) * (C + D) = L * M	F	C	D
2	2^4k + 2 + 1	\Phi ^{2 k +1} _{4 ( 2} )	1	2^2k + 1 + 1	2^k + 1
3	3^6k + 3 + 1	\Phi ^{2 k +1} _{6 ( 3} )	3^2k + 1 + 1	3^2k + 1 + 1	3^k + 1
5	5^10k + 5 - 1	\Phi ^{2 k +1} _{5 ( 5} )	5^2k + 1 - 1	5^4k + 2 + 3(5^2k + 1) + 1	5^3k + 2 + 5^k + 1
6	6^12k + 6 + 1	\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	\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	\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	\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	\Phi ^{2 k +1} _{6 ( 12} )	12^2k + 1 + 1	12^2k + 1 + 1	6(12^k)
13	13^26k + 13 - 1	\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	\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	\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	\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	\Phi ^{2 k +1} _{4 ( 18} )	1	18^2k + 1 + 1	6(18^k)
19	19^38k + 19 + 1	\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	\Phi ^{2 k +1} _{5 ( 20} )	20^2k + 1 - 1	20^4k + 2 + 3(20^2k + 1) + 1	10(20^3k + 1) + 10(20^k)
21	21^42k + 21 - 1	\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	\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	\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	\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

L _{10k+5} have the following aurifeuillean factorization:^[6] L _{10k+5} = L _{2k+1} ⋅ ( 5 {F _{2k+1} }^2-5F_+1)\cdot (5^2+5F_+1)

where

L _{n} is the n th Lucas number, and F _{n} is the n th Fibonacci number.

History

In 1869, before the discovery of aurifeuillean factorizations,, through a tremendous manual effort,^{[7] [8]} obtained the following factorization into primes:

2 ^{58} +1 = 5 ⋅ 107367629 ⋅ 536903681 .

Three years later, 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 ⋅ 536903681 .

Of course, Landry's full factorization follows from this (taking out the obvious factor of 5). The general form of the factorization was later discovered by Lucas.

536903681 is an example of a Gaussian Mersenne norm.

External links

• Aurifeuillean Factorisation, Colin Barker
• Aurifeuillean Factorizations, Gérard P. Michon
• The Search for Aurifeuillean-Like Factorizations
• Online factor collection
• A Note on Aurifeuillean Factorizations
• Aurifeuillean Factorisation

Notes and References

1. factorization . A. Granville, P. Pleasants . Math. Comp. . 75 . 253 . 2006 . 497–508 . 10.1090/S0025-5718-05-01766-7. free .
2. Web site: Main Cunningham Tables. At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ are formulae detailing the aurifeuillean factorizations.
3. https://stdkmd.net/nrr/repunit/repunitnote.htm#aurifeuillean List of aurifeuillean factorization of cyclotomic numbers (square-free bases up to 199)
4. http://myfactorcollection.mooo.com:8090/LCD_2_199 Coefficients of Lucas C,D polynomials for all square-free bases up to 199
5. http://myfactorcollection.mooo.com:8090/LCD_2_998 Coefficients of Lucas C,D polynomials for all square-free bases up to 998
6. https://t5k.org/top20/page.php?id=21 Lucas Aurifeuilliean primitive part
7. http://www.numericana.com/answer/numbers.htm#aurifeuille Integer Arithmetic, Number Theory – Aurifeuillean Factorizations
8. https://primes.utm.edu/glossary/page.php?sort=GaussianMersenne Gaussian Mersenne