Факторизация

Полином x ² + cx + d , где *a + b = c* и *ab = d* , можно разложить на ( *x + a* )( *x + b* ).

В математике факторизация (или факторизация , см. различия в английском написании ) или факторизация состоит в записи числа или другого математического объекта как продукта нескольких факторов , обычно меньших или более простых объектов одного и того же типа. Например, $3 \times 5$ — это целочисленная факторизация 15 $,$ а $(x - 2)(x + 2)$ – это полиномиальная факторизация x $2 - 4$ .

Факторизация обычно не считается значимой в системах счисления, обладающих делением , таких как действительные или комплексные числа , поскольку любое из них может быть тривиально записано так, как будто оно не равно нулю. Однако осмысленную факторизацию рационального числа или рациональной функции можно получить, записав его в самых простых терминах и разделив на множители его числитель и знаменатель. $х$ $(xy)\times (1/y)$ $y$

Факторизация впервые была рассмотрена древнегреческими математиками для целых чисел. Они доказали фундаментальную теорему арифметики , которая утверждает, что каждое положительное целое число можно разложить на множители в произведение простых чисел , которое нельзя далее разложить на целые числа, большие 1. Более того, эта факторизация уникальна с точностью до порядка множителей. Хотя факторизация целых чисел является своего рода обратной операцией умножения, она гораздо сложнее алгоритмически , и этот факт используется в криптосистеме RSA для реализации криптографии с открытым ключом .

Полиномиальная факторизация также изучалась на протяжении веков. В элементарной алгебре факторизация многочлена сводит проблему поиска его корней к поиску корней множителей. Многочлены с коэффициентами в целых числах или в поле обладают уникальным свойством факторизации — версией основной теоремы арифметики с заменой простых чисел неприводимыми многочленами . В частности, одномерный многочлен с комплексными коэффициентами допускает уникальную (с точностью до порядка) факторизацию на линейные многочлены : это версия основной теоремы алгебры . В этом случае факторизация может быть выполнена с помощью алгоритмов поиска корня . Случай многочленов с целыми коэффициентами является фундаментальным для компьютерной алгебры . Существуют эффективные компьютерные алгоритмы для вычисления (полной) факторизации внутри кольца многочленов с рациональными коэффициентами (см. факторизацию многочленов ).

Коммутативное кольцо , обладающее уникальным свойством факторизации, называется уникальной областью факторизации . Существуют системы счисления , такие как определенные кольца алгебраических целых чисел , которые не являются уникальными областями факторизации. Однако кольца целых алгебраических чисел удовлетворяют более слабому свойству дедекиндовых областей : идеалы однозначно факторизуются в простые идеалы .

Факторизация также может относиться к более общему разложению математического объекта на произведение меньших или более простых объектов. Например, каждая функция может быть включена в композицию сюръективной функции с инъективной функцией . Матрицы обладают многими видами матричной факторизации . Например, каждая матрица имеет уникальную факторизацию LUP как произведение нижней треугольной матрицы $L$ со всеми диагональными элементами, равными единице, верхней треугольной матрицы $U$ и матрицы перестановок $P$ ; это матричная формулировка метода исключения Гаусса .

Целые числа

Согласно фундаментальной теореме арифметики , каждое целое число больше 1 имеет уникальную (с точностью до порядка множителей) факторизацию на простые числа , которые представляют собой те целые числа, которые не могут быть далее разложены на множители в произведение целых чисел, больших единицы.

Для вычисления факторизации целого числа $n$ необходим алгоритм нахождения делителя $q$ числа $n$ или принятия решения о том, что $n$ является простым. Когда такой делитель найден, повторное применение этого алгоритма к факторам $q$ и $n / q$ дает в конечном итоге полную факторизацию $n$ . ^[1]

Чтобы найти делитель $q$ числа $n$ , если таковой имеется, достаточно проверить все значения $q$ такие, что 1 $< q$ и $q2 \leq n .$ Фактически, если $r$ — делитель $n$ такой, что $r 2 > n$ , то $q = n / r$ — делитель $n$ такой, что $q 2 ⩽ n$ .

Если проверить значения $q$ в порядке возрастания, первый найденный делитель обязательно будет простым числом, а сомножитель r $= n / q не$ может иметь делителя меньше $q$ . Таким образом, для получения полной факторизации достаточно продолжить алгоритм поиском делителя $r$ , который не меньше $q$ и не больше $\sqrt r$ .

Для применения метода нет необходимости проверять все значения $q .$ В принципе, достаточно проверить только простые делители. Для этого необходима таблица простых чисел, которую можно создать, например, с помощью решета Эратосфена . Поскольку метод факторизации выполняет по существу ту же работу, что и решето Эратосфена, обычно более эффективно проверять на делитель только те числа, для которых не сразу ясно, простые они или нет. Обычно можно продолжить, проверив 2, 3, 5 и числа > 5, последняя цифра которых равна 1, 3, 7, 9, а сумма цифр не кратна 3.

