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

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

Примеры

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

Таким образом, когда

b=s^{2}\cdot t

с безквадратным

t

, и

n

соответствует

t

модуль

2t

, то если

t

соответствует 1 модулю 4,

b^{n}-1

иметь аурифейлеву факторизацию, в противном случае

b^{n}+1

имеют аурифейлеву факторизацию.

Когда число имеет определенную форму (точное выражение зависит от основания), можно использовать факторизацию Аурифейля, которая дает произведение двух или трех чисел. Следующие уравнения дают коэффициенты Орифейля для баз проекта Каннингема как произведение 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 ]})

б	Число	( C - D ) * ( C + D ) знак равно L * M	Ф	С	Д
2	2 ^{4 k + 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 k + 2} + 3(5 ^{2к + 1}) + 1	5 ^{3 тыс. + 2} + 5 ^{к + 1}
6	6 ^{12 тыс. + 6} + 1	$\Phi _{12}(6^{2k+1})$	6 ^{4 k + 2} + 1	6 ^{4 k + 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 k + 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 k + 2} + 1	10 ^{8 тыс. + 4} + 5(10 ^{6 тыс. + 3}) + 7(10 ^{4 k + 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 k + 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 k + 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 k + 2} + 1	14 ^{12 тыс. + 6} + 7(14 ^{10 тысяч + 5}) + 3(14 ^{8 тыс. + 4}) - 7(14 ^{6 тыс. + 3}) + 3(14 ^{4 k + 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 k + 2} - 15 ^{2к + 1} + 1	15 ^{8 тыс. + 4} + 8(15 ^{6 тыс. + 3}) + 13(15 ^{4 k + 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 k + 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 k + 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 k + 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 k + 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 k + 2} - 21 ^{2к + 1} - 1	21 ^{12 тыс. + 6} + 10(21 ^{10 тысяч + 5}) + 13(21 ^{8 тыс. + 4}) + 7(21 ^{6 тыс. + 3}) + 13(21 ^{4 k + 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 k + 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 k + 2}) + 11(22 ^{2к + 1}) + 1	22 ^{19 тысяч + 10} + 4(22 ^{17 тыс. + 9}) + 7(22 ^{15 тысяч + 8}) + 6(22 ^{13к + 7}) + 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 k + 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 k + 2} + 1	24 ^{4 k + 2} + 3(24 ^{2к + 1}) + 1	12(24 ^{3 тыс. + 1}) + 12(24 ^к)

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

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 году, до открытия аурифейлевых факторизаций, Ландри [ фр ; эс ; de ] , благодаря огромным ручным усилиям, ^{[ 8 ]}^{[ 9 ]} получил следующую факторизацию на простые числа :

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

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

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

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

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

Ссылки

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

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

[1] А. Гранвилл, П. Плезантс (2006). «Факторизация Орифейля» (PDF) . Математика. Комп . 75 (253): 497–508. дои : 10.1090/S0025-5718-05-01766-7 .

[Wolfram-2] Jump up to: ^а ^б ^с ^д Вайсштейн, Эрик В. «Факторизация Орифейля» . Математический мир .

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

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

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

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

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

[numericana-8] Jump up to: ^а ^б Целочисленная арифметика, Теория чисел – Факторизации Орифейля , Numericana

[primepages-9] Jump up to: ^а ^б Гауссовский Мерсенн , Prime Pages глоссарий

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]