Aurifeuillean 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.[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 $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]

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$ $\text{[math]}$ or $\Phi _{n}(b)$ $\text{[math]}$ , where $b=s^{2}\cdot t$ $\text{[math]}$ with square-free $t$ $\text{[math]}$ , 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:[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	$\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)

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

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, through a tremendous manual effort,[8][9] 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][8]

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

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

External links

Aurifeuillian Factorisation, Colin Barker
Online factor collection

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] A. Granville, P. Pleasants (2006). "Aurifeuillian factorization" (PDF). Math. Comp. 75 (253): 497–508. doi:10.1090/S0025-5718-05-01766-7.

[Wolfram-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

[numericana-8] Integer Arithmetic, Number Theory – Aurifeuillian Factorizations, Numericana

[primepages-9] Gaussian Mersenne, the Prime Pages glossary