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

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

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

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

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

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

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

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

Целые числа [ править ]

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

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

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

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

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

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

${\displaystyle 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 = 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 . Когда выражение можно разложить на множители, факторы часто намного проще и, таким образом, могут дать некоторое представление о проблеме. Например,

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

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

${\displaystyle (x-a)(x-b)(x-c),}$

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

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

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

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

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

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

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

Общие методы [ править ]

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

Общий фактор [ править ]

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

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

${\displaystyle 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 и делит все члены.${\displaystyle x^{3}y^{2}}$

Группировка [ править ]

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

Например, чтобы фактор

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

можно заметить, что первые два члена имеют общий множитель x , а последние два члена имеют общий множитель y . Таким образом

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

Затем простой осмотр показывает общий множитель x + 5 , что приводит к факторизации

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

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

Добавление и вычитание терминов [ править ]

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

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

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

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

Однако может потребоваться факторизация с коэффициентами действительных чисел . Складывая, вычитая и группируя три члена, можно узнать квадрат бинома :${\displaystyle 2x^{2},}$

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

Вычитание и сложение также дает факторизацию:${\displaystyle 2x^{2}}$

${\displaystyle 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 - квадрат. В конечном поле произведение двух неквадратов является квадратом; это означает , что многочлен , который является неприводимым над целыми числами, приводит по модулю каждого простого числа . Например,${\displaystyle x^{4}+1,}$

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

${\displaystyle x^{4}+1\equiv (x^{2}+x-1)(x^{2}-x-1){\pmod {3}},\qquad }$поскольку ${\displaystyle 1^{2}\equiv -2{\pmod {3}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+2)(x^{2}-2){\pmod {5}},\qquad }$поскольку ${\displaystyle 2^{2}\equiv -1{\pmod {5}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+3x+1)(x^{2}-3x+1){\pmod {7}},\qquad }$поскольку ${\displaystyle 3^{2}\equiv 2{\pmod {7}}.}$

Узнаваемые узоры [ править ]

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

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

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

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

Например,

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

• Сумма / разница двух кубиков

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

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

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

${\displaystyle {\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- х степеней

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

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

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

• Разница, четная или нечетная экспонента

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

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

• Сумма, нечетная экспонента

${\displaystyle 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 , можно использовать предыдущую формулу (в «Сумма, нечетный показатель»), примененную к${\displaystyle (E^{q})^{p}+(F^{q})^{p}.}$

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

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

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

В бином поставляет модели , которые могут быть легко признаны из целых чисел , которые появляются в них

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

${\displaystyle a^{2}+2ab+b^{2}=(a+b)^{2}}$

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

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

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

В более общем смысле, коэффициенты развернутой формы и являются биномиальными коэффициентами , которые появляются в n- й строке треугольника Паскаля .${\displaystyle (a+b)^{n}}$${\displaystyle (a-b)^{n}}$

Корни единства [ править ]

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

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

за ${\displaystyle k=0,\ldots ,n-1.}$

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

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

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

${\displaystyle 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 - действительные выражения и кто-то хочет действительные множители, нужно заменить каждую пару комплексно сопряженных множителей их произведением. Поскольку комплексное сопряжение есть и ${\displaystyle e^{i\alpha }}$${\displaystyle e^{-i\alpha },}$

${\displaystyle \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 , и применяя обычные тригонометрические формулы :

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

${\displaystyle {\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 . Например,

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

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

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

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

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

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

где произведения берутся по всем делителям n или всем делителям 2 n, которые не делят n , и является n- м круговым полиномом.${\displaystyle Q_{n}(x)}$

Например,

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

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

Полиномы [ править ]

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

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

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

${\displaystyle P(r)=0.}$

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

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

${\displaystyle P(x)=(x-r)Q(x),}$

где Q ( х ) есть фактор евклидова деления на Р ( х ) = 0 по линейной (степени один) фактор х - г .

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

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

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

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

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

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

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

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

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

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

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

Факторизация примитивов и содержимого [ править ]

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

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

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

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

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

Использование факторной теоремы [ править ]

Теорема фактора гласит , что, если г является корнем из полинома

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

то есть P ( r ) = 0 , то есть факторизация

${\displaystyle P(x)=(x-r)Q(x),}$

куда

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

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

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

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

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

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

Рациональные корни [ править ]

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

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

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

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

${\displaystyle P(x)=(qx-p)Q(x),}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle -{\frac {b}{a}}-{\frac {r}{a}}=-{\frac {b+r}{a}}={\frac {s}{a}},}$

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

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

то есть

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

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

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

${\displaystyle 6x^{2}+13x+6.}$

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

${\displaystyle -{\frac {4}{6}}=-{\frac {2}{3}}\quad {\text{and}}\quad -{\frac {9}{6}}=-{\frac {3}{2}},}$

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

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

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

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

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

где и - два корня многочлена.${\displaystyle \alpha }$${\displaystyle \beta }$

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

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

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

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

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

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

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

где Q - полином.

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

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

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

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

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

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

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

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

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

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

Идеалы [ править ]

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

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

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

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

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

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

Матрицы [ править ]

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

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

• Wolfram Alpha тоже может разложить на множители .