Этот метод хорошо работает для факторизации небольших целых чисел, но неэффективен для больших целых чисел. Например, Пьер де Ферма не смог обнаружить, что шестое число Ферма

1+2^{2^{5}}=1+2^{32}=4\,294\,967\,297

не является простым числом. Фактически, применение описанного выше метода потребует более10 000 делений для числа, состоящего из 10 десятичных цифр .

Существуют более эффективные алгоритмы факторинга. Однако они остаются относительно неэффективными, поскольку при нынешнем уровне техники невозможно факторизовать даже с помощью более мощных компьютеров число из 500 десятичных цифр, которое является произведением двух случайно выбранных простых чисел. Это обеспечивает безопасность криптосистемы RSA , которая широко используется для безопасного интернет -соединения.

Пример

Для разложения $n = 1386$ на простые числа:

Начнем с деления на 2: число четное, $n = 2 \cdot 693$ . Продолжайте с 693 и 2 в качестве кандидата на первый делитель.
693 нечетно (2 не делитель), но кратно 3: $693 = 3 \cdot 231$ и $n = 2 \cdot 3 \cdot 231$ . Продолжайте с 231 и 3 в качестве первого делителя.
231 также кратно 3: $231 = 3 \cdot 77$ и, следовательно, $n = 2 \cdot 3 2 \cdot 77$ . Продолжайте с 77 и 3 в качестве первого делителя.
Число 77 не кратно 3, поскольку сумма его цифр равна 14, а не кратно 3. Оно также не кратно 5, поскольку его последняя цифра равна 7. Следующий нечетный делитель, который нужно проверить, равен 7. Число 77 не кратно 3. $77 = 7 \cdot 11$ и, таким образом, $n = 2 \cdot 3 2 \cdot 7 \cdot 11$ . Это показывает, что 7 — простое число (это легко проверить напрямую). Продолжайте с 11 и 7 в качестве кандидатов на первый делитель.
Поскольку $72 > 11$ , человек закончил. Таким образом, 11 — простое число, а факторизация простых чисел равна

1386 = 2 \cdot 3 2 \cdot 7 \cdot 11

Выражения

Манипулирование выражениями является основой алгебры . Факторизация является одним из наиболее важных методов манипулирования выражениями по нескольким причинам. Если уравнение можно представить в факторизованной форме $E \cdot F = 0$ , то проблема решения уравнения распадается на две независимые (и, как правило, более простые) задачи $E = 0$ и $F = 0$ . Когда выражение можно факторизовать, факторы часто оказываются намного проще и, таким образом, могут дать некоторое представление о проблеме. Например,

x^{3}-ax^{2}-bx^{2}-cx^{2}+abx+acx+bcx-abc

имея 16 умножений, 4 вычитания и 3 сложения, можно включить в гораздо более простое выражение

{\ displaystyle (xa) (xb) (xc),}

всего с двумя умножениями и тремя вычитаниями. Более того, факторизованная форма сразу дает корни x = a , b , c как корни многочлена.

С другой стороны, факторизация не всегда возможна, а когда она возможна, факторы не всегда проще. Например, можно разложить на два неприводимых фактора и . $x^{10}-1$ $x-1$ $x^{9}+x^{8}+\cdots +x^{2}+x+1$

Для нахождения факторизаций были разработаны различные методы; некоторые из них описаны ниже.

Решение алгебраических уравнений можно рассматривать как задачу полиномиальной факторизации . Фактически, фундаментальную теорему алгебры можно сформулировать следующим образом: каждый многочлен от $x$ степени $n$ с комплексными коэффициентами можно разложить на $n$ линейных множителей для $i$ $= 1, ...,$ $n$ , где a $i$ $s$ - корни полинома. ^[2] Несмотря на то, что структура факторизации в этих случаях известна, a $is$ $обычно$ не может быть вычислена в терминах радикалов ( корней n ^-й степени) по теореме Абеля-Руффини . В большинстве случаев лучшее, что можно сделать, — это вычислить приблизительные значения корней с помощью алгоритма поиска корней . $xa_{i},$

История факторизации выражений

Систематическое использование алгебраических манипуляций для упрощения выражений (точнее уравнений ) можно отнести к 9 веку, благодаря книге аль-Хорезми « Сборник вычислений путем завершения и балансировки» , в названии которой описаны два таких типа манипуляций.

Однако даже для решения квадратных уравнений метод факторизации не использовался до работы Харриота, опубликованной в 1631 году, через десять лет после его смерти . ^[3] В своей книге Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas Харриот нарисовал таблицы для сложения, вычитания, умножения и деления одночленов , биномов и трехчленов . Затем, во втором разделе, он составил уравнение $aa - ba + ca = + bc$ и показал, что оно соответствует форме умножения, которую он предоставил ранее, давая факторизацию $(a - b)(a + c)$ . ^[4]

Общие методы

