Орифейлевская факторизация

В теории чисел , факторизация aurifeuillean , названная в честь Леона-Франсуа-Антуана Орифея , является факторизацией определенных целых значений циклотомических многочленов . ^[1] Поскольку циклотомические многочлены являются неприводимыми многочленами над целыми числами, такая факторизация не может происходить из алгебраической факторизации многочлена. Тем не менее, некоторые семейства целых чисел, происходящие от циклотомических многочленов, имеют факторизации, заданные формулами, применяемыми ко всему семейству, как в примерах ниже.

Примеры

Числа вида имеют следующую факторизацию ( тождество Софи Жермен ): Полагая и , получаем следующую орифейлевскую факторизацию , где — четвертый циклотомический многочлен: ^[2] $а^{4}+4b^{4}$ $a^{4}+4b^{4}=(a^{2}-2ab+2b^{2})\cdot (a^{2}+2ab+2b^{2}).$ $а=1$ $b=2^{k}$ $\Phi _{4}(2^{2k+1})=2^{4k+2}+1$ $\Phi _{4}(x)=x^{2}+1$ $2^{4k+2}+1=(2^{2k+1}-2^{k+1}+1)\cdot (2^{2k+1}+2^{k+1} +1).$
Числа вида имеют следующую факторизацию, где первый множитель ( ) является алгебраической факторизацией суммы двух кубов : Полагая и , получаем следующую факторизацию : ^[2] Здесь первый из трех членов факторизации равен , а оставшиеся два члена обеспечивают аурифейлеву факторизацию , где . $а^{6}+27б^{6}$ $а^{2}+3b^{2}$ $a^{6}+27b^{6}=(a^{2}+3b^{2})\cdot (a^{2}-3ab+3b^{2})\cdot (a^ {2}+3ab+3b^{2}).$ $а=1$ $b=3^{k}$ $3^{6k+3}+1$ $3^{6k+3}+1=(3^{2k+1}+1)\cdot (3^{2k+1}-3^{k+1}+1)\cdot (3^{2k+1}+3^{k+1}+1).$ $\Phi _{2}(3^{2k+1})$ $\Phi _{6}(3^{2k+1})$ $\Фи _{6}(x)=x^{2}-x+1$
Числа вида или их множители , где с квадратным исключением , имеют аурифейлевскую факторизацию тогда и только тогда, когда выполняется одно из следующих условий: $b^{n}-1$ $\Фи _{n}(б)$ $b=s^{2}\cdot t$ $т$
- $t\equiv 1{\pmod {4}}$ и $n\equiv t{\pmod {2t}}$
- $t\equiv 2,3{\pmod {4}}$ и $n\equiv 2t{\pmod {4t}}$

Таким образом, когда с бесквадратным и сравнимо по модулю , то если сравнимо с 1 по модулю 4, имеем аурифейлеву факторизацию, в противном случае имеем аурифейлеву факторизацию .

b=s^{2}\cdot t

т

n

т

2т

т

b^{n}-1

б^{н}+1

Когда число имеет определенную форму (точное выражение зависит от основания), может быть использована факторизация aurifeuillean, которая дает произведение двух или трех чисел. Следующие уравнения дают факторы aurifeuillean для оснований проекта Каннингема как произведение F , L и M : ^[3]

Если положить L = C − D , M = C + D , то аурифейлевы факторизации для b ⁿ ± 1 вида F * ( C − D ) * ( C + D ) = F * L * M с основаниями 2 ≤ b ≤ 24 ( исключая совершенные степени , поскольку степень b ⁿ также является степенью b ) будут следующими:

(коэффициенты многочленов для всех бесквадратных оснований до 199 и до 998 см. в [ ^4]^[5]^[6] )

