Часть II · Алгебра Глава 14 из 60
Многочлены
В 1535 году в Венеции два математика обменялись тридцатью задачами, и все задачи одного из них были кубическими уравнениями. Проследим историю этого поединка до конца, а по дороге соберём оружие, которым с тех пор решают уравнения высоких степеней.
Опирается на: 13 · Последовательности и индукция
Вы научитесь
- делить многочлены уголком и по схеме Горнера, находить остаток по теореме Безу
- искать рациональные корни и раскладывать многочлен на множители
- восстанавливать многочлен по точкам и понимать, как на этом устроено разделение секрета
- решать кубические уравнения формулой Кардано и видеть, где она упирается в корень из отрицательного числа
3Почему для уравнения пятой степени нет формулы корней?
Прошлая глава закончилась уравнением $x^3 - 6x^2 + 11x - 6 = 0$. Формулы для него у нас нет, но подбор напрашивается сам. При $x = 1$ получается $1 - 6 + 11 - 6 = 0$: один корень есть. Пробуем $2$: $8 - 24 + 22 - 6 = 0$. Пробуем $3$: $27 - 54 + 33 - 6 = 0$. Три корня за три попытки. Повезло? Не совсем: выбор здесь был невелик, и к середине главы станет ясно почему. А вот если заменить свободный член $-6$ на $-5$, подбор не даст ничего, и два корня из трёх вообще пропадут.
Почти пятьсот лет назад такие уравнения решали не за партой, а на публике, и на кону стояла репутация. Должности в итальянских университетах давали на время, и их нередко приходилось отстаивать в публичных диспутах: проигрыш мог стоить учеников и жалованья. Эта глава — о самом знаменитом из таких поединков и о его последствиях, растянувшихся на полвека. Но сначала — об оружии. У математиков того времени был общий арсенал, и мы соберём его заново: деление, остатки, быстрый счёт, связь корней с коэффициентами.
Вызов
Около 1515 года профессор Болонского университета Сципион дель Ферро нашёл способ решать уравнения вида «куб и вещи равны числу», по-нашему $x^3 + px = q$ с положительными $p$ и $q$. Он не опубликовал его. Секретный приём был капиталом: с ним можно выиграть любой диспут. Незадолго до смерти, в 1526 году, дель Ферро передал способ своему ученику Антонио Марии Фиоре.
Фиоре был математиком скромных способностей, но с секретным оружием. В начале 1535 года он вызвал на поединок Никколо Тарталью из Брешии, преподававшего математику в Венеции. Условия записали у нотариуса: каждый даёт сопернику тридцать задач, на решение — сорок или пятьдесят дней, кто решит больше, получает честь и небольшую награду. Все тридцать задач Фиоре оказались одного типа — «куб и вещи равны числу». Одна из них, например, требовала найти число, которое вместе со своим кубическим корнем даёт шесть. Если обозначить кубический корень через $x$, получится $x^3 + x = 6$.
Фиоре рассчитывал, что соперник не справится ни с одной задачей. Тарталья, получив список, понял, что против него выставлен один-единственный тип уравнений, и догадывался, что у Фиоре есть на него правило. Чем он располагал сам? Посмотрим на предмет спора внимательнее.
Левая часть уравнения Фиоре, $x^3 + x - 6$, — сумма степеней неизвестного, умноженных на числа. Такие выражения не раз встречались в прошлых главах: $ax + b$, $ax^2 + bx + c$, а в главе о счёте — даже запись числа: $1331 = 1 \cdot 10^3 + 3 \cdot 10^2 + 3 \cdot 10 + 1$. Пора дать им имя.
Многочлен от $x$ — выражение вида $a_n x^n + a_{n-1}x^{n-1} + \dots + a_1 x + a_0$, где $a_0, a_1, \dots, a_n$ — числа, их называют коэффициентами. Если $a_n \ne 0$, число $n$ называют степенью многочлена, $a_n$ — старшим коэффициентом, $a_0$ — свободным членом.
Число $5$ тоже многочлен, нулевой степени. У числа $0$ степени нет вовсе: ни одного ненулевого коэффициента у него не найти. Многочлены складывают, вычитают и перемножают по правилам раскрытия скобок из главы 7, и результат снова многочлен. Степень произведения ненулевых многочленов равна сумме степеней: старшие члены $a_n x^n$ и $b_m x^m$ дают $a_n b_m x^{n+m}$, и никакое другое слагаемое такой степени не достигает.
Сходство с числами глубже, чем кажется. Запись $1331$ — значение многочлена $x^3 + 3x^2 + 3x + 1$ при $x = 10$. А этот многочлен равен $(x + 1)^3$, поэтому $1331 = 11^3$. Числа в позиционной записи — многочлены, в которые подставили основание. И как числа, многочлены можно делить с остатком.
Корень многочлена $P(x)$ — число $a$, при котором $P(a) = 0$. Корни многочлена — это корни уравнения $P(x) = 0$.
Деление уголком
Помните деление с остатком из главы 4: $1000 = 7 \cdot 142 + 6$, и остаток меньше делителя. У многочленов то же самое, только «меньше» означает «меньшей степени».
Находят частное так же, как при делении чисел столбиком. Смотрим на старший член делимого и спрашиваем: на что умножить старший член делителя, чтобы его получить? Для $x^3 - 6x^2 + 11x - 6$ и $x - 1$ ответ — $x^2$. Умножаем на $x^2$ весь делитель, вычитаем и повторяем то же с тем, что осталось. Каждый шаг уничтожает старший член, степень остатка падает, и рано или поздно она станет меньше степени делителя.
Для любого многочлена $P$ и ненулевого многочлена $S$ существуют, и притом единственные, многочлены $Q$ и $R$, такие что $P = S \cdot Q + R$, где $R$ — нулевой многочлен или многочлен меньшей степени, чем $S$.
Существование доказывает сам алгоритм деления уголком. Если степень $P$ меньше степени $S$ (или $P$ нулевой), берём $Q = 0$ и $R = P$. Иначе пусть $P$ имеет степень $n$ и старший коэффициент $a$, а $S$ — степень $m \le n$ и старший коэффициент $s$. Одночлен $\frac{a}{s}x^{n-m}$, умноженный на $S$, даёт многочлен с тем же старшим членом $ax^n$, что у $P$, поэтому разность $P_1 = P - \frac{a}{s}x^{n-m}S$ либо нулевая, либо имеет степень меньше $n$. С $P_1$ поступаем так же. Степени остатков строго убывают, а бесконечно убывать целые неотрицательные числа не могут, поэтому через конечное число шагов остаток станет нулём или многочленом степени меньше $m$. Сумма всех выписанных одночленов и есть частное $Q$.
Единственность. Пусть $P = SQ_1 + R_1 = SQ_2 + R_2$, где оба остатка нулевые или степени меньше $m$. Вычтем одно из другого: $S(Q_1 - Q_2) = R_2 - R_1$. Если $Q_1 \ne Q_2$, то слева произведение ненулевых многочленов, и его степень не меньше $m$, потому что степени при умножении складываются. Справа же многочлен степени меньше $m$ или ноль. Противоречие; значит, $Q_1 = Q_2$, а тогда и $R_1 = R_2$.
Первый пример закончился нулём: $x^3 - 6x^2 + 11x - 6 = (x - 1)(x^2 - 5x + 6)$. Трёхчлен в скобках раскладывается по Виету, $x^2 - 5x + 6 = (x - 2)(x - 3)$, и уравнение из начала главы решено до конца. Но за этим стоит закономерность: деление на $x - 1$ прошло нацело именно потому, что $1$ — корень. А если бы остаток не был нулём, каким бы он оказался?
Остаток без деления
Остаток от деления на $x - a$ можно узнать, вообще не деля.
Остаток от деления многочлена $P(x)$ на $x - a$ равен $P(a)$. В частности, $P(x)$ делится на $x - a$ без остатка тогда и только тогда, когда $a$ — корень $P(x)$.
Идея: записать деление с остатком и подставить в него $x = a$. Делитель $x - a$ имеет первую степень, поэтому по теореме о делении с остатком остаток — нулевой многочлен или многочлен нулевой степени, то есть в любом случае число $r$:
$$P(x) = (x - a)\,Q(x) + r.$$Это равенство многочленов, оно верно при любом $x$, в том числе при $x = a$. Тогда первое слагаемое равно $(a - a)\,Q(a) = 0$, и остаётся $P(a) = r$. Вторая часть: если $P(a) = 0$, то $r = 0$ и $P(x) = (x - a)\,Q(x)$; обратно, если $P(x) = (x - a)\,Q(x)$, то $P(a) = 0 \cdot Q(a) = 0$.
В русской традиции это утверждение носит имя Этьена Безу, того самого, чьё имя в главе 4 получило соотношение для НОД. В других странах его чаще называют просто теоремой об остатке.
Найдите остаток от деления $x^{2026} + 3x + 5$ на $x + 1$.
По теореме Безу остаток равен значению многочлена при $x = -1$: $(-1)^{2026} + 3 \cdot (-1) + 5 = 1 - 3 + 5 = 3$. Делить многочлен две тысячи двадцать шестой степени не пришлось.
У теоремы есть следствие, на котором держится вся глава.
У ненулевого многочлена степени $n$ не больше $n$ различных корней.
Идея: каждый корень отщепляет от многочлена множитель первой степени и забирает единицу степени, а степень конечна. Проведём индукцию по $n$, как в главе о последовательностях. База: многочлен степени $0$ — ненулевое число, корней у него нет.
Шаг. Пусть утверждение верно для степени $n - 1$, и пусть у многочлена $P$ степени $n$ есть корень $a_1$ (если корней нет, доказывать нечего). По теореме Безу $P(x) = (x - a_1)\,Q(x)$, и степень $Q$ равна $n - 1$, потому что при умножении степени складываются. Возьмём любой другой корень $b \ne a_1$. Тогда $0 = P(b) = (b - a_1)\,Q(b)$, и раз $b - a_1 \ne 0$, то $Q(b) = 0$: любой корень $P$, кроме $a_1$, — корень $Q$. По предположению индукции у $Q$ не больше $n - 1$ различных корней, значит, у $P$ их не больше $(n - 1) + 1 = n$.
Корень может отщепляться и несколько раз подряд. У $x^3 - 3x + 2 = (x - 1)^2(x + 2)$ корней два, но $1$ — корень двойной: график в этой точке касается оси, а не пересекает её.
Число $a$ — корень кратности $k$ многочлена $P(x)$, если $P(x)$ делится на $(x - a)^k$, но не делится на $(x - a)^{k+1}$. Корни кратности $1$ называют простыми, остальные — кратными.
Если считать корни с кратностью, их всё равно не больше $n$. Бывает и меньше: у $x^2 + 1$ действительных корней нет совсем. Можно ли расширить запас чисел так, чтобы корней всегда было ровно $n$? Об этом следующая глава.
Схема Горнера
Чтобы проверить кандидата в корни, надо вычислить $P(a)$. Если возводить $a$ в каждую степень заново, на многочлен степени $n$ уйдёт около $\frac{n^2}{2}$ умножений, если запоминать степени — около $2n$. А можно обойтись $n$ умножениями: вынести $x$ за скобки столько раз, сколько получится.
$$x^3 - 6x^2 + 11x - 6 = \bigl((x - 6)\,x + 11\bigr)\,x - 6.$$Считаем изнутри наружу: взяли старший коэффициент, умножили на $x$, прибавили следующий коэффициент, снова умножили, снова прибавили. Для $x = 2$: $1$, затем $1 \cdot 2 - 6 = -4$, затем $-4 \cdot 2 + 11 = 3$, затем $3 \cdot 2 - 6 = 0$. Ровно так в главе о счёте мы переводили числа в десятичную систему «слева направо». Приём тот же, только основанием там было число, а здесь — неизвестное.
Пусть $P(x) = a_n x^n + \dots + a_1 x + a_0$, а числа $b_0, \dots, b_n$ построены по правилу $b_0 = a_n$, $b_k = a_{n-k} + a\,b_{k-1}$. Тогда $P(x) = (x - a)\left(b_0 x^{n-1} + b_1 x^{n-2} + \dots + b_{n-1}\right) + b_n$, и в частности $P(a) = b_n$.
Раскроем скобки справа. Одночлен $b_k x^{n-1-k}$, умноженный на $x$, даёт $b_k x^{n-k}$, а умноженный на $-a$ — слагаемое $-a\,b_k x^{n-1-k}$, которое встречается с $b_{k+1}x^{n-1-k}$ от следующего одночлена. Поэтому
$$(x - a)\left(b_0 x^{n-1} + \dots + b_{n-1}\right) + b_n = b_0 x^n + (b_1 - a\,b_0)\,x^{n-1} + \dots + (b_{n-1} - a\,b_{n-2})\,x + (b_n - a\,b_{n-1}).$$Правило построения говорит ровно, что $b_0 = a_n$ и $b_k - a\,b_{k-1} = a_{n-k}$ при $k = 1, \dots, n$. Значит, коэффициенты справа совпадают с коэффициентами $P$, и равенство верно. Подставив $x = a$, получаем $P(a) = b_n$ — ту же теорему Безу, проверенную ещё раз.
Схема даёт сразу два ответа. Последнее число — значение $P(a)$, оно же остаток по теореме Безу. Все предыдущие — коэффициенты частного от деления на $x - a$: то же, что давало деление уголком, но без единой буквы и без вычитаний столбиком.
Схема Горнера — запись вычисления $P(a)$ в виде таблицы: сверху коэффициенты многочлена, снизу числа $b_k$. Последнее из них — остаток $P(a)$, остальные — коэффициенты частного от деления $P(x)$ на $x - a$.
Кого проверять
Горнер быстро отвечает на вопрос «корень ли $a$?», но какие $a$ пробовать? Для многочленов с целыми коэффициентами список кандидатов конечен.
Пусть у многочлена $a_n x^n + \dots + a_1 x + a_0$ все коэффициенты целые, $a_0 \ne 0$, и несократимая дробь $\frac pq$ — его корень. Тогда $p$ делит свободный член $a_0$, а $q$ делит старший коэффициент $a_n$.
Идея: подставить дробь, избавиться от знаменателей и посмотреть, что на что делится. Подставим $x = \frac pq$ в равенство $P(x) = 0$ и умножим обе части на $q^n$:
$$a_n p^n + a_{n-1}p^{n-1}q + \dots + a_1 p\,q^{n-1} + a_0 q^n = 0.$$Перенесём последнее слагаемое вправо и вынесем $p$ из остальных: $a_0 q^n = -\left(a_n p^{n-1} + a_{n-1}p^{n-2}q + \dots + a_1 q^{n-1}\right)p$. Правая часть делится на $p$, значит, и $a_0 q^n$ делится на $p$. Дробь $\frac pq$ несократима, то есть у $p$ и $q$ нет общих простых делителей, а по основной теореме арифметики простые делители $q^n$ — те же, что у $q$. Выходит, все простые множители $p$ вместе с кратностями входят в разложение $a_0$, то есть $p$ делит $a_0$. (То же можно получить, применив лемму Евклида к каждому простому множителю $p$.)
Точно так же перенесём вправо первое слагаемое и вынесем $q$ из остальных: $a_n p^n = -\left(a_{n-1}p^{n-1} + \dots + a_1 p\,q^{n-2} + a_0 q^{n-1}\right)q$. Значит, $q$ делит $a_n p^n$, а так как с $p^n$ у $q$ общих простых делителей нет, $q$ делит $a_n$.
Для многочлена со старшим коэффициентом $1$ кандидатами остаются только целые делители свободного члена. У $x^3 - 6x^2 + 11x - 6$ это $\pm1, \pm2, \pm3, \pm6$ — восемь чисел, из которых три оказались корнями. Вот почему подбор в начале главы сработал так быстро. А у $x^3 - 6x^2 + 11x - 5$ кандидатов всего четыре, $\pm1$ и $\pm5$, и ни один не подходит.
Решите уравнение $x^3 - 7x + 6 = 0$.
Кандидаты — делители числа $6$: $\pm1, \pm2, \pm3, \pm6$. Уже $x = 1$ подходит: $1 - 7 + 6 = 0$. Схема Горнера для $a = 1$ (коэффициенты $1, 0, -7, 6$) даёт нижнюю строку $1,\ 1,\ -6,\ 0$, то есть $x^3 - 7x + 6 = (x - 1)(x^2 + x - 6)$. Трёхчлен раскладывается по Виету: $x^2 + x - 6 = (x - 2)(x + 3)$. Корни: $1$, $2$ и $-3$. Обратите внимание на нулевой коэффициент при $x^2$: пропустить его в таблице — самая частая ошибка.
Набить руку поможет тренажёр. На первом уровне остаток ищут по теореме Безу, на втором делят многочлены, на третьем решают уравнения третьей и четвёртой степени.
Свой многочлен можно разложить в решателе, а все тренажёры курса собраны на странице практики.
Корни и коэффициенты
В главе о квадратных уравнениях мы видели, как корни квадратного трёхчлена связаны с коэффициентами: сумма корней приведённого уравнения $x^2 + px + q = 0$ равна $-p$, произведение равно $q$. Там же было обещание вернуться к этим формулам для любой степени. Выполняем. Если у многочлена $x^3 + ax^2 + bx + c$ три корня $x_1, x_2, x_3$, то по теореме Безу он раскладывается на множители:
$$x^3 + ax^2 + bx + c = (x - x_1)(x - x_2)(x - x_3).$$Раскроем скобки справа и сравним коэффициенты при одинаковых степенях. Сравнивать так законно, и это стоит доказать отдельно.
Если два многочлена принимают равные значения при всех $x$ (или хотя бы в бесконечном множестве точек), то их коэффициенты при одинаковых степенях совпадают.
Вычтем один многочлен из другого. Разность — тоже многочлен, и каждая точка, где исходные многочлены равны, — его корень. Корней бесконечно много, а у ненулевого многочлена их не больше, чем его степень, по следствию теоремы Безу. Значит, разность — нулевой многочлен: все её коэффициенты равны нулю, а это и есть равенство коэффициентов.
Если $x^3 + ax^2 + bx + c = (x - x_1)(x - x_2)(x - x_3)$, то $x_1 + x_2 + x_3 = -a$, $\ x_1x_2 + x_1x_3 + x_2x_3 = b$ и $x_1x_2x_3 = -c$.
Перемножим скобки по очереди. Сначала $(x - x_1)(x - x_2) = x^2 - (x_1 + x_2)x + x_1x_2$. Умножим на $x - x_3$:
$$\bigl(x^2 - (x_1 + x_2)x + x_1x_2\bigr)(x - x_3) = x^3 - (x_1 + x_2 + x_3)x^2 + (x_1x_2 + x_1x_3 + x_2x_3)x - x_1x_2x_3.$$Слагаемые с $x^2$ пришли из $-(x_1 + x_2)x \cdot x$ и $x^2 \cdot (-x_3)$, слагаемые с $x$ — из $x_1x_2 \cdot x$ и $-(x_1 + x_2)x \cdot (-x_3)$, свободный член — из $x_1x_2 \cdot (-x_3)$. По лемме о равенстве многочленов коэффициенты слева и справа совпадают: $a = -(x_1 + x_2 + x_3)$, $b = x_1x_2 + x_1x_3 + x_2x_3$, $c = -x_1x_2x_3$.
Для многочлена степени $n$ всё устроено так же: у приведённого многочлена коэффициент при $x^{n-k}$ равен сумме всех произведений корней по $k$ штук, взятой со знаком $(-1)^k$. Корни здесь считаются с кратностью. Сам Виет рассматривал только положительные корни, а в общем виде эти соотношения выписал Альбер Жирар в 1629 году.
Во втором режиме видно то, от чего не отмахнуться. Сдвигаем график совсем немного, и два корня сближаются, сливаются в один и пропадают. У многочлена степени $3$ может быть три, два или один различный корень, но никогда ни одного: при больших положительных $x$ он одного знака со старшим коэффициентом, при больших отрицательных — противоположного, и где-то между ними график обязан пересечь ось. Строго это следует из теоремы о промежуточном значении непрерывной функции (глава 25). А вот куда исчезает пара корней — вопрос, на который среди действительных чисел ответа нет.
Сколько различных действительных корней может быть у уравнения третьей степени?
Ни одного быть не может: многочлен нечётной степени принимает значения разных знаков при больших по модулю положительных и отрицательных $x$, и график пересекает ось. Два различных корня бывает, когда один из них двойной: $x^3 - 3x + 2 = (x - 1)^2(x + 2)$.
Не решая уравнение $2x^3 - 3x^2 - 11x + 6 = 0$, найдите сумму его корней.
Разделим на старший коэффициент: $x^3 - \frac32 x^2 - \frac{11}{2}x + 3 = 0$. Сумма корней равна коэффициенту при $x^2$ с обратным знаком, то есть $\frac32$. Проверка: корни этого уравнения $3$, $-2$ и $\frac12$ (их найдёт схема Горнера во втором примере выше), и $3 - 2 + \frac12 = \frac32$.
Многочлен по точкам
Теорема Безу умеет и неожиданное: восстанавливать многочлен по его значениям. Пусть известно, что многочлен степени не выше второй принимает в точках $0$, $1$, $2$ значения $1$, $3$, $7$. Какой он?
Во вступлении такой вопрос уже возникал: в задаче «продолжите последовательность» через пять или шесть точек проводили многочлен, и мы обещали объяснить, почему он единственный. Выполняем обещание.
Через $n + 1$ точку $(x_0;\,y_0), \dots, (x_n;\,y_n)$ с различными $x_i$ проходит ровно один многочлен степени не выше $n$.
Идея: собрать многочлен из деталей, каждая из которых отвечает за одну точку, а единственность получить из теоремы о числе корней.
Существование. Для каждого $i$ рассмотрим произведение $\ell_i(x) = \prod_{j \ne i} \frac{x - x_j}{x_i - x_j}$ по всем $j$, кроме $i$. Знаменатели не равны нулю, потому что все $x_j$ различны. В числителе $n$ множителей первой степени, поэтому $\ell_i$ — многочлен степени $n$. Если подставить $x = x_i$, каждая дробь станет $\frac{x_i - x_j}{x_i - x_j} = 1$, и $\ell_i(x_i) = 1$. Если подставить любую другую точку $x_k$, $k \ne i$, то среди множителей есть дробь с числителем $x_k - x_k = 0$, и $\ell_i(x_k) = 0$. Положим $P(x) = y_0\ell_0(x) + y_1\ell_1(x) + \dots + y_n\ell_n(x)$. Это сумма многочленов степени $n$, так что степень $P$ не выше $n$. В точке $x_k$ все слагаемые, кроме $k$-го, обнуляются, а $k$-е равно $y_k \cdot 1$. Значит, $P(x_k) = y_k$ для каждого $k$.
Единственность. Пусть $\tilde P$ — ещё один многочлен степени не выше $n$ с теми же значениями. Разность $P - \tilde P$ имеет степень не выше $n$ и обращается в ноль во всех $n + 1$ точках $x_0, \dots, x_n$. По теореме о числе корней ненулевой многочлен такой степени не может иметь $n + 1$ корень, значит, разность нулевая и $\tilde P = P$.
Построенный в доказательстве многочлен и есть ответ. Записанный одной строкой, он называется формулой Лагранжа.
Многочлен из теоремы об интерполяции называют интерполяционным многочленом, а его построение — интерполяцией.
Формулу называют именем Жозефа Луи Лагранжа, изложившего её в лекциях 1795 года, хотя Эдвард Уоринг опубликовал её ещё в 1779-м. Оговорка «не выше $n$» важна: если три точки лежат на одной прямой, единственный многочлен степени не выше второй через них — сама прямая.
Какой многочлен степени не выше второй проходит через точки $(1;\,2)$, $(2;\,4)$, $(3;\,6)$?
Прямая $y = 2x$ — многочлен первой степени, то есть «не выше второй», и она проходит через все три точки. По теореме об интерполяции другого нет: формула Лагранжа тоже даст $2x$, коэффициент при $x^2$ сократится до нуля.
Найдите многочлен $P(x)$ степени не выше второй, для которого $P(0) = 3$, $P(1) = 2$, $P(3) = 6$.
Ищем $P(x) = ax^2 + bx + c$. Из $P(0) = 3$ сразу $c = 3$. Дальше $a + b + 3 = 2$ и $9a + 3b + 3 = 6$, то есть $a + b = -1$ и $3a + b = 1$. Вычитаем: $2a = 2$, $a = 1$, $b = -2$. Ответ: $x^2 - 2x + 3$. Формула Лагранжа даст то же самое — по теореме единственности иначе и быть не может.
Как хранить секрет
Вернёмся к дуэлянтам. Секрет дель Ферро жил в его голове и в тетради, доставшейся зятю, секрет Тартальи — только в голове. Надёжно, пока хозяин молчит. А если секрет нужно доверить нескольким людям, да так, чтобы открыть его могли только несколько из них вместе, а поодиночке никто не узнал ничего?
Такую задачу решил в 1979 году израильский математик Ади Шамир, тот самый «S» из шифра RSA (о нём — в главе об арифметике остатков). Решение умещается в одну фразу: спрятать секрет в свободный член многочлена.
Пусть секрет — число $S$, например PIN-код $4721$, и открыть его должны любые трое из пяти хранителей. Возьмём многочлен второй степени со свободным членом $S$ и случайными остальными коэффициентами, скажем $f(x) = 4721 + 1234x + 567x^2$. Первый хранитель получает точку $(1;\,f(1))$, второй — $(2;\,f(2))$, и так до пятого. Любые трое знают три точки параболы, по теореме об интерполяции восстанавливают её целиком и вычисляют $f(0) = S$. Для хранителей с номерами $1$, $2$, $3$ формула Лагранжа в нуле превращается в совсем простую: $S = 3f(1) - 3f(2) + f(3)$. Проверим: $f(1) = 6522$, $f(2) = 9457$, $f(3) = 13\,526$, и $3 \cdot 6522 - 3 \cdot 9457 + 13\,526 = 4721$.
А двое? Через две точки проходит парабола с любым значением в нуле. Какой бы PIN ни загадать, найдётся парабола, которая проходит через обе известные точки и через этот PIN. Двое хранителей не отличат настоящий секрет от любого другого.
Разделение секрета по схеме Шамира: секрет — свободный член случайного многочлена степени $k - 1$, каждый из $n$ участников получает его значение в своей точке. Любые $k$ участников восстанавливают многочлен, а с ним и секрет; меньшее число — не может.
Секрет Тартальи
Вернёмся в февраль 1535 года и проверим уравнение Фиоре нашим арсеналом. Кандидатов в рациональные корни у $x^3 + x - 6$ восемь: $\pm1, \pm2, \pm3, \pm6$. Ни один не подходит. При этом $P(1) = -4$, а $P(2) = 4$, так что корень лежит где-то между единицей и двойкой. Это примерно $1{,}6344$, число иррациональное. Весь арсенал из первой половины главы на таком уравнении бессилен. Нужна формула.
По словам самого Тартальи, общее правило он нашёл за восемь дней до срока, а потом решил все тридцать задач Фиоре меньше чем за два часа. Фиоре с разнообразными задачами Тартальи почти не справился. От награды победитель, по рассказам, отказался: ему хватило чести.
Как именно Тарталья пришёл к правилу, неизвестно. Кардано позже обосновал его геометрически, разрезая куб на части. Мы проделаем то же алгебраически. Ищем корень уравнения $x^3 + px + q = 0$ в виде суммы двух чисел, $x = u + v$, и вспоминаем куб суммы из главы 7:
$$(u + v)^3 = u^3 + v^3 + 3uv(u + v), \qquad\text{то есть}\qquad x^3 - 3uv\,x - (u^3 + v^3) = 0.$$Это уравнение совпадёт с нашим, если $3uv = -p$ и $u^3 + v^3 = -q$. Возведём первое условие в куб: $u^3 v^3 = -\frac{p^3}{27}$. Теперь известны сумма и произведение чисел $u^3$ и $v^3$, а такие числа, как мы знаем по Виету, — корни квадратного уравнения $t^2 + qt - \frac{p^3}{27} = 0$. Кубическое уравнение свелось к квадратному.
Вывод подсказал, как искать корень. Проверим, что найденное действительно корень, а заодно выясним, сколько корней у уравнения.
Пусть $\Delta = \frac{q^2}{4} + \frac{p^3}{27} \ge 0$, $A = -\frac q2 + \sqrt\Delta$, $B = -\frac q2 - \sqrt\Delta$, а $u = \sqrt[3]{A}$ и $v = \sqrt[3]{B}$ — действительные кубические корни. Тогда $x_0 = u + v$ — корень уравнения $x^3 + px + q = 0$. При $\Delta > 0$ других действительных корней у уравнения нет.
Идея: проверить подстановкой, опираясь на то, что сумма и произведение чисел $A$ и $B$ нам известны. Сложим и перемножим их: $A + B = -q$, а по формуле разности квадратов $AB = \frac{q^2}{4} - \Delta = -\frac{p^3}{27}$. Значит, $(uv)^3 = AB = \left(-\frac p3\right)^3$. Действительный кубический корень у каждого числа один, поэтому $uv = -\frac p3$.
Теперь возведём $x_0 = u + v$ в куб по формуле куба суммы: $x_0^3 = u^3 + v^3 + 3uv(u + v) = (A + B) + 3 \cdot \left(-\frac p3\right) x_0 = -q - p\,x_0$. Перенесём всё влево: $x_0^3 + p\,x_0 + q = 0$, то есть $x_0$ — корень.
Остальные корни. По теореме Безу разделим $x^3 + px + q$ на $x - x_0$ по схеме Горнера: коэффициенты $1, 0, p, q$ дают нижнюю строку $1,\ x_0,\ x_0^2 + p,\ 0$, то есть $x^3 + px + q = (x - x_0)\left(x^2 + x_0 x + x_0^2 + p\right)$. Дискриминант квадратного трёхчлена в скобках равен $x_0^2 - 4\left(x_0^2 + p\right) = -3x_0^2 - 4p$. Подставим $x_0 = u + v$ и $p = -3uv$: получится $-3(u + v)^2 + 12uv = -3(u - v)^2$. При $\Delta > 0$ числа $A$ и $B$ различны, значит, различны и их кубические корни $u$ и $v$, дискриминант отрицателен, и у трёхчлена действительных корней нет. (При $\Delta = 0$ получаем $u = v$, и трёхчлен даёт двойной корень $-u$.)
Формула написана для уравнения без слагаемого с $x^2$, но это не ограничение. Подстановка $x = t - \frac{b}{3a}$ убирает квадрат из любого кубического уравнения $ax^3 + bx^2 + cx + d = 0$, так же как выделение полного квадрата убирает слагаемое с $x$ из квадратного. Уравнение из начала главы после подстановки $x = t + 2$ превращается в $t^3 - t = 0$, откуда $t = 0$ или $t = \pm1$, то есть $x = 2, 1, 3$.
В задачах Фиоре $p$ и $q$ были положительны, а при $p > 0$ выражение $\Delta$ положительно всегда: формула проходит без помех, и корень единственный. Для $x^3 + x = 6$ она даёт тот самый корень между единицей и двойкой:
$$x = \sqrt[3]{3 + \sqrt{\tfrac{244}{27}}} + \sqrt[3]{3 - \sqrt{\tfrac{244}{27}}} \approx 1{,}8177 - 0{,}1834 \approx 1{,}6344.$$Клятва и картели
Слух о победе Тартальи дошёл до Милана, где жил Джероламо Кардано — врач, астролог, изобретатель, игрок и автор книг обо всём на свете. Он как раз писал книгу по арифметике и алгебре и хотел включить в неё решение кубических уравнений. Тарталья долго отказывал. В марте 1539 года он всё же приехал в Милан, и 25 марта в доме Кардано открыл ему правило — в стихах, которые легче запомнить и труднее понять постороннему:
Когда куб вместе с вещами
равен какому-нибудь числу,
найди два других числа, разность которых — это число.
Потом держи за правило,
что их произведение всегда равно
кубу трети вещей.
И разность их кубических корней
будет твоей главной вещью.
В наших буквах: для $x^3 + px = q$ надо найти числа $U$ и $V$ с разностью $U - V = q$ и произведением $UV = \left(\frac p3\right)^3$; тогда $x = \sqrt[3]{U} - \sqrt[3]{V}$. Это та же формула: $U = u^3$, $V = -v^3$.
По словам Тартальи, Кардано поклялся никогда не публиковать правило. Лодовико Феррари, бывший слуга Кардано, ставший его учеником и присутствовавший при встрече, позже утверждал, что никакой клятвы не было. Так или иначе, правило оказалось у Кардано и Феррари, и они быстро пошли дальше. Кардано научился сводить к нему любые кубические уравнения, а Феррари около 1540 года нашёл способ решать уравнения четвёртой степени, сводя их к кубическим.
Опубликовать всё это мешало обещание. В 1543 году Кардано и Феррари съездили в Болонью, и Аннибале делла Наве, зять дель Ферро, показал им тетрадь покойного профессора. Правило там было, записанное задолго до 1535 года. Кардано рассудил, что раз первым был не Тарталья, то и клятва его больше не связывает. В 1545 году в Нюрнберге вышло «Великое искусство» Кардано с решениями уравнений третьей и четвёртой степени. Дель Ферро и Тарталью Кардано в книге назвал, а Феррари — как автора решения для четвёртой степени. Но правило с тех пор носит имя Кардано.
Тарталья пришёл в ярость и в книге 1546 года изложил свою версию событий, не стесняясь в выражениях. Ответил ему не Кардано, а Феррари. С февраля 1547 года по июль 1548-го они обменялись двенадцатью печатными «картелями» — открытыми письмами-вызовами с задачами, по шесть с каждой стороны. 10 августа 1548 года в Милане, в церкви францисканского монастыря, при огромном стечении народа прошёл публичный диспут. Двадцатишестилетний Феррари разбирался в кубических уравнениях и уравнениях четвёртой степени лучше соперника и держался уверенно. Тарталья уехал после первого же дня. Вскоре в Брешии, где он получил было место преподавателя, ему отказались платить жалованье.
Формулы в радикалах, то есть через сложение, вычитание, умножение, деление и извлечение корней, существуют для уравнений второй, третьей и четвёртой степени: квадратные решали ещё в Вавилоне, кубические — дель Ферро и Тарталья, уравнения четвёртой степени — Феррари. Для пятой степени формулу искали почти три века, пока Паоло Руффини (1799, с пробелом в доказательстве) и Нильс Хенрик Абель (1824) не доказали, что общей формулы нет. Почему её нет и какие уравнения пятой степени всё же решаются в радикалах, объясняет теория Галуа.
Корень из минус ста двадцати одного
Формула Кардано таила сюрприз, и Кардано его заметил. Возьмём уравнение $x^3 = 15x + 4$. У него есть очевидный корень $x = 4$: $64 = 60 + 4$. Разделим $x^3 - 15x - 4$ на $x - 4$ по Горнеру и получим трёхчлен $x^2 + 4x + 1$ с корнями $-2 \pm \sqrt3$. Все три корня действительные. А формула? Здесь $p = -15$, $q = -4$, и
$$\Delta = \frac{q^2}{4} + \frac{p^3}{27} = 4 - 125 = -121, \qquad x = \sqrt[3]{2 + \sqrt{-121}} + \sqrt[3]{2 - \sqrt{-121}}.$$Корень из отрицательного числа. В главе о квадратных уравнениях такой корень, $\sqrt{-15}$, появлялся в задаче без решения, и Кардано отмахнулся от него как от «тонкого, но бесполезного». Здесь отмахнуться нельзя: решения есть, целых три. Формула упирается в невозможное число как раз тогда, когда корней больше всего.
Неприводимый случай (по-латыни casus irreducibilis) — кубическое уравнение с тремя различными действительными корнями. Для $x^3 + px + q = 0$ он наступает ровно при $\Delta < 0$. В одну сторону мы это доказали: при $\Delta \ge 0$ три различных действительных корня не получается. В другую сторону это видно на графике в виджете выше, а строго доказывается с помощью производной (глава 26).
Кардано назвал такие уравнения неприводимыми и отложил. Позже выяснилось, что обойти беду нельзя.
Если у кубического уравнения с рациональными коэффициентами три действительных корня и ни одного рационального, то эти корни нельзя выразить через рациональные числа сложением, вычитанием, умножением, делением и извлечением корней, оставаясь в действительных числах.
Доказательство этой теоремы XIX века требует теории Галуа, и целиком оно ждёт нас в главе 43. Идея такова. Будем добавлять к рациональным числам действительные радикалы по одному. В какой-то момент наше уравнение впервые получит корень. Теория Галуа показывает, что тогда вместе с ним появятся сразу все три корня, а с ними — и недействительные кубические корни из единицы, о которых пойдёт речь в следующей главе. Но все добавленные числа действительные, а недействительное среди них оказаться не может.
Первым, кто не отступил, был Рафаэль Бомбелли, инженер, осушавший болота в долине Кьяна. В «Алгебре» 1572 года он предложил считать с $\sqrt{-1}$ как с обычным числом, условившись, что его квадрат равен $-1$, и честно довёл вычисление до конца. Кубический корень из $2 + \sqrt{-121}$ он искал в виде $a + \sqrt{-b}$ и нашёл: это $2 + \sqrt{-1}$. Проверьте сами, раскрыв куб суммы и заменив $\left(\sqrt{-1}\right)^2$ на $-1$:
$$\left(2 + \sqrt{-1}\right)^3 = 8 + 12\sqrt{-1} + 6\left(\sqrt{-1}\right)^2 + \left(\sqrt{-1}\right)^3 = 8 + 12\sqrt{-1} - 6 - \sqrt{-1} = 2 + 11\sqrt{-1}.$$А $11\sqrt{-1}$ — это и есть $\sqrt{-121}$, если обращаться с корнями из отрицательных чисел по обычным правилам. Точно так же $\sqrt[3]{2 - \sqrt{-121}} = 2 - \sqrt{-1}$, и сумма равна $\left(2 + \sqrt{-1}\right) + \left(2 - \sqrt{-1}\right) = 4$. Невозможные слагаемые уничтожили друг друга, и ответ вышел верным.
Куда дальше
Бомбелли получил $4$ честным вычислением, но по дороге прошёл через числа, которых не бывает: $\sqrt{-121}$ и $2 + \sqrt{-1}$. Фокусом это не назовёшь: та же дорога приводит и к двум другим корням, $-2 \pm \sqrt3$, если найти остальные кубические корни из $2 + \sqrt{-121}$. Значит, «невозможным» числам есть место, и считать с ними можно не хуже, чем с обычными. Где это место, что такое $\sqrt{-1}$ и куда уходили корни, пропавшие с оси, когда мы двигали свободный член, — в главе о комплексных числах.