Следующие методы применяются к любому выражению, которое является суммой или может быть преобразовано в сумму. Поэтому они чаще всего применяются к многочленам , хотя их также можно применять, когда члены суммы не являются мономами , то есть члены суммы являются произведением переменных и констант.

Общий делитель

Может случиться так, что все члены суммы являются произведениями и что некоторые факторы являются общими для всех членов. В этом случае распределительный закон позволяет исключить этот общий фактор. Если таких общих факторов несколько, то предпочтительно выделить наибольший из таких общих факторов. Кроме того, если есть целые коэффициенты, можно выделить наибольший общий делитель этих коэффициентов.

Например, ^[5]

6x^{3}y^{2}+8x^{4}y^{3} -10x^{5}y^{3}=2x^{3}y^{2}(3+4xy -5x^{2}y),

x^{3}y^{2}

Группировка

Условия группировки могут позволить использовать другие методы факторизации.

Например, факторизовать

4x^{2}+20x+3xy+15y,

x

y

4x^{2}+20x+3xy+15y=(4x^{2}+20x)+(3xy+15y)=4x(x+5)+3y(x+5).

x + 5

4x^{2}+20x+3xy+15y=(4x+3y)(x+5).

В общем, это работает для сумм 4 членов, полученных как произведение двух биномов . Хотя это и не часто, это может сработать и для более сложных примеров.

Добавление и вычитание терминов

Иногда некоторая группировка терминов обнаруживает часть узнаваемой закономерности. Затем полезно добавлять и вычитать члены, чтобы завершить шаблон.

Типичное использование этого метода — завершение метода квадратов для получения квадратичной формулы .

Другим примером является факторизация. Если ввести недействительный квадратный корень из –1 , обычно обозначаемый $i$ , то получится разность квадратов. $x^{4}+1.$

x^{4}+1 = (x^{2}+i)(x^{2}-i).

вещественными бинома

2x^{2},

x^{4}+1=(x^{4}+2x^{2}+1)-2x^{2}=(x^{2}+1)^{2}-\left( x{\sqrt {2}}\right)^{2}=\left(x^{2}+x{\sqrt {2}}+1\right)\left(x^{2}-x{\ sqrt {2}}+1\вправо).

2x^{2}

x^{4}+1=(x^{4}-2x^{2}+1)+2x^{2}=(x^{2}-1)^{2}+\left( x{\sqrt {2}}\right)^{2}=\left(x^{2}+x{\sqrt {-2}}-1\right)\left(x^{2}-x{ \sqrt {-2}}-1\вправо).

полем конечном поле полином , неприводимый по модулю простого числа

x^{4}+1,

x^{4}+1\equiv (x+1)^{4}{\pmod {2}};

x^{4}+1\equiv (x^{2}+x-1)(x^{2}-x-1){\pmod {3}},

1^{2}\equiv -2{\pmod {3}};

x^{4}+1\equiv (x^{2}+2)(x^{2}-2){\pmod {5}},

2^{2}\equiv -1{\pmod {5}};

x^{4}+1\equiv (x^{2}+3x+1)(x^{2}-3x+1){\pmod {7}},

3^{2}\equiv 2{\pmod {7}}.

Узнаваемые узоры

Многие тождества обеспечивают равенство суммы и произведения. Вышеупомянутые методы можно использовать для того, чтобы в выражении появлялась сумма некоторой идентичности, которая, следовательно, может быть заменена произведением.

Ниже приведены тождества, левые части которых обычно используются в качестве шаблонов (это означает, что переменные $E$ и $F$ , входящие в эти тождества, могут представлять любое подвыражение выражения, которое необходимо факторизовать). ^[6]

Разница двух квадратов

E^{2}-F^{2}=(E+F)(EF)

Например,

{\begin{aligned}a^{2}+&2ab+b^{2}-x^{2}+2xy-y^{2}\\&=(a^{2}+2ab+b^{2})-(x^{2}-2xy+y^{2})\\&=(a+b)^{2}-(x-y)^{2}\\&=(a+b+x-y)(a+b-x+y).\end{aligned}}

Сумма/разность двух кубов

E^{3}+F^{3}=(E+F)(E^{2}-EF+F^{2})

E^{3}-F^{3}=(E-F)(E^{2}+EF+F^{2})

Разница двух четвертых степеней

{\begin{aligned}E^{4}-F^{4}&=(E^{2}+F^{2})(E^{2}-F^{2})\\&=(E^{2}+F^{2})(E+F)(E-F)\end{aligned}}

Сумма/разность двух $n-ных$ степеней

В следующих тождествах факторы часто могут быть дополнительно факторизованы:

Разница, даже показатель

E^{2n}-F^{2n}=(E^{n}+F^{n})(E^{n}-F^{n})

Разница, четный или нечетный показатель

E^{n}-F^{n}=(E-F)(E^{n-1}+E^{n-2}F+E^{n-3}F^{2}+\cdots +EF^{n-2}+F^{n-1})

