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

Les polynômes cyclotomiques eux-mêmes sont irréductibles (dans ${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle 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

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

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

• De même, puisque ${\displaystyle \Phi _{3}(-X)=X^{2}-X+1}$, on a ${\displaystyle \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

${\displaystyle 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 ${\displaystyle b^{n}-1}$ ou ${\displaystyle \Phi _{n}(b)}$, avec ${\displaystyle b=s^{2}\cdot t}$ et ${\displaystyle t}$ sans facteur carré ont une factorisation aurifeuillienne si et seulement si l'une des deux conditions suivantes est remplie^[1] :
  • ${\displaystyle t\equiv 1{\pmod {4}}}$ et ${\displaystyle n\equiv t{\pmod {2t}}}$
  • ${\displaystyle t\equiv 2,3{\pmod {4}}}$ et ${\displaystyle 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 ${\displaystyle L_{10k+5}}$ peut aussi être considérée comme aurifeuillienne :

${\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)}$

où ${\displaystyle L_{n}}$ est le ${\displaystyle n}$-ème nombre de Lucas, et ${\displaystyle F_{n}}$ est le ${\displaystyle n}$-ème nombre de Fibonacci^{[réf. souhaitée]}.

Historique

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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

• (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).

1. (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.
4. (en) Eric W. Weisstein, « Aurifeuillean Factorization », sur MathWorld
5. (en) Integer Arithmetic, Number Theory – Aurifeuillian Factorizations, Numericana

Liens externes

• (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.