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

Чтобы узнать о других значениях, см. Фактор (значения) .

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

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

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

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

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

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

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

Целые числа

Основная статья: Целочисленная факторизация

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

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

Чтобы найти делитель q числа n , если таковой имеется, достаточно проверить все значения q такие, что 1 < q и q ² ≤ п . В самом деле, если r — делитель n такой, что r ² > n , то q = n / r — делитель n такой, что q ² ≤ п .

Если проверить значения q в порядке возрастания, первый найденный делитель обязательно будет простым числом, а сомножитель r = n / q не может иметь делителя меньше q . Таким образом, для получения полной факторизации достаточно продолжить алгоритм поиском делителя r , который не меньше q и не больше √ 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 · 693 . Продолжайте с 693 и 2 в качестве кандидата на первый делитель.
• 693 нечетно (2 не делитель), но кратно 3: 693 = 3 · 231 и n = 2 · 3 · 231 . Продолжайте с 231 и 3 в качестве первого делителя.
• 231 также кратно 3: 231 = 3 · 77 и, следовательно, n = 2 · 3. ² · 77 . Продолжайте с 77 и 3 в качестве первого делителя.
• Число 77 не кратно 3, поскольку сумма его цифр равна 14, а не кратно 3. Оно также не кратно 5, поскольку его последняя цифра равна 7. Следующий нечетный делитель, который нужно проверить, равен 7. Число 77 не кратно 3. 77 = 7 · 11 и, следовательно, n = 2 · 3 ² · 7 · 11 . Это показывает, что 7 — простое число (это легко проверить напрямую). Продолжайте с 11 и 7 в качестве кандидатов на первый делитель.
• Как 7 ² > 11 , один закончил. Таким образом, 11 — простое число, а факторизация простых чисел равна

1386 = 2 · 3 ² · 7 · 11 .

Выражения

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

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

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

$(x-a)(x-b)(x-c),$

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

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

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

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

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

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

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

Общие методы

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

Общий фактор

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

Например, $$6x^{3}y^{2}+8x^{4}y^{3}-10x^{5}y^{3}=2x^{3}y^{2}(3+4xy-5x^{2}y),$$поскольку 2 — наибольший общий делитель 6, 8 и 10, и $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 членов, полученных как произведение двух биномов . Хотя это и не часто, это может сработать и для более сложных примеров.

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

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

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

Другой пример — факторизация $x^{4}+1.$ Если ввести недействительный квадратный корень из –1 , обычно обозначаемый i , то получится разность квадратов $$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\right).$$Вычитание и добавление $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\right).$$Эти факторизации работают не только над комплексными числами, но и над любым полем , где либо –1, 2 или –2 является квадратом. В конечном поле произведение двух неквадратов является квадратом; это означает, что полином $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 , входящие в эти тождества, могут представлять любое подвыражение выражения, которое необходимо факторизовать).

Наглядное доказательство различий между двумя квадратами и двумя кубами

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

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

Например,

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

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

Визуализация биномиального разложения до 4-й степени

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

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

$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}$

В более общем плане коэффициенты развернутых форм $(a+b)^{n}$ и $(a-b)^{n}$ — биномиальные коэффициенты , стоящие в 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 являются действительными выражениями и требуются реальные множители, необходимо заменить каждую пару комплексно-сопряженных множителей ее произведением. В качестве комплексного сопряжения $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 , и $Q_{n}(x)$ — n- й круговой полином.

Например, $$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}),$$так как делители 6 — это 1, 2, 3, 6, а делители 12, не делящие 6, — это 4 и 12.

Полиномы

Основная статья: Факторизация полиномов

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

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

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

$P(r)=0.$

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

И наоборот, факторная теорема утверждает, что если 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}),$

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

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

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

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

Основная статья: Полиномиальная факторизация § Примитивная факторизация части – содержания

Каждый многочлен с рациональными коэффициентами может быть факторизован уникальным способом как произведение рационального числа и многочлена с целыми коэффициентами, который является примитивным (т. е. наибольший общий делитель коэффициентов равен 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/q.$ Наконец, при необходимости меняются знаки p и всех коэффициентов примитивной части.

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

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

Основная статья: Факторная теорема

Факторная теорема утверждает, что 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.$

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

Например, для $P(x)=x^{3}-3x+2,$ легко видеть, что сумма его коэффициентов равна 0, поэтому r = 1 является корнем. Поскольку r + 0 = 1 и $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 и постоянных коэффициентов в приведенном выше равенстве показывает, что если ${\tfrac {p}{q}}$ — рациональный корень в приведенной форме , то q — делитель $a_{0},$ и p является делителем $a_{n}.$ Следовательно, существует конечное число возможностей для p и q , которые можно систематически исследовать.

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

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

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

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

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

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

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

$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, дает рациональные корни, если таковые имеются.

Подводя итог, если $ax^{2}+bx+c$ имеет рациональные корни, существуют целые числа r и s такие $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$ является неотрицательным. В противном случае квадратичный многочлен не может быть разложен на непостоянные действительные множители.

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

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

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

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

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

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

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

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

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

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

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

$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-разложение», в котором матрица перестановок является третьим фактором.

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

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

См. также

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

Ссылки

• Бернсайд, Уильям Сноу ; Пантон, Артур Уильям (1960) [1912], Теория уравнений с введением в теорию бинарных алгебраических форм (первый том) , Дувр
• Диксон, Леонард Юджин (1922), Первый курс теории уравнений , Нью-Йорк: John Wiley & Sons
• Файт, Уильям Бенджамин (1921), Колледж алгебры (пересмотренный) , Бостон: DC Heath & Co.
• Кляйн, Феликс (1925), Элементарная математика с продвинутой точки зрения; Арифметика, Алгебра, Анализ , Дувр
• Селби, Сэмюэл М. (1970), Стандартные математические таблицы CRC (18-е изд.), The Chemical Rubber Co.

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

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