Это пример, показывающий, что факторы могут быть намного больше, чем факторизованная сумма.

Сумма, нечетный показатель

E^{n}+F^{n}=(E+F)(E^{n-1}-E^{n-2}F+E^{n-3}F^{2}-\cdots -EF^{n-2}+F^{n-1})

(получено заменой

F

на

- F

в предыдущей формуле)

Сумма, четная степень

Если показатель степени представляет собой степень двойки, то выражение, как правило, невозможно факторизовать без введения комплексных чисел (если

E

F

содержат комплексные числа, это может быть не так). Если n имеет нечетный делитель, то есть если

n = pq

с нечетным

p

, можно использовать предыдущую формулу (в разделе «Сумма, нечетный показатель степени»), примененную к

(E^{q})^{p}+(F^{q})^{p}.

Трехчлены и кубические формулы

{\begin{aligned}&x^{2}+y^{2}+z^{2}+2(xy+yz+xz)=(x+y+z)^{2}\\&x^{3}+y^{3}+z^{3}-3xyz=(x+y+z)(x^{2}+y^{2}+z^{2}-xy-xz-yz)\\&x^{3}+y^{3}+z^{3}+3x^{2}(y+z)+3y^{2}(x+z)+3z^{2}(x+y)+6xyz=(x+y+z)^{3}\\&x^{4}+x^{2}y^{2}+y^{4}=(x^{2}+xy+y^{2})(x^{2}-xy+y^{2}).\end{aligned}}

Биномиальные разложения

Биномиальная теорема предоставляет шаблоны, которые можно легко распознать по встречающимся в них целым числам.

В низкой степени:

a^{2}+2ab+b^{2}=(a+b)^{2}

a^{2}-2ab+b^{2}=(a-b)^{2}

a^{3}+3a^{2}b+3ab^{2}+b^{3}=(a+b)^{3}

a^{3}-3a^{2}b+3ab^{2}-b^{3}=(a-b)^{3}

В более общем смысле, коэффициенты расширенных форм и являются биномиальными коэффициентами , которые появляются в

n-

й строке треугольника Паскаля .

(a+b)^{n}

(a-b)^{n}

Корни единства

Корни $n-$ й степени из единицы — это комплексные числа, каждое из которых является корнем многочлена. Таким образом, они являются числами. $x^{n}-1.$

e^{2ik\pi /n}=\cos {\tfrac {2\pi k}{n}}+i\sin {\tfrac {2\pi k}{n}}

k=0,\ldots ,n-1.

Отсюда следует, что для любых двух выражений $E$ и $F$ имеем:

E^{n}-F^{n}=(E-F)\prod _{k=1}^{n-1}\left(E-Fe^{2ik\pi /n}\right)

E^{n}+F^{n}=\prod _{k=0}^{n-1}\left(E-Fe^{(2k+1)i\pi /n}\right)\qquad {\text{if }}n{\text{ is even}}

E^{n}+F^{n}=(E+F)\prod _{k=1}^{n-1}\left(E+Fe^{2ik\pi /n}\right)\qquad {\text{if }}n{\text{ is odd}}

Если $E$ и $F$ являются действительными выражениями и требуются реальные множители, необходимо заменить каждую пару комплексно-сопряженных множителей ее произведением. Поскольку комплексное сопряжение is и $e^{i\alpha }$ $e^{-i\alpha },$

\left(a-be^{i\alpha }\right)\left(a-be^{-i\alpha }\right)=a^{2}-ab\left(e^{i\alpha }+e^{-i\alpha }\right)+b^{2}e^{i\alpha }e^{-i\alpha }=a^{2}-2ab\cos \,\alpha +b^{2},

k

n - k

n + 1 - k

тригонометрические формулы

{\begin{aligned}E^{2n}-F^{2n}&=(E-F)(E+F)\prod _{k=1}^{n-1}\left(E^{2}-2EF\cos \,{\tfrac {k\pi }{n}}+F^{2}\right)\\&=(E-F)(E+F)\prod _{k=1}^{n-1}\left(E^{2}+2EF\cos \,{\tfrac {k\pi }{n}}+F^{2}\right)\end{aligned}}

{\begin{aligned}E^{2n}+F^{2n}&=\prod _{k=1}^{n}\left(E^{2}+2EF\cos \,{\tfrac {(2k-1)\pi }{2n}}+F^{2}\right)\\&=\prod _{k=1}^{n}\left(E^{2}-2EF\cos \,{\tfrac {(2k-1)\pi }{2n}}+F^{2}\right)\end{aligned}}

Косинусы , которые появляются в этих факторизациях, являются алгебраическими числами и могут быть выражены через радикалы (это возможно, потому что их группа Галуа циклическая); однако эти радикальные выражения слишком сложны для использования, за исключением низких значений $n$ . Например,

a^{4}+b^{4}=(a^{2}-{\sqrt {2}}ab+b^{2})(a^{2}+{\sqrt {2}}ab+b^{2}).

