Aurifeuillian factor

Numbers of the form [math]\displaystyle{ 2^{4k+2}+1 }[/math] have the following aurifeuillean factorization: Mathworld

[math]\displaystyle{ 2^{4k+2}+1 = (2^{2k+1}-2^{k+1}+1)\cdot (2^{2k+1}+2^{k+1}+1) }[/math]

Numbers of the form [math]\displaystyle{ b^n - 1 }[/math] or [math]\displaystyle{ \Phi_n(b) }[/math], where [math]\displaystyle{ b = s^2 \cdot t }[/math] with square-free [math]\displaystyle{ t }[/math], have aurifeuillean factorization if and only if one of the following conditions holds:
- [math]\displaystyle{ t\equiv 1 \pmod 4 }[/math] and [math]\displaystyle{ n\equiv t \pmod{2t} }[/math]
- [math]\displaystyle{ t\equiv 2, 3 \pmod 4 }[/math] and [math]\displaystyle{ n\equiv 2t \pmod{4t} }[/math]

Thus, when [math]\displaystyle{ b = s^2\cdot t }[/math] with square-free [math]\displaystyle{ t }[/math], and [math]\displaystyle{ n }[/math] is congruent to [math]\displaystyle{ t }[/math] mod [math]\displaystyle{ 2t }[/math], then if [math]\displaystyle{ t }[/math] is congruent to 1 mod 4, [math]\displaystyle{ b^n-1 }[/math] have aurifeuillean factorization, otherwise, [math]\displaystyle{ b^n+1 }[/math] 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: Main Cunningham Tables. At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ are formulae detailing the Aurifeuillian factorisations.</ref>

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ⁿ is also a power of b) are: (for the coefficients of the polynomials for all square-free bases up to 199, see Coefficients of Lucas C,D polynomials for all square-free bases up to 199)

(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	[math]\displaystyle{ \Phi_4(2^{2k+1}) }[/math]	1	2^{2k + 1} + 1	2^{k + 1}
3	3^{6k + 3} + 1	[math]\displaystyle{ \Phi_6(3^{2k+1}) }[/math]	3^{2k + 1} + 1	3^{2k + 1} + 1	3^{k + 1}
5	5^{10k + 5} - 1	[math]\displaystyle{ \Phi_5(5^{2k+1}) }[/math]	5^{2k + 1} - 1	5^{4k + 2} + 3(5^{2k + 1}) + 1	5^{3k + 2} + 5^{k + 1}
6	6^{12k + 6} + 1	[math]\displaystyle{ \Phi_{12}(6^{2k+1}) }[/math]	6^{4k + 2} + 1	6^{4k + 2} + 3(6^{2k + 1}) + 1	6^{3k + 2} + 6^{k + 1}
7	7^{14k + 7} + 1	[math]\displaystyle{ \Phi_{14}(7^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{20}(10^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{22}(11^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_6(12^{2k+1}) }[/math]	12^{2k + 1} + 1	12^{2k + 1} + 1	6(12^k)
13	13^{26k + 13} - 1	[math]\displaystyle{ \Phi_{13}(13^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{28}(14^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{30}(15^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{17}(17^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_4(18^{2k+1}) }[/math]	1	18^{2k + 1} + 1	6(18^k)
19	19^{38k + 19} + 1	[math]\displaystyle{ \Phi_{38}(19^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_5(20^{2k+1}) }[/math]	20^{2k + 1} - 1	20^{4k + 2} + 3(20^{2k + 1}) + 1	10(20^{3k + 1}) + 10(20^k)
21	21^{42k + 21} - 1	[math]\displaystyle{ \Phi_{21}(21^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{44}(22^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{46}(23^{2k+1}) }[/math]	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	[math]\displaystyle{ \Phi_{12}(24^{2k+1}) }[/math]	24^{4k + 2} + 1	24^{4k + 2} + 3(24^{2k + 1}) + 1	12(24^{3k + 1}) + 12(24^k)

(See List of Aurifeuillean factorization for more information (square-free bases up to 199))

Numbers of the form [math]\displaystyle{ a^4 + 4b^4 }[/math] have the following aurifeuillean factorization:

[math]\displaystyle{ a^4 + 4b^4 = (a^2 - 2ab + 2b^2)\cdot (a^2 + 2ab + 2b^2) }[/math]

Lucas numbers [math]\displaystyle{ L_{10k+5} }[/math] have the following aurifeuillean factorization: Lucas Aurifeuilliean primitive part

[math]\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) }[/math]

where [math]\displaystyle{ L_n }[/math] is the [math]\displaystyle{ n }[/math]th Lucas number, [math]\displaystyle{ F_n }[/math] is the [math]\displaystyle{ n }[/math]th Fibonacci number.

External links

[[Wikipedia:Aurifeuillean_factorization|Aurifeuillean factorization}}

Aurifeuillian factor

External links

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Prime (direct)

Prime Wiki

Tools