Factorisation aurifeuillienne

En théorie des nombres, une factorisation aurifeuillienne, nommée d'après Léon-François-Antoine Aurifeuille, est un cas particulier de factorisation algébrique d'entiers provenant d'une factorisation (accidentelle) d'un polynôme cyclotomique^[1].

Définition modifier

Les polynômes cyclotomiques eux-mêmes sont irréductibles (dans ${\mathbb {Q} }[X]$ ), mais il peut néanmoins arriver qu'on dispose de factorisations systématiques de leurs valeurs sur certains entiers. On appelle factorisation aurifeuillienne du polynôme cyclotomique P une formule de la forme $P(b^{cn+d})=Q_{n}(b)R_{n}(b)$ (où b est un entier fixé, la base, et Q et R sont des polynômes non constants), valable pour tout n. Une telle factorisation provient en général de ce que le polynôme $b^{d}X^{n}-1$ possède des facteurs autres que ceux donnés par les polynômes cyclotomiques (en 2004, Andrew Granville a démontré qu'avec une définition convenablement précisée, il n'en existait pas d'autres^[1]). Les exemples qui suivent illustrent ce phénomène.

Exemples modifier

Les nombres de la forme $2^{4k+2}+1$ peuvent s'écrire^[2] :

2^{4k+2}+1=(2^{2k+1}-2^{k+1}+1)\cdot (2^{2k+1}+2^{k+1}+1)

.

De même, puisque $\Phi _{3}(-X)=X^{2}-X+1$ , on a $\Phi _{3}(-3x^{2})=9x^{4}-3x^{2}+1=(3x^{2}+1)^{2}-9x^{2}$ ; prenant b=x=3, on en déduit la factorisation aurifeuillienne

3^{6k+3}+1=(3^{2k+1}+1)(3^{2k+1}-3^{k+1}+1)(3^{2k+1}+3^{k+1}+1)

.

Les nombres de la forme $b^{n}-1$ ou $\Phi _{n}(b)$ , avec $b=s^{2}\cdot t$ et $t$ sans facteur carré ont une factorisation aurifeuillienne si et seulement si l'une des deux conditions suivantes est remplie^[1] :
- $t\equiv 1{\pmod {4}}$ et $n\equiv t{\pmod {2t}}$
- $t\equiv 2,3{\pmod {4}}$ et $n\equiv 2t{\pmod {4t}}$ .

Les formules suivantes donnent les facteurs aurifeuilliens de bⁿ ± 1 obtenus par le projet Cunningham pour les bases b ≤ 24 (qui ne sont pas des puissances d'autres bases) comme produits de trois facteurs F, L et M^[3], avec L = A - B et M = A + B : nombre = F * (A - B) * (A + B) = F * L * M

b	Nombre	F	A	B
2	2^{4k + 2} + 1	1	2^{2k + 1} + 1	2^{k + 1}
3	3^{6k + 3} + 1	3^{2k + 1} + 1	3^{2k + 1} + 1	3^{k + 1}
5	5^{10k + 5} - 1	5^{2k + 1} - 1	5^{4k + 2} + 3(5^{2k + 1}) + 1	5^{3k + 2} + 5^{k + 1}
6	6^{12k + 6} + 1	6^{4k + 2} + 1	6^{4k + 2} + 3(6^{2k + 1}) + 1	6^{3k + 2} + 6^{k + 1}
7	7^{14k + 7} + 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	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	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	12^{2k + 1} + 1	12^{2k + 1} + 1	6(12^k)
13	13^{26k + 13} - 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	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	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	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	1	18^{2k + 1} + 1	6(18^k)
19	19^{38k + 19} + 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	20^{2k + 1} - 1	20^{4k + 2} + 3(20^{2k + 1}) + 1	10(20^{3k + 1}) + 10(20^k)
21	21^{42k + 21} - 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	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	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	24^{4k + 2} + 1	24^{4k + 2} + 3(24^{2k + 1}) + 1	12(24^{3k + 1}) + 12(24^k)

La factorisation suivante des nombres de Lucas $L_{10k+5}$ peut aussi être considérée comme aurifeuillienne :

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)

où

L_{n}

est le

n

-ème nombre de Lucas, et

F_{n}

est le

n

-ème nombre de Fibonacci^{[réf. souhaitée]}.

Historique modifier

En 1871, Aurifeuille découvrit la factorisation de $2^{4k+2}+1$ pour k = 14^[4] ^,^[5]

2^{58}+1=(2^{29}+2^{15}+1)(2^{29}-2^{15}+1)=536838145\cdot 536903681.\,\!

Le second facteur est premier, et l'autre vaut $5\times 107367629,$ ce dernier nombre étant premier^[5]. Cette factorisation (qui avait échappé à Fortuné Landry) est un cas particulier de l'identité de Sophie Germain $4x^{4}+y^{4}=(2x^{2}+2xy+y^{2})(2x^{2}-2xy+y^{2})$ , mais en 1878, Édouard Lucas signala que Aurifeuille avait obtenu des factorisations analogues pour tous les b premiers^[1]

Références modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Aurifeuillean factorization » (voir la liste des auteurs).

↑ ^{a b c et d} (en) Andrew Granville et Peter Pleasants, « Aurifeuillian factorization », Math. Comp., vol. 75,‎ 2006, p. 497–508 (DOI 10.1090/S0025-5718-05-01766-7, lire en ligne)
↑ C'est un cas particulier de l'identité de Sophie Germain
↑ (en) « Main Cunningham Tables » (consulté le 21 décembre 2015) ; après les tables 2LM, 3+, 5-, 7+, 10+, 11+ et 12+ se trouvent des formules détaillant les factorisations.
↑ (en) Eric W. Weisstein, « Aurifeuillean Factorization », sur MathWorld
↑ ^{a et b} (en) Integer Arithmetic, Number Theory – Aurifeuillian Factorizations, Numericana

Liens externes modifier

(en) Factorisation aurifeuillienne, sur le site de Colin Barker.
(en) Programmes de factorisation en ligne.
(en) Site de Makoto Kamada, pour d'autres factorisations aurifeuilliennes, avec b ≤ 199.

Arithmétique et théorie des nombres

[gr-1] {a b c et d} (en) Andrew Granville et Peter Pleasants, « Aurifeuillian factorization », Math. Comp., vol. 75,‎ 2006, p. 497–508 (DOI 10.1090/S0025-5718-05-01766-7, lire en ligne)

[2] C'est un cas particulier de l'identité de Sophie Germain

[3] (en) « Main Cunningham Tables » (consulté le 21 décembre 2015) ; après les tables 2LM, 3+, 5-, 7+, 10+, 11+ et 12+ se trouvent des formules détaillant les factorisations.

[Wolfram-4] (en) Eric W. Weisstein, « Aurifeuillean Factorization », sur MathWorld

[numericana-5] {a et b} (en) Integer Arithmetic, Number Theory – Aurifeuillian Factorizations, Numericana

[1]

[2]

[3]

[4]

[5]