a^{5}-b^{5}=(a-b)\left(a^{2}+{\frac {1-{\sqrt {5}}}{2}}ab+b^{2}\right)\left(a^{2}+{\frac {1+{\sqrt {5}}}{2}}ab+b^{2}\right),

a^{5}+b^{5}=(a+b)\left(a^{2}-{\frac {1-{\sqrt {5}}}{2}}ab+b^{2}\right)\left(a^{2}-{\frac {1+{\sqrt {5}}}{2}}ab+b^{2}\right),

Часто требуется факторизация с рациональными коэффициентами. Такая факторизация включает в себя круговые полиномы . Чтобы выразить рациональную факторизацию сумм и разностей или степеней, нам нужны обозначения для усреднения многочлена : если его усреднение является двумерным многочленом . Тогда имеем $P(x)=a_{0}x^{n}+a_{i}x^{n-1}+\cdots +a_{n},$ ${\overline {P}}(x,y)=a_{0}x^{n}+a_{i}x^{n-1}y+\cdots +a_{n}y^{n}.$

E^{n}-F^{n}=\prod _{k\mid n}{\overline {Q}}_{n}(E,F),

E^{n}+F^{n}=\prod _{k\mid 2n,k\not \mid n}{\overline {Q}}_{n}(E,F),

n

2 n

n

n-

Q_{n}(x)

Например,

a^{6}-b^{6}={\overline {Q}}_{1}(a,b){\overline {Q}}_{2}(a,b){\overline {Q}}_{3}(a,b){\overline {Q}}_{6}(a,b)=(a-b)(a+b)(a^{2}-ab+b^{2})(a^{2}+ab+b^{2}),

a^{6}+b^{6}={\overline {Q}}_{4}(a,b){\overline {Q}}_{12}(a,b)=(a^{2}+b^{2})(a^{4}-a^{2}b^{2}+b^{4}),

Полиномы

Для многочленов факторизация тесно связана с проблемой решения алгебраических уравнений . Алгебраическое уравнение имеет вид

P(x)\ \,{\stackrel {\text{def}}{=}}\ \,a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n}=0,

где $P (x)$ — многочлен от $x$ , причем решение этого уравнения (также называемое корнем многочлена) — это значение $r$ от $x$ такое, что $a_{0}\neq 0.$

P(r)=0.

Если это факторизация $P$ $($ $x$ $) = 0$ как произведение двух многочленов, то корни $P$ $($ $x$ $)$ представляют собой объединение корней $Q$ $($ $x$ $)$ и корней $R$ $($ $x$ $)$ . Таким образом, решение $P$ $($ $x$ $) = 0$ сводится к более простым задачам решения $Q$ $($ $x$ $) = 0$ и $R$ $($ $x$ $) = 0$ . $P(x)=Q(x)R(x)$

И наоборот, факторная теорема утверждает, что если $r$ является корнем $P (x) = 0$ , то $P (x)$ можно факторизовать как

P(x)=(x-r)Q(x),

где $Q (x)$ — частное евклидова деления P $(x) = 0$ на линейный (первой степени) множитель $x - r$ .

Если коэффициенты $P (x)$ являются действительными или комплексными числами, фундаментальная теорема алгебры утверждает, что $P (x)$ имеет действительный или комплексный корень. Рекурсивно используя факторную теорему, получаем, что

P(x)=a_{0}(x-r_{1})\cdots (x-r_{n}),

где действительные или комплексные корни $P$ , некоторые из которых, возможно, повторяются. Эта полная факторизация уникальна с точностью до порядка факторов. $r_{1},\ldots ,r_{n}$

Если коэффициенты $P (x)$ действительны, обычно требуется факторизация, в которой факторы имеют реальные коэффициенты. В этом случае полная факторизация может иметь несколько квадратичных множителей (второй степени). Эту факторизацию можно легко вывести из приведенной выше полной факторизации. Фактически, если $r = a + ib$ — невещественный корень $P (x)$ , то его комплексно-сопряженный элемент $s = a — ib$ также является корнем $P (x)$ . Итак, продукт

(x-r)(x-s)=x^{2}-(r+s)x+rs=x^{2}-2ax+a^{2}+b^{2}

является фактором $P (x)$ с действительными коэффициентами. Повторение этого для всех нереальных факторов дает факторизацию с линейными или квадратичными реальными факторами.

Для вычисления этих действительных или комплексных факторизаций нужны корни многочлена, которые не могут быть вычислены точно, а только аппроксимированы с использованием алгоритмов поиска корней .

На практике большинство представляющих интерес алгебраических уравнений имеют целые или рациональные коэффициенты, и может потребоваться факторизация с факторами одного и того же типа. Фундаментальную теорему арифметики можно обобщить на этот случай, заявив, что многочлены с целыми или рациональными коэффициентами обладают уникальным свойством факторизации . Точнее, каждый многочлен с рациональными коэффициентами можно факторизовать в произведение

P(x)=q\,P_{1}(x)\cdots P_{k}(x),