б	Число	( С − Д ) * ( С + Д ) = Л * М	Ф	С	Д
2	2 ^{4 к + 2} + 1	$\Phi _{4}(2^{2k+1})$	1	2 ^{2 к + 1} + 1	2 ^{к + 1}
3	3 ^{6 к + 3} + 1	$\Phi _{6}(3^{2k+1})$	3 ^{2 к + 1} + 1	3 ^{2 к + 1} + 1	3 ^{к + 1}
5	5 ^{10 тыс. + 5} - 1	$\Phi _{5}(5^{2k+1})$	5 ^{2 к + 1} - 1	5 ^{4 к + 2} + 3(5 ^{2 к + 1} ) + 1	5 ^{3 к + 2} + 5 ^{к + 1}
6	6 ^{12 тыс. + 6} + 1	$\Phi _{12}(6^{2k+1})$	6 ^{4 к + 2} + 1	6 ^{4 к + 2} + 3(6 ^{2 к + 1} ) + 1	6 ^{3 к + 2} + 6 ^{к + 1}
7	7 ^{14 к + 7} + 1	$\Phi _{14}(7^{2k+1})$	7 ^{2 к + 1} + 1	7 ^{6 к + 3} + 3(7 ^{4 к + 2} ) + 3(7 ^{2 к + 1} ) + 1	7 ^{5 к + 3} + 7 ^{3 к + 2} + 7 ^{к + 1}
10	10 ^{20 тыс. + 10} + 1	$\Phi _{20}(10^{2k+1})$	10 ^{4 к + 2} + 1	10 ^{8 к + 4} + 5(10 ^{6 к + 3} ) + 7(10 ^{4 к + 2} ) + 5(10 ^{2 к + 1} ) + 1	10 ^{7 к + 4} + 2(10 ^{5 к + 3} ) + 2(10 ^{3 к + 2} ) + 10 ^{к + 1}
11	11 ^{22 к + 11} + 1	$\Phi _{22}(11^{2k+1})$	11 ^{2 к + 1} + 1	11 ^{10 к + 5} + 5(11 ^{8 к + 4} ) - 11 ^{6 к + 3} - 11 ^{4 к + 2} + 5(11 ^{2 к + 1} ) + 1	11 ^{9 к + 5} + 11 ^{7 к + 4} - 11 ^{5 к + 3} + 11 ^{3 к + 2} + 11 ^{к + 1}
12	12 ^{6 к + 3} + 1	$\Phi _{6}(12^{2k+1})$	12 ^{2 к + 1} + 1	12 ^{2 к + 1} + 1	6(12 ^тыс .)
13	13 ^{26 к + 13} - 1	$\Phi _{13}(13^{2k+1})$	13 ^{2 к + 1} - 1	13 ^{12 тыс. + 6} + 7(13 ^{10 тыс. + 5} ) + 15(13 ^{8 тыс . + 4} ) + 19(13 ^{6 тыс. + 3} ) + 15(13 ^{4 тыс. + 2} ) + 7(13 ^{2 тыс . + 1} ) + 1	13 ^{11 к + 6} + 3(13 ^{9 к + 5} ) + 5(13 ^{7 к + 4} ) + 5(13 ^{5 к + 3} ) + 3(13 ^{3 к + 2} ) + 13 ^{к + 1}
14	14 ^{28 к + 14} + 1	$\Phi _{28}(14^{2k+1})$	14 ^{4 к + 2} + 1	14 ^{12 тыс. + 6} + 7(14 ^{10 тыс . + 5} ) + 3(14 ^{8 тыс. + 4} ) - 7(14 ^{6 тыс. + 3} ) + 3(14 ^{4 тыс. + 2} ) + 7(14 ^{2 тыс . + 1} ) + 1	14 ^{11 к + 6} + 2(14 ^{9 к + 5} ) - 14 ^{7 к + 4} - 14 ^{5 к + 3} + 2(14 ^{3 к + 2} ) + 14 ^{к + 1}
15	15 ^{30 тыс. + 15} + 1	$\Phi _{30}(15^{2k+1})$	15 ^{14 тыс. + 7} - 15 ^{12 тыс . + 6} + 15 ^{10 тыс. + 5} + 15 ^{4 тыс. + 2} - 15 ^{2 тыс. + 1} + 1	15 ^{8 к + 4} + 8(15 ^{6 к + 3} ) + 13(15 ^{4 к + 2} ) + 8(15 ^{2 к + 1} ) + 1	15 ^{7 к + 4} + 3(15 ^{5 к + 3} ) + 3(15 ^{3 к + 2} ) + 15 ^{к + 1}
17	17 ^{34 к + 17} - 1	$\Phi _{17}(17^{2k+1})$	17 ^{2 к + 1} - 1	17 ^{16 тыс. + 8} + 9(17 ^{14 тыс . + 7} ) + 11(17 ^{12 тыс . + 6} ) - 5(17 ^{10 тыс. + 5} ) - 15(17 ^{8 тыс. + 4} ) - 5(17 ^{6 тыс . + 3} ) + 11(17 ^{4 тыс. + 2} ) + 9(17 ^{2 тыс. + 1} ) + 1	17 ^{15 к + 8} + 3(17 ^{13 к + 7} ) + 17 ^{11 к + 6} - 3(17 ^{9 к + 5} ) - 3(17 ^{7 к + 4} ) + 17 ^{5 к + 3} + 3(17 ^{3 к + 2} ) + 17 ^{к + 1}
18	18 ^{4 к + 2} + 1	$\Phi _{4}(18^{2k+1})$	1	18 ^{2 к + 1} + 1	6(18 ^тыс .)
19	19 ^{38 к + 19} + 1	$\Phi _{38}(19^{2k+1})$	19 ^{2 к + 1} + 1	19 ^{18 тыс. + 9} + 9(19 ^{16 тыс. + 8} ) + 17(19 ^{14 тыс. + 7} ) + 27(19 ^{12 тыс . + 6} ) + 31( 19 ^{10 тыс. + 5} ) + 31(19 ^{8 тыс . + 4} ) + 27(19 ^{6 тыс. + 3} ) + 17(19 ^{4 тыс. + 2} ) + 9(19 ^{2 тыс. + 1} ) + 1	19 ^{17 тыс. + 9} + 3(19 ^{15 тыс . + 8} ) + 5(19 ^{13 тыс . + 7} ) + 7(19 ^{11 тыс. + 6} ) + 7 (19 ^{9 тыс. + 5} ) + 7(19 ^{7 тыс . + 4} ) + 5(19 ^{5 тыс . + 3} ) + 3(19 ^{3 тыс. + 2} ) + 19 ^{тыс. + 1}
20	20 ^{10 тыс. + 5} - 1	$\Phi _{5}(20^{2k+1})$	20 ^{2 к + 1} - 1	20 ^{4 к + 2} + 3(20 ^{2 к + 1} ) + 1	10(20 ^{3 тыс. + 1} ) + 10(20 ^тыс. )
21	21 ^{42 к + 21} - 1	$\Phi _{21}(21^{2k+1})$	21 ^{18 тыс. + 9} + 21 ^{16 тыс . + 8} + 21 ^{14 тыс . + 7} - 21 ^{4 тыс. + 2} - 21 ^{2 тыс. + 1} - 1	21 ^{12 тыс. + 6} + 10(21 ^{10 тыс. + 5} ) + 13(21 ^{8 тыс . + 4} ) + 7(21 ^{6 тыс. + 3} ) + 13(21 ^{4 тыс. + 2} ) + 10(21 ^{2 тыс. + 1} ) + 1	21 ^{11 к + 6} + 3(21 ^{9 к + 5} ) + 2(21 ^{7 к + 4} ) + 2(21 ^{5 к + 3} ) + 3(21 ^{3 к + 2} ) + 21 ^{к + 1}
22	22 ^{44 к + 22} + 1	$\Phi _{44}(22^{2k+1})$	22 ^{4 к + 2} + 1	22 ^{20 тыс. + 10} + 11(22 ^{18 тыс . + 9} ) + 27(22 ^{16 тыс. + 8} ) + 33(22 ^{14 тыс. + 7} ) + 21(22 ^{12 тыс. + 6} ) + 11 (22 ^{10 тыс. + 5} ) + 21(22 ^{8 тыс. + 4} ) + 33(22 ^{6 тыс. + 3} ) + 27(22 ^{4 тыс. + 2} ) + 11(22 ^{2 тыс. + 1} ) + 1	22 ^{19 тыс. + 10} + 4(22 ^{17 тыс . + 9} ) + 7(22 ^{15 тыс. + 8} ) + 6(22 ^{13 тыс.}⁺⁷ ) + 3(22 ^{11 тыс} . + 6 ) + 3 (22 ^{9 тыс . + 5} ) + 6(22 ^{7 тыс. + 4} ) + 7(22 ^{5 тыс. + 3} ) + 4(22 ^{3 тыс. + 2} ) + 22 ^{тыс. + 1}
23	23 ^{46 к + 23} + 1	$\Phi _{46}(23^{2k+1})$	23 ^{2 к + 1} + 1	23 ^{22 тыс. + 11} + 11(23 ^{20 тыс. + 10} ) + 9(23 ^{18 тыс. + 9} ) - 19(23 ^{16 тыс. + 8} ) - 15(23 ^{14 тыс. + 7} ) + 25 (23 ^{12 тыс. + 6} ) + 25(23 ^{10 тыс. + 5} ) - 15(23 ^{8 тыс. + 4} ) - 19(23 ^{6 тыс. + 3} ) + 9(23 ^{4 тыс. + 2} ) + 11(23 ^{2 тыс . + 1} ) + 1	23 ^{21 к + 11} + 3(23 ^{19 к + 10} ) - 23 ^{17 к + 9} - 5(23 ^{15 к + 8} ) + 23 ^{13 к + 7} + 7(23 ^{11 к + 6} ) + 23 ^{9 к + 5} - 5(23 ^{7 к + 4} ) - 23 ^{5 к + 3} + 3(23 ^{3 к + 2} ) + 23 ^{к + 1}
24	24 ^{12 тыс. + 6} + 1	$\Phi _{12}(24^{2k+1})$	24 ^{4 к + 2} + 1	24 ^{4 к + 2} + 3(24 ^{2 к + 1} ) + 1	12(24 ^{3 тыс. + 1} ) + 12(24 ^тыс. )

