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 $2^{4k+2}+1$ have the following aurifeuillean factorization:^[2]

$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$ mod $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:^[3]

If we let L = C − D, M = C + D, the Aurifeuillian factorizations for bⁿ ± 1 with the bases 2 ≤ b ≤ 24 (perfect powers excluded, since a power of bⁿ 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 * (C − D) * (C + D) = F * L * M)

b	Number	(C − D) * (C + D) = L * M	F	C	D
2	2^4k + 2 + 1	$\Phi_4(2^{2k+1})$	1	2^2k + 1 + 1	2^k + 1
3	3^6k + 3 + 1	$\Phi_6(3^{2k+1})$	3^2k + 1 + 1	3^2k + 1 + 1	3^k + 1
5	5^10k + 5 - 1	$\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	$\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_6(12^{2k+1})$	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_4(18^{2k+1})$	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_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	$\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)

(See ^[5] for more information (square-free bases up to 199))

• Numbers of the form $a^4 + 4b^4$ have the following aurifeuillean factorization:

$a^4 + 4b^4 = (a^2 - 2ab + 2b^2)\cdot (a^2 + 2ab + 2b^2)$

• Lucas number $L_{10k+5}$ have the following aurifeuillean factorization:^[6]

$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

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

$2^{58}+1 = 536838145 \cdot 536903681 \,\!$

The second factor is prime, and the factorization of the first factor is $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. Weisstein, Eric W., "Aurifeuillean Factorization", MathWorld.
3. "Main Cunningham Tables". Retrieved 21 December 2015. At the end of tables 2LM, 3+, 5-, 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. Integer Arithmetic, Number Theory – Aurifeuillian Factorizations, Numericana

External links

• Aurifeuillian Factorisation, Colin Barker
• Online factor collection