где $q$ — рациональное число и представляют собой непостоянные многочлены с целыми коэффициентами, которые являются неприводимыми и примитивными ; это означает, что ни один из них не может быть записан как произведение двух полиномов (с целыми коэффициентами), которые не равны ни 1, ни –1 (целые числа считаются полиномами нулевой степени). Более того, эта факторизация уникальна с точностью до порядка факторов и знаков факторов. $P_{1}(x),\ldots ,P_{k}(x)$ $P_{i}(x)$

Существуют эффективные алгоритмы вычисления этой факторизации, которые реализованы в большинстве систем компьютерной алгебры . См. Факторизацию полиномов . К сожалению, эти алгоритмы слишком сложны, чтобы их можно было использовать для вычислений на бумаге и карандаше. Помимо описанных выше эвристик, для ручных вычислений подходят лишь несколько методов, которые обычно работают только для полиномов низкой степени с небольшим количеством ненулевых коэффициентов. Основные такие методы описаны в следующих подразделах.

Факторизация примитивных частей и контента

Каждый многочлен с рациональными коэффициентами может быть факторизован уникальным способом как произведение рационального числа и многочлена с целыми коэффициентами, который является примитивным (т. е. наибольший общий делитель коэффициентов равен 1) и имеет положительный ведущий коэффициент (коэффициент члена высшей степени). Например:

-10x^{2}+5x+5=(-5)\cdot (2x^{2}-x-1)

{\frac {1}{3}}x^{5}+{\frac {7}{2}}x^{2}+2x+1={\frac {1}{6}}(2x^{5}+21x^{2}+12x+6)

В этой факторизации рациональное число называется содержимым , а примитивный многочлен — примитивной частью . Вычисление этой факторизации можно выполнить следующим образом: во-первых, привести все коэффициенты к общему знаменателю, чтобы получить частное по целому числу $q$ многочлена с целыми коэффициентами. Затем делят больший общий делитель $p$ коэффициентов этого многочлена для получения примитивной части, причем содержание таково . Наконец, при необходимости, меняют знаки $p$ и всех коэффициентов примитивной части. $p/q.$

Эта факторизация может дать результат, превышающий исходный полином (обычно, когда имеется много взаимно простых знаменателей), но даже в этом случае примитивной частью обычно легче манипулировать для дальнейшей факторизации.

Используя факторную теорему

Факторная теорема утверждает, что если $r$ является корнем многочлена

P(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n},

что означает $P (r) = 0$ , тогда существует факторизация

P(x)=(x-r)Q(x),

где

Q(x)=b_{0}x^{n-1}+\cdots +b_{n-2}x+b_{n-1},

с . Тогда полиномиальное длинное деление или синтетическое деление дают: $a_{0}=b_{0}$

b_{i}=a_{0}r^{i}+\cdots +a_{i-1}r+a_{i}\ {\text{ for }}\ i=1,\ldots ,n{-}1.

Это может быть полезно, когда кто-то знает или может угадать корень многочлена.

Например, легко увидеть, что сумма его коэффициентов равна 0, поэтому $r$ $= 1$ является корнем. Поскольку $r$ $+ 0 = 1$ и имеем $P(x)=x^{3}-3x+2,$ $r^{2}+0r-3=-2,$

x^{3}-3x+2=(x-1)(x^{2}+x-2).

Рациональные корни

Для многочленов с рациональными числовыми коэффициентами можно искать корни, которые являются рациональными числами. Примитивная факторизация по частям (см. выше) сводит задачу поиска рациональных корней к случаю многочленов с целыми коэффициентами, не имеющими нетривиального общего делителя .

Если – рациональный корень такого многочлена $x={\tfrac {p}{q}}$

P(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n},

факторная теорема показывает, что существует факторизация

P(x)=(qx-p)Q(x),

где оба фактора имеют целые коэффициенты (тот факт, что $Q$ имеет целые коэффициенты, следует из приведенной выше формулы для частного $P (x)$ по ). $x-p/q$

Сравнение коэффициентов степени $n$ и постоянных коэффициентов в приведенном выше равенстве показывает, что если — рациональный корень в приведенной форме , то $q$ — делитель , а $p$ — делитель Следовательно, существует конечное число возможностей для $p$ и $q$ , которые можно систематически исследовать. ^[7] ${\tfrac {p}{q}}$ $a_{0},$ $a_{n}.$

Например, если полином

P(x)=2x^{3}-7x^{2}+10x-6

имеет рациональный корень с $q$ $> 0$ , то $p$ должно делить 6; то есть и $q$ должно делить 2, то есть. Более того, если $x$ $< 0$ , все члены многочлена отрицательны, и, следовательно, корень не может быть отрицательным. То есть нужно иметь ${\tfrac {p}{q}}$ $p\in \{\pm 1,\pm 2,\pm 3,\pm 6\},$ $q\in \{1,2\}.$

