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 | modifier le code]

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 | modifier le code]

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$ $b^{n}-1$ ou $\Phi _{n}(b)$ $\Phi _{n}(b)$ , avec $b=s^{2}\cdot t$ $b=s^{2}\cdot t$ et $t$ $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 | modifier le code]

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 | modifier le code]

(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 | modifier le code]

(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]