Числа Люка имеют следующую аурифейлевскую факторизацию: ^[7] $L_{10k+5}$

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)

где - -ое число Люка, а - -ое число Фибоначчи .

L_{n}

n

F_{n}

n

История

В 1869 году, до открытия аурифейских факторизаций, Ландри [fr; es; de] , проделав колоссальный ручной труд, ^[8]^[9] получил следующее разложение на простые множители :

2^{58}+1=5\cdot 107367629\cdot 536903681.

Три года спустя, в 1871 году, Орифейль открыл природу этой факторизации; число для , с формулой из предыдущего раздела, раскладывается на множители следующим образом: ^[2]^[8] $2^{4k+2}+1$ $к=14$

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

Конечно, отсюда следует полная факторизация Ландри (исключая очевидный множитель 5). Общая форма факторизации была позже открыта Лукасом . [ ^2]

536903681 является примером гауссовой нормы Мерсенна . ^[9]

Ссылки

^ A. Granville, P. Pleasants (2006). "Aurifeuillian factorization" (PDF) . Math. Comp . 75 (253): 497–508. doi : 10.1090/S0025-5718-05-01766-7 .
^ abcd Вайсстейн, Эрик В. «Орифейская факторизация». MathWorld .
^ «Основные таблицы Каннингема».В конце таблиц 2LM, 3+, 5-, 6+, 7+, 10+, 11+ и 12+ приведены формулы, описывающие аурифейлевские факторизации.
^ Список аурифейских факторизаций циклотомических чисел (бесквадратные основания до 199)
^ Коэффициенты полиномов Люка C,D для всех бесквадратных оснований до 199
^ Коэффициенты полиномов Люка C,D для всех бесквадратных оснований до 998
^ Лукас Аурифейская примитивная часть
^ ab Целочисленная арифметика, Теория чисел – Факторизации Aurifeuillean, Numericana
^ ab Гауссовский Мерсенн, глоссарий Prime Pages

Внешние ссылки

Факторизация Орифея, Колин Баркер
Факторизации Орифея, Жерар П. Мишон
Поиск факторизаций, подобных Орифейлю
Онлайн-сбор факторов
Заметка об орифейлевских факторизациях
Факторизация Орифея

[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] Вайсстейн, Эрик В. «Орифейская факторизация». MathWorld .

[3] «Основные таблицы Каннингема».В конце таблиц 2LM, 3+, 5-, 6+, 7+, 10+, 11+ и 12+ приведены формулы, описывающие аурифейлевские факторизации.

[4] Список аурифейских факторизаций циклотомических чисел (бесквадратные основания до 199)

[5] Коэффициенты полиномов Люка C,D для всех бесквадратных оснований до 199

[6] Коэффициенты полиномов Люка C,D для всех бесквадратных оснований до 998

[7] Лукас Аурифейская примитивная часть

[numericana-8] Целочисленная арифметика, Теория чисел – Факторизации Aurifeuillean, Numericana

[primepages-9] Гауссовский Мерсенн, глоссарий Prime Pages