{\tfrac {p}{q}}\in \{1,2,3,6,{\tfrac {1}{2}},{\tfrac {3}{2}}\}.

Непосредственное вычисление показывает, что только это корень, поэтому другого рационального корня быть не может. Применение факторной теоремы в конечном итоге приводит к факторизации ${\tfrac {3}{2}}$ $2x^{3}-7x^{2}+10x-6=(2x-3)(x^{2}-2x+2).$

Квадратичный метод переменного тока

Вышеупомянутый метод может быть адаптирован для квадратичных многочленов , что приводит к методу факторизации переменного тока . ^[8]

Рассмотрим квадратичный полином

P(x)=ax^{2}+bx+c

с целыми коэффициентами. Если он имеет рациональный корень, его знаменатель должен делить $a$ нацело, и его можно записать как возможно приводимую дробь . По формулам Виеты другой корень равен $r_{1}={\tfrac {r}{a}}.$ $r_{2}$

r_{2}=-{\frac {b}{a}}-r_{1}=-{\frac {b}{a}}-{\frac {r}{a}}=-{\frac {b+r}{a}}={\frac {s}{a}},

Таким образом, второй корень также рационален, и вторая формула Виеты дает $s=-(b+r).$ $r_{1}r_{2}={\frac {c}{a}}$

{\frac {s}{a}}{\frac {r}{a}}={\frac {c}{a}},

то есть

rs=ac\quad {\text{and}}\quad r+s=-b.

Проверка всех пар целых чисел, произведение которых равно $ac$ , дает рациональные корни, если таковые имеются.

Таким образом, если имеет рациональные корни, то существуют целые числа $r$ и $s$ , такие как и (конечное число случаев для проверки), а корни равны и . Другими словами, имеется факторизация $ax^{2}+bx+c$ $rs=ac$ $r+s=-b$ ${\tfrac {r}{a}}$ ${\tfrac {s}{a}}.$

a(ax^{2}+bx+c)=(ax-r)(ax-s).

Например, рассмотрим квадратичный полином

6x^{2}+13x+6.

Проверка факторов $ac = 36$ приводит к $4 + 9 = 13 = b$ , давая два корня

r_{1}=-{\frac {4}{6}}=-{\frac {2}{3}}\quad {\text{and}}\quad r_{2}=-{\frac {9}{6}}=-{\frac {3}{2}},

и факторизация

6x^{2}+13x+6=6(x+{\tfrac {2}{3}})(x+{\tfrac {3}{2}})=(3x+2)(2x+3).

Использование формул для корней полинома

Любой одномерный квадратичный многочлен можно разложить по квадратичной формуле : $ax^{2}+bx+c$

ax^{2}+bx+c=a(x-\alpha )(x-\beta )=a\left(x-{\frac {-b+{\sqrt {b^{2}-4ac}}}{2a}}\right)\left(x-{\frac {-b-{\sqrt {b^{2}-4ac}}}{2a}}\right),

где и – два корня многочлена. $\alpha$ $\beta$

Если все $a, b, c$ вещественны , то факторы действительны тогда и только тогда, когда дискриминант неотрицательен. В противном случае квадратичный многочлен не может быть разложен на непостоянные действительные множители. $b^{2}-4ac$

Квадратичная формула справедлива, когда коэффициенты принадлежат любому полю характеристики , отличной от двух, и, в частности, для коэффициентов конечного поля с нечетным числом элементов. ^[9]

Существуют также формулы для корней многочленов кубической и четвертой степени , которые, вообще говоря, слишком сложны для практического использования. Теорема Абеля –Руффини показывает, что не существует общих корневых формул в терминах радикалов для многочленов пятой степени и выше.

Использование отношений между корнями

Может случиться так, что кто-то знает некоторую связь между корнями многочлена и его коэффициентами. Использование этих знаний может помочь факторизовать полином и найти его корни. Теория Галуа основана на систематическом изучении связей между корнями и коэффициентами, к которым относятся формулы Виеты .

Здесь мы рассматриваем более простой случай, когда два корня многочлена удовлетворяют соотношению $x_{1}$ $x_{2}$ $P(x)$

x_{2}=Q(x_{1}),

где $Q$ — многочлен.

Это означает, что является общим корнем и, следовательно, является корнем наибольшего общего делителя этих двух многочленов. Отсюда следует, что этот наибольший общий делитель является непостоянным множителем алгоритма Евклида для многочленов, позволяющего вычислить этот наибольший общий делитель. $x_{1}$ $P(Q(x))$ $P(x).$ $P(x).$

Например, ^[10] если кто-то знает или догадывается, что: имеет два корня , сумма которых равна нулю, можно применить алгоритм Евклида к и Первый шаг деления состоит в добавлении к получению остатка $P(x)=x^{3}-5x^{2}-16x+80$ $P(x)$ $P(-x).$ $P(x)$ $P(-x),$

-10(x^{2}-16).

