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

(Математическое) разложение в произведение

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

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

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

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

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

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

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

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

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

Общие методы

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

Общий фактор

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

Например, ^[5], поскольку 2 является наибольшим общим делителем 6, 8 и 10 и делит все члены. $${\displaystyle 6x^{3}y^{2}+8x^{4}y^{3}-10x^{5}y^{3}=2x^{3}y^{2}(3+4xy-5x^{2}y),}$$ ${\displaystyle x^{3}y^{2}}$

Группировка

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

Например, для факторизации можно заметить, что первые два члена имеют общий множитель x , а последние два члена имеют общий множитель y . Таким образом , тогда простой осмотр показывает общий множитель x + 5 , что приводит к факторизации $${\displaystyle 4x^{2}+20x+3xy+15y,}$$ $${\displaystyle 4x^{2}+20x+3xy+15y=(4x^{2}+20x)+(3xy+15y)=4x(x+5)+3y(x+5).}$$ $${\displaystyle 4x^{2}+20x+3xy+15y=(4x+3y)(x+5).}$$

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

Сложение и вычитание членов

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

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

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

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

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

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

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

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

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

Корни 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)i\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 — действительные выражения, и нужны действительные множители, то нужно заменить каждую пару комплексно-сопряженных множителей их произведением. Так как комплексно-сопряженное число равно и имеет следующие действительные факторизации (переход от одного к другому осуществляется путем замены k на n – k или n + 1 – k и применения обычных тригонометрических формул ): ${\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},}$$ $${\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),}$$

Часто требуется факторизация с рациональными коэффициентами. Такая факторизация включает в себя циклотомические многочлены . Чтобы выразить рациональные факторизации сумм и разностей или степеней, нам нужна нотация для гомогенизации многочлена : если его гомогенизация является двумерным многочленом Тогда, имеем где произведения берутся по всем делителям n или всем делителям 2 n , которые не делят n , и является n-м циклотомическим многочленом. ${\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),}$$ ${\displaystyle Q_{n}(x)}$

Например, поскольку делителями числа 6 являются 1, 2, 3, 6, а делителями числа 12, которые не делят 6, являются 4 и 12. $${\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}),}$$

Полиномы

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

${\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 ( x ) — частное от евклидова деления P ( x ) = 0 на линейный (первой степени) множитель x – r .

Если коэффициенты 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.}$

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

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

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

${\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 является корнем. Так как r + 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; то есть и q должно делить 2, то есть Более того, если x < 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}$

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

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

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

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

то есть

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

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

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

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

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

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

Рассмотрение множителей ac = 36 приводит к 4 + 9 = 13 = b , что дает два корня

${\displaystyle r_{1}=-{\frac {4}{6}}=-{\frac {2}{3}}\quad {\text{and}}\quad r_{2}=-{\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 }$

Если a, b, c все действительны , то множители действительны тогда и только тогда, когда дискриминант неотрицателен. В противном случае квадратный многочлен не может быть разложен на непостоянные действительные множители. ${\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, но не каждая целочисленная область, в которой существуют наибольшие общие делители (известная как область GCD ), является UFD. Каждая главная идеальная область является UFD.

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

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

Идеалы

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

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

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

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

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

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

Матрицы

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

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

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

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

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

Примечания

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

Ссылки

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

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

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