Затем деление на дает ноль в качестве нового остатка и $x$ $- 5$ в качестве частного, что приводит к полной факторизации. $P(x)$ $x^{2}-16$

x^{3}-5x^{2}-16x+80=(x-5)(x-4)(x+4).

Уникальные домены факторизации

Целые числа и многочлены над полем обладают свойством уникальной факторизации, то есть каждый ненулевой элемент может быть разложен на произведение обратимого элемента (единицы ± 1 в случае целых чисел) и произведения неприводимых элементов ( простые числа , в случае целых чисел), и эта факторизация уникальна вплоть до перестановки множителей и смещения единиц среди множителей. Целочисленные домены , обладающие этим свойством, называются уникальными доменами факторизации (UFD).

Наибольшие общие делители существуют в UFD, и наоборот, каждая область целостности, в которой существуют наибольшие общие делители, является UFD. Каждая область главных идеалов является UFD.

Евклидова область — это целая область, в которой определено евклидово деление , аналогичное делению целых чисел. Каждая евклидова область является областью главного идеала и, следовательно, UFD.

В евклидовой области евклидово деление позволяет определить евклидов алгоритм для вычисления наибольших общих делителей. Однако это не означает существования алгоритма факторизации. Существует явный пример поля F $такого$ , что не может существовать никакого алгоритма факторизации в евклидовой области $F [x]$ одномерных многочленов над $F.$

Идеалы

В теории алгебраических чисел изучение диофантовых уравнений привело математиков в 19 веке к введению обобщений целых чисел , называемых целыми алгебраическими числами . Первым кольцом алгебраических целых чисел , которые были рассмотрены, были целые числа Гаусса и целые числа Эйзенштейна , которые разделяют с обычными целыми числами свойство быть областями главных идеалов и, таким образом, обладают уникальным свойством факторизации .

К сожалению, вскоре выяснилось, что большинство колец целых алгебраических чисел не являются главными и не имеют однозначной факторизации. Самый простой пример, в котором $\mathbb {Z} [{\sqrt {-5}}],$

9=3\cdot 3=(2+{\sqrt {-5}})(2-{\sqrt {-5}}),

и все эти факторы неустранимы .

Отсутствие уникальной факторизации является основной трудностью при решении диофантовых уравнений. Например, многие неправильные доказательства Великой теоремы Ферма (вероятно, включая «поистине чудесное доказательство Ферма , которое эти поля слишком узки, чтобы вместить» ) были основаны на неявном предположении об уникальной факторизации.

Эту трудность разрешил Дедекинд , доказавший, что кольца целых алгебраических чисел имеют единственную факторизацию идеалов : в этих кольцах каждый идеал является произведением простых идеалов , и эта факторизация единственна до порядка множителей. Целые области , обладающие этим уникальным свойством факторизации, теперь называются доменами Дедекинда . У них есть много замечательных свойств, которые делают их фундаментальными в теории алгебраических чисел.

Матрицы

Кольца матриц некоммутативны и не имеют уникальной факторизации: вообще существует много способов записи матрицы как произведения матриц. Таким образом, задача факторизации состоит в нахождении факторов заданных типов. Например, LU-разложение дает матрицу как произведение нижней треугольной матрицы на верхнюю треугольную матрицу . Поскольку это не всегда возможно, обычно рассматривают «LUP-разложение», в котором матрица перестановок является третьим фактором.

См. раздел «Разложение матрицы» , где описаны наиболее распространенные типы факторизации матрицы.

Логическая матрица представляет собой бинарное отношение , а умножение матрицы соответствует композиции отношений . Разложение отношения посредством факторизации служит для профилирования природы отношения, например, дифункционального отношения.

Смотрите также

Метод факторизации Эйлера для целых чисел
Метод факторизации Ферма для целых чисел
Моноидная факторизация
Мультипликативный раздел
Таблица гауссовских целочисленных факторизаций

Примечания

^ Харди; Райт (1980), Введение в теорию чисел (5-е изд.), Oxford Science Publications, ISBN 978-0198531715
^ Кляйн 1925, стр. 101–102.
^ В Сэнфорде, Вера (2008) [1930], Краткая история математики , Прочтите книги, ISBN 9781409727101, автор отмечает: «Ввиду того, что в настоящее время уделяется внимание решению квадратных уравнений путем факторизации, интересно отметить, что этот метод не использовался до работы Харриота в 1631 году».
^ Харриот, Т. (1631), Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas (на латыни), Apud Robertum Barker, typographum regium
^ Файт 1921, с. 19
^ Селби 1970, с. 101
^ Диксон 1922, с. 27
↑ Стовер, Кристофер, «Метод переменного тока», Mathworld , заархивировано из оригинала 12 ноября 2014 г.
^ В поле характеристики 2 имеется 2 = 0, и формула производит деление на ноль.
^ Бернсайд и Пантон 1960, с. 38

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

Найдите факторизацию или факторизацию в Викисловаре, бесплатном словаре.

Wolfram Alpha тоже может факторизовать.