Polynomial Rings: кольца многочленов

#абстрактная алгебра #cs #zero knowledge

Polynomials / многочлены вам знакомы ещё со школы (наверное). Например:

3x^2 - 5x + 7

или:

x^4 + 2x - 1

Обычно мы видим polynomials с integer, rational, real или complex coefficients:

Z[x]
Q[x]
R[x]
C[x]

Но теперь мы можем обобщить эту идею. Если R — commutative ring, то можно рассматривать polynomials, у которых coefficients берутся из R. Так появляется polynomial ring:

R[x]

Что означает R[x]

Пусть R — commutative ring. Тогда:

R[x]

означает ring of polynomials over R.

Его элементы имеют вид:

anx^n + a(n-1)x^(n-1) + ... + a1x + a0

где каждый coefficient лежит в R:

ai ∈ R

а n — nonnegative integer:

n = 0, 1, 2, ...

Например, если:

R = Z

то:

Z[x]

состоит из polynomials with integer coefficients:

3x^2 - 5x + 7
x^4 + 2
-8x
4

Если:

R = Z3

то:

Z3[x]

состоит из polynomials, coefficients которых считаются modulo 3.

Например:

2x^3 + x + 1

лежит в Z3[x].

Что такое coefficient

В polynomial:

3x^2 - 5x + 7

числа:

3
-5
7

являются coefficients / коэффициентами. Coefficient показывает, сколько копий соответствующей power of x стоит в polynomial.

В записи:

anx^n + a(n-1)x^(n-1) + ... + a1x + a0

coefficient при x^n — это:

an

coefficient при x — это:

a1

а constant term / свободный член — это:

a0

Polynomial как formal object

Важный момент: в abstract algebra polynomial — это не обязательно function. В записи:

3x^2 - 5x + 7

символ x можно воспринимать как formal variable / формальную переменную. То есть x здесь не обязан прямо сейчас быть конкретным числом или элементом ring R. Он работает как placeholder / метка, которая отделяет coefficients друг от друга.

Например, polynomial:

a2x^2 + a1x + a0

можно понимать как удобную запись sequence coefficients:

(a0, a1, a2)

То есть вместо бесконечной sequence:

a0, a1, a2, 0, 0, 0, ...

мы пишем привычно:

a2x^2 + a1x + a0

Это удобнее читать и умножать.

Polynomial и polynomial function — не одно и то же

В обычной школьной алгебре polynomial часто сразу воспринимается как function:

f(x) = x^2 + 1

и мы можем подставлять значения:

f(2) = 5

Но в ring theory важно различать:

polynomial

и:

polynomial function
  • Polynomial — это formal expression.
  • Polynomial function — это функция, которую он задаёт после подстановки значений.

Иногда разные polynomials могут задавать одну и ту же function.

Пример в Z3[x]

Рассмотрим два polynomials:

f(x) = x

и:

g(x) = x^3

Как polynomials в Z3[x], они разные:

x != x^3

У них разные powers of x. Но как functions from Z3 to Z3, они дают одинаковые значения.

В Z3 есть только три элемента:

0, 1, 2

Проверим:

0^3 = 0

1^3 = 1

2^3 = 8 ≡ 2 (mod 3)

То есть для каждого a ∈ Z3:

a^3 = a

Поэтому functions совпадают:

f(a) = g(a)

для всех a ∈ Z3.

Но polynomials всё равно разные:

x != x^3

в Z3[x].

Главная мысль:

polynomial equality сравнивает coefficients при одинаковых powers of x, а не только значения функции на элементах ring.

Когда два polynomials равны

Два polynomials равны, если у них совпадают coefficients при всех powers of x. Например:

2x^2 + x + 1

и:

2x^2 + x + 1

равны.

А x и x^3 не равны как polynomials, потому что coefficient при x и coefficient при x^3 различаются. Если один polynomial короче другого, мы можем мысленно добавить missing terms with coefficient 0.

Например:

x + 1

можно записать как:

0x^3 + 0x^2 + x + 1

Тогда сравнение coefficients становится прямым.

В Z_n[x] уменьшаются coefficients, а не powers

Ещё одна частая ловушка.

В ring:

Z_n[x]

coefficients считаются modulo n. Но exponents / степени x не уменьшаются modulo n.

Например, в:

Z3[x]

имеем:

5x = 2x

потому что coefficient:

5 ≡ 2 (mod 3)

Но:

x^5 != x^2

as polynomials. Мы не уменьшаем exponent 5 modulo 3. То есть modulo применяется к coefficients:

5x -> 2x

но не к powers:

x^5 not -> x^2

Addition в R[x]

Polynomials складываются по одинаковым powers of x.

Пусть:

f(x) = 2x^3 + x^2 + 2x + 2

и:

g(x) = 2x^2 + 2x + 1

Рассмотрим их как elements of:

Z3[x]

То есть coefficients считаются modulo 3.

Складываем:

f(x) + g(x)
=
(2x^3 + x^2 + 2x + 2) + (2x^2 + 2x + 1)

Собираем одинаковые powers:

= 2x^3 + (1 + 2)x^2 + (2 + 2)x + (2 + 1)

Теперь считаем coefficients modulo 3:

1 + 2 = 3 ≡ 0

2 + 2 = 4 ≡ 1

2 + 1 = 3 ≡ 0

Получаем:

f(x) + g(x)
=
2x^3 + 0x^2 + x + 0

То есть:

f(x) + g(x) = 2x^3 + x

Multiplication в R[x]

Multiplication polynomials работает через distributive law. То есть каждый term первого polynomial умножается на каждый term второго.

Например:

(x + 1)(x + 2)

Раскрываем:

x · x + x · 2 + 1 · x + 1 · 2

Получаем:

x^2 + 2x + x + 2

Собираем terms:

x^2 + 3x + 2

Если мы работаем в Z3[x], то:

3x = 0x

поэтому:

(x + 1)(x + 2) = x^2 + 2

в Z3[x].

Большой пример multiplication в Z3[x]

Пусть:

f(x) = 2x^3 + x^2 + 2x + 2

и:

g(x) = 2x^2 + 2x + 1

в Z3[x].

Умножаем:

f(x)g(x)
=
(2x^3 + x^2 + 2x + 2)(2x^2 + 2x + 1)

Раскрываем по частям. Сначала 2x^3:

2x^3 · 2x^2 = 4x^5 ≡ x^5

2x^3 · 2x = 4x^4 ≡ x^4

2x^3 · 1 = 2x^3

Теперь x^2:

x^2 · 2x^2 = 2x^4

x^2 · 2x = 2x^3

x^2 · 1 = x^2

Теперь 2x:

2x · 2x^2 = 4x^3 ≡ x^3

2x · 2x = 4x^2 ≡ x^2

2x · 1 = 2x

Теперь 2:

2 · 2x^2 = 4x^2 ≡ x^2

2 · 2x = 4x ≡ x

2 · 1 = 2

Собираем всё:

x^5 + x^4 + 2x^3
+ 2x^4 + 2x^3 + x^2
+ x^3 + x^2 + 2x
+ x^2 + x + 2

Теперь группируем одинаковые powers:

x^5 + (1 + 2)x^4 + (2 + 2 + 1)x^3 + (1 + 1 + 1)x^2 + (2 + 1)x + 2

Считаем coefficients modulo 3:

1 + 2 = 3 ≡ 0

2 + 2 + 1 = 5 ≡ 2

1 + 1 + 1 = 3 ≡ 0

2 + 1 = 3 ≡ 0

Получаем:

f(x)g(x) = x^5 + 2x^3 + 2

Почему R[x] является ring

Мы определили на R[x] две operations:

polynomial addition
polynomial multiplication

Эти operations работают так, чтобы R[x] снова был ring.

  • Если R — commutative ring, то R[x] тоже commutative ring.
  • Если R имеет unity 1, то R[x] тоже имеет unity.

Unity в R[x] — это constant polynomial 1. Потому что:

1 · f(x) = f(x)

для любого polynomial f(x).

Degree

Теперь введём terminology.

Пусть:

f(x) = anx^n + a(n-1)x^(n-1) + ... + a1x + a0

и:

an != 0

Тогда говорят, что polynomial f(x) имеет degree / степень n. Обозначение:

deg f(x) = n

Например:

f(x) = 5x^7 + 3x^2 - 1

имеет degree 7.

Polynomial:

g(x) = 4x^3 + x + 9

имеет degree 3.

Constant nonzero polynomial:

h(x) = 5

имеет degree 0.

Zero polynomial:

0

обычно не имеет degree.

Leading coefficient

Если:

f(x) = anx^n + a(n-1)x^(n-1) + ... + a1x + a0

и:

an != 0

то coefficient:

an

называется leading coefficient / старшим коэффициентом. Например, у polynomial:

7x^4 - 2x + 9

degree равна 4 а leading coefficient равен 7.

Monic polynomial

Polynomial называется monic / приведённым, если его leading coefficient равен multiplicative identity ring R. То есть если leading coefficient равен 1.

Например, в Z[x] polynomial:

x^3 - 5x + 2

monic, потому что leading coefficient равен 1.

А polynomial:

3x^3 - 5x + 2

не monic, потому что leading coefficient равен 3.

Constant polynomial

Polynomial вида:

f(x) = a0

называется constant polynomial / константным многочленом.

Например:

5

-2

0

являются constant polynomials.

Если a0 != 0, то degree constant polynomial равна:

0

Zero polynomial обычно рассматривают отдельно.

Когда D[x] тоже integral domain

Если D — integral domain, то polynomial ring:

D[x]

тоже является integral domain. То есть если в D нет zero divisors, то и в D[x] zero divisors не появятся.

Почему это правда

Пусть:

f(x), g(x) ∈ D[x]

и оба polynomials ненулевые. Допустим:

deg f = m

и:

deg g = n

Тогда leading terms имеют вид:

am x^m

и:

bn x^n

где:

am != 0
bn != 0

При multiplication самый старший term произведения будет:

am bn x^(m+n)

Так как D — integral domain, в нём нет zero divisors. Поэтому из:

am != 0

и:

bn != 0

следует:

am bn != 0

Значит произведение:

f(x)g(x)

не может быть zero polynomial. То есть два ненулевых polynomials не могут перемножиться в 0.

Следовательно:

D[x]

тоже integral domain.

Division algorithm for polynomials

Для integers у нас есть division algorithm.

Если:

a, b ∈ Z

и:

b != 0

то можно записать:

a = bq + r

где q — quotient / частное, а r — remainder / остаток.

Для polynomials есть похожая идея. Но важно: хорошо работает она над field.

Division algorithm в F[x]

Пусть F — field, и пусть:

f(x), g(x) ∈ F[x]

причём:

g(x) != 0

Тогда существуют unique polynomials:

q(x), r(x) ∈ F[x]

такие, что:

f(x) = g(x)q(x) + r(x)

и при этом:

r(x) = 0

или:

deg r < deg g

То есть любой polynomial f(x) можно разделить на ненулевой polynomial g(x) с остатком.

Почему нужно field

При polynomial division часто нужно делить на leading coefficient divisor polynomial. Например, если leading term divisor равен:

2x^2

а leading term dividend равен:

3x^4

то нужно поделить coefficient 3 на coefficient 2. Это возможно, если 2 имеет inverse. В field каждый nonzero element имеет inverse, поэтому division algorithm работает нормально.

Например, в:

Q[x]
R[x]
C[x]
Z_p[x]

division algorithm работает.

А в:

Z[x]

нужно быть осторожнее, потому что не каждый integer coefficient обратим. Например, 2 не имеет inverse внутри Z.

Пример: деление многочленов в Z5[x]

Рассмотрим многочлены:

f(x) = 3x^4 + x^3 + 2x^2 + 1
g(x) = x^2 + 4x + 2

Мы хотим разделить f(x) на g(x), то есть найти частное q(x) и остаток r(x):

f(x) = g(x)q(x) + r(x)

При этом степень остатка должна быть меньше степени делителя:

deg r < deg g = 2

Все вычисления выполняются modulo 5.

Шаг 1. Находим первый член частного

Смотрим на старшие члены двух многочленов:

3x^4 и x^2

Чтобы из x² получить 3x⁴, нужно умножить его на 3x²:

3x^4 / x^2 = 3x^2

Это первый член нашего частного:

q(x) = 3x^2 + ...

Теперь умножаем весь делитель на 3x²:

3x²(x² + 4x + 2)
= 3x⁴ + 12x³ + 6x²

Поскольку работаем в Z5, приводим коэффициенты modulo 5:

12 ≡ 2 (mod 5)
6 ≡ 1 (mod 5)

Получаем:

3x⁴ + 2x³ + x²

Вычитаем это из исходного многочлена:

  3x⁴ +  x³ + 2x² + 1
- 3x⁴ - 2x³ -  x²
------------------------
        -x³ +  x² + 1

Но в Z5:

-1 ≡ 4 (mod 5)

Поэтому результат вычитания:

4x³ + x² + 1

Шаг 2. Находим следующий член частного

Теперь нужно разделить старший член полученного многочлена на старший член делителя:

4x³ / x² = 4x

Значит, второй член частного — 4x:

q(x) = 3x² + 4x

Снова умножаем весь делитель, теперь на 4x:

4x(x² + 4x + 2)
= 4x³ + 16x² + 8x

Приводим коэффициенты modulo 5:

16 ≡ 1 (mod 5)
8 ≡ 3 (mod 5)

Получаем:

4x³ + x² + 3x

Вычитаем:

  4x³ + x² + 0x + 1
- 4x³ - x² - 3x
---------------------
             -3x + 1

Поскольку:

-3 ≡ 2 (mod 5)

результат:

2x + 1

Шаг 3. Проверяем остаток

Теперь у нас остался многочлен:

r(x) = 2x + 1

Его степень равна 1, а степень делителя — 2.

deg r = 1 < 2 = deg g

Значит, деление закончено: дальше продолжать нельзя, поскольку степень остатка уже меньше степени делителя.

Получили:

q(x) = 3x² + 4x
r(x) = 2x + 1

И окончательное равенство:

3x⁴ + x³ + 2x² + 1
=
(x² + 4x + 2)(3x² + 4x) + 2x + 1

Таким образом, деление многочленов в Z5[x] выполняется по тем же правилам, что и обычное деление столбиком. Единственное отличие — после операций с коэффициентами мы приводим результаты modulo 5.

Divisibility polynomials

Пусть D — integral domain, и пусть:

f(x), g(x) ∈ D[x]

Говорят, что g(x) divides f(x), если существует polynomial:

h(x) ∈ D[x]

такой, что:

f(x) = g(x)h(x)

Обозначение:

g(x) | f(x)

В этом случае g(x) называют:

factor of f(x)

То есть factor polynomial — это polynomial, который делит другой polynomial без остатка.

Пример

В Z[x]:

x - 1

divides:

x^2 - 1

потому что:

x^2 - 1 = (x - 1)(x + 1)

Значит:

x - 1 | x^2 - 1

и:

x + 1 | x^2 - 1

Zeros / roots polynomial

Элемент a называется zero / root polynomial f(x), если:

f(a) = 0

То есть мы подставляем a вместо x, и результат равен zero element ring.

Например, для:

f(x) = x^2 - 4x + 3

имеем:

f(1) = 1 - 4 + 3 = 0

и:

f(3) = 9 - 12 + 3 = 0

Значит 1 и 3 являются roots polynomial f(x).

Multiplicity of a root

Мы уже знаем, что число a является корнем многочлена f(x), если:

f(a) = 0

По теореме о корнях это означает, что f(x) делится на:

x - a

без остатка.

Но иногда многочлен можно разделить на x - a не один раз, а несколько. Количество таких делений и называется кратностью корня (multiplicity).

Простой пример

Рассмотрим многочлен над R:

f(x) = (x - 2)(x - 2)

Или:

f(x) = (x - 2)^2

Число 2 — его корень, потому что:

f(2) = (2 - 2)^2 = 0

Но здесь есть дополнительное свойство: многочлен можно дважды разделить на x - 2 без остатка.

Первое деление:

(x - 2)^2 / (x - 2) = x - 2

Второе деление:

(x - 2) / (x - 2) = 1

Третье деление уже невозможно без остатка, поскольку 1 не делится на x - 2.

Поэтому говорят, что 2 — корень кратности 2, или двойной корень.

Пример с несколькими корнями

Теперь рассмотрим:

f(x) = (x - 2)^3(x + 1)

У этого многочлена два различных корня:

2 и -1

Почему? При x = 2 первый множитель становится нулём:

f(2) = (2 - 2)^3(2 + 1) = 0

При x = -1 нулём становится второй:

f(-1) = (-1 - 2)^3(-1 + 1) = 0

Но их кратности различаются.

Корень 2 имеет кратность 3.

Мы можем трижды разделить f(x) на x - 2 без остатка:

f(x) / (x - 2) = (x - 2)^2(x + 1)

Затем:

(x - 2)^2(x + 1) / (x - 2) = (x - 2)(x + 1)

И ещё раз:

(x - 2)(x + 1) / (x - 2) = x + 1

На этом останавливаемся: x + 1 уже не делится на x - 2 без остатка.

Корень -1 имеет кратность 1.

Ему соответствует множитель:

x - (-1) = x + 1

Делим исходный многочлен:

f(x) / (x + 1) = (x - 2)^3

Повторно разделить на x + 1 без остатка уже нельзя.

Общее определение

Пусть F — поле, f(x) ∈ F[x], а a ∈ F. Число a называется корнем кратности k, если:

(x - a)^k

делит f(x) без остатка, но:

(x - a)^(k+1)

уже не делит его без остатка.

То есть кратность показывает, сколько раз можно убрать множитель x - a из многочлена, прежде чем деление перестанет быть возможным без остатка. Если кратность равна 1, корень называется простым. Если больше 1 — кратным.

Remainder theorem (теорема об остатке)

Мы уже знаем, как делить многочлены с остатком. Но если делитель имеет вид:

x - a

существует гораздо более простой способ найти остаток.

Remainder theorem утверждает: остаток от деления f(x) на x - a равен f(a). То есть вместо деления достаточно подставить a в исходный многочлен.

Пример

Возьмём многочлен над Q:

f(x) = x² + 3x + 2

Допустим, мы хотим найти остаток от деления на:

x - 2

По Remainder theorem достаточно вычислить:

f(2) = 2² + 3·2 + 2
     = 4 + 6 + 2
     = 12

Значит, остаток равен 12.

Проверим обычным делением. Сначала делим старшие члены:

x² / x = x

Умножаем делитель на x и вычитаем:

(x² + 3x + 2) - (x² - 2x) = 5x + 2

Теперь делим:

5x / x = 5

Снова умножаем и вычитаем:

(5x + 2) - (5x - 10) = 12

Получили:

q(x) = x + 5
r = 12

То есть:

x² + 3x + 2 = (x - 2)(x + 5) + 12

Остаток действительно равен f(2) = 12.

Почему это работает

Пусть F — поле, f(x) ∈ F[x] и a ∈ F. По алгоритму деления мы можем записать:

f(x) = (x - a)q(x) + r(x)

Поскольку делитель x - a имеет степень 1, остаток должен иметь степень меньше 1. Значит, остаток — обычная константа r (в том числе возможно 0).

Теперь подставим x = a:

f(a) = (a - a)q(a) + r

Но:

a - a = 0

Поэтому:

f(a) = 0 + r = r

Вот и всё доказательство: при подстановке x = a вся часть с делителем исчезает, и остаётся только остаток.

Связь с корнями многочлена

Из Remainder theorem следует ещё одно полезное свойство. Если:

f(a) = 0

то остаток от деления на x - a равен 0. Значит, многочлен делится на x - a без остатка. Например, для нашего многочлена:

f(x) = x² + 3x + 2

проверим a = -1:

f(-1) = (-1)² + 3·(-1) + 2
      = 1 - 3 + 2
      = 0

Следовательно, f(x) делится на x + 1 без остатка.

И действительно:

x² + 3x + 2 = (x + 1)(x + 2)

Таким образом, Remainder theorem позволяет не только находить остатки без деления, но и проверять, является ли число корнем многочлена.

Factor theorem (теорема о множителе)

В предыдущем разделе мы выяснили, что остаток от деления многочлена f(x) на x - a равен f(a). Отсюда следует важный результат: если a — корень многочлена, то x - a является его множителем. И наоборот: если x - a — множитель многочлена, то a обязательно является его корнем.

Формально, для f(x) ∈ F[x] и a ∈ F:

f(a) = 0 ⇔ (x - a) | f(x)

Это и есть factor theorem.

Почему это работает

По Remainder theorem:

f(x) = (x - a)q(x) + f(a)

Если a — корень, то f(a) = 0. Следовательно:

f(x) = (x - a)q(x)

То есть многочлен делится на x - a без остатка.

Обратно, если x - a делит f(x) без остатка, то по Remainder theorem:

f(a) = 0

Значит, a — корень.

Пример: находим множители многочлена

Рассмотрим:

f(x) = x² - 4x + 3

Допустим, мы хотим разложить его на множители.

Начнём с проверки, является ли 1 корнем:

f(1) = 1² - 4·1 + 3 = 0

Получили 0. Значит, по Factor theorem многочлен обязательно делится на:

x - 1

Теперь разделим:

(x² - 4x + 3) / (x - 1) = x - 3

Таким образом:

f(x) = (x - 1)(x - 3)

Мы нашли разложение на множители!

Заодно видим, что второй корень — 3, поскольку:

f(3) = 3² - 4·3 + 3 = 0

Зачем нужна Factor theorem

Теорема связывает две задачи:

  • Поиск корней: подставляем число a и проверяем, равно ли f(a) нулю.
  • Разложение на множители: если нашли корень a, можем выделить множитель x - a и разделить на него многочлен.

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

Polynomials over a field have at most n roots

Из Factor theorem следует важное свойство: ненулевой многочлен степени n над полем не может иметь больше n корней, даже если учитывать их кратности. Например, многочлен степени 2 не может иметь пять разных корней. Почему?

Почему количество корней ограничено

Вспомним Factor theorem: если a — корень многочлена f(x), то x - a является его множителем.

То есть:

f(x) = (x - a)q(x)

Допустим, мы нашли ещё один корень b, отличный от a.

Тогда:

f(b) = (b - a)q(b) = 0

Поскольку a и b различны:

b - a ≠ 0

А в поле нет делителей нуля. Поэтому, чтобы произведение равнялось 0, обязательно:

q(b) = 0

Значит, b — корень оставшегося многочлена q(x), и мы можем выделить ещё один множитель:

f(x) = (x - a)(x - b)h(x)

Каждый раз, когда мы выделяем такой множитель, степень оставшегося многочлена уменьшается на 1. Если исходная степень равна n, мы не можем проделать это больше n раз. Таким образом, у многочлена степени n не может быть больше n различных корней.

Если учитывать кратности, ограничение остаётся тем же. Например:

f(x) = (x - 2)^2(x + 1)

Этот многочлен имеет степень 3.

Примечание: степень многочлена определяется наибольшей степенью x после раскрытия скобок. При умножении ненулевых многочленов над полем их степени складываются.

Например:

f(x) = (x - 2)²(x + 1)

Первый множитель имеет степень 2, второй — 1. Поэтому степень всего многочлена равна 2 + 1 = 3.

Действительно:

f(x) = x³ - 3x² + 4

Наибольшая степень x здесь — 3.

У этого многочлена только два различных корня:

  • 2 — кратность 2.
  • -1 — кратность 1.

С учётом кратностей получаем 2 + 1 = 3, что соответствует степени многочлена.

При этом корней может быть и меньше n. Например, x² + 1 не имеет корней в R, хотя его степень равна 2.

Почему важно работать над полем

В кольцах с делителями нуля ситуация может быть другой. Рассмотрим многочлен над Z12:

f(x) = x² - 4x + 3

Его степень равна 2. Но проверим несколько значений:

f(1) = 1 - 4 + 3 = 0

f(3) = 9 - 12 + 3 = 0

f(7) = 49 - 28 + 3 = 24 ≡ 0 (mod 12)

f(9) = 81 - 36 + 3 = 48 ≡ 0 (mod 12)

Получается, что у многочлена степени 2 есть целых четыре различных корня в Z12:

1, 3, 7, 9

Как такое возможно?

Разложим многочлен:

f(x) = (x - 1)(x - 3)

В поле такое разложение означало бы, что произведение равно нулю только при x = 1 или x = 3.

Но в Z12 есть делители нуля.

Например, при x = 7:

f(7) = (7 - 1)(7 - 3)
     = 6 · 4
     = 24
     ≡ 0 (mod 12)

Хотя ни 6, ни 4 не равны нулю в Z12, их произведение равно нулю. Поэтому 7 тоже является корнем!

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

Example: complex roots of x^n - 1

Теперь применим нашу теорему к комплексным числам.

Рассмотрим многочлен:

f(x) = x^n - 1

Мы хотим найти все его комплексные корни:

x^n - 1 = 0

То есть все числа, для которых:

x^n = 1

Такие числа называются корнями n-й степени из единицы (nth roots of unity).

Один корень очевиден:

x = 1

поскольку 1^n = 1.

Но в комплексных числах существуют и другие решения.

Primitive nth root of unity

Рассмотрим комплексное число:

ω = cos(360°/n) + i·sin(360°/n)

Оно лежит на единичной окружности комплексной плоскости и соответствует углу 360°/n.

По формуле Муавра возведение такого числа в степень n умножает угол на n:

n · (360°/n) = 360°

Поэтому:

ω^n = cos(360°) + i·sin(360°) = 1

Значит, ω — корень многочлена x^n - 1.

Но мы можем взять и другие степени ω:

1, ω, ω², ..., ω^(n-1)

Все они тоже являются корнями, потому что:

(ω^k)^n = (ω^n)^k = 1

Причём эти n чисел различны: они соответствуют разным углам на единичной окружности.

Например, при n = 4:

ω = cos(90°) + i·sin(90°) = i

Его степени:

ω^0 = 1
ω^1 = i
ω^2 = -1
ω^3 = -i

Все четыре числа удовлетворяют уравнению:

x^4 = 1

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

Аналогично для произвольного n мы получаем ровно n различных комплексных корней:

1, ω, ω², ..., ω^(n-1)

Число ω, степени которого дают все n различных корней, называется primitive nth root of unity (первообразным корнем n-й степени из единицы).

Итог

Ненулевой многочлен степени n над полем имеет не более n корней с учётом кратностей. Это свойство позволяет не только ограничивать количество возможных решений, но и доказывать, что мы уже нашли все корни многочлена.

Именно так мы установили, что список:

1, ω, ω², ..., ω^(n-1)

содержит все комплексные корни уравнения x^n = 1.

Principal Ideal Domain (PID)

Вспомним, что главный идеал (principal ideal) — это идеал, порождённый одним элементом. В коммутативном кольце R с единицей он имеет вид:

<a> = {ra | r ∈ R}

То есть мы берём элемент a, умножаем его на все элементы кольца и получаем идеал.

Например, в Z:

<6> = 6Z = {..., -12, -6, 0, 6, 12, ...}

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

Что такое PID

Principal Ideal Domain (PID) — это область целостности, в которой каждый идеал является главным. То есть должны выполняться два условия:

  1. R — область целостности (integral domain).
  2. Для любого идеала I существует элемент a ∈ R, такой что:
I = <a>

Иными словами, для описания любого идеала достаточно одного порождающего элемента.

Пример: Z является PID

В кольце целых чисел все идеалы имеют вид:

nZ

где n — некоторое неотрицательное целое число.

Но каждый такой идеал порождён одним элементом:

nZ = <n>

Например:

12Z = <12>

Даже если мы попробуем породить идеал несколькими числами, всё равно окажется, что достаточно одного.

Например, рассмотрим идеал, порождённый 6 и 10:

<6, 10>

Он содержит всевозможные целочисленные комбинации этих чисел:

6a + 10b, где a, b ∈ Z

Но заметим:

10 - 6 = 4
6 - 4 = 2

Следовательно, 2 тоже принадлежит этому идеалу. При этом любая комбинация 6a + 10b чётная, то есть принадлежит 2Z. А поскольку идеал содержит 2, он содержит и все кратные 2. Поэтому:

<6, 10> = <2> = 2Z

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

Z is a PID

Почему F[x] тоже является PID

Теперь рассмотрим кольцо многочленов:

F[x]

где F — поле. Для него справедлива теорема:

Если F — поле, то F[x] является PID.

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

Почему это работает

Пусть I — ненулевой идеал в F[x]. Выберем из него ненулевой многочлен с наименьшей степенью и назовём его:

g(x)

Почему выбираем именно минимальную степень? Потому что мы хотим доказать, что любой другой многочлен из I делится на g(x) без остатка. Если это так, то все элементы I являются кратными g(x), а значит, одного этого многочлена достаточно для порождения всего идеала:

I = <g(x)>

Проверим наше предположение. Возьмём произвольный многочлен:

f(x) ∈ I

Поскольку F — поле, в F[x] работает алгоритм деления. Поэтому:

f(x) = g(x)q(x) + r(x)

где остаток r(x) равен нулю или имеет степень меньше степени g(x):

deg r < deg g

Теперь выразим остаток:

r(x) = f(x) - g(x)q(x)

Обратим внимание:

  • f(x) принадлежит идеалу I по условию.
  • g(x) тоже принадлежит I, поэтому g(x)q(x) принадлежит I по свойству идеала.
  • Разность двух элементов идеала также принадлежит этому идеалу.

Следовательно:

r(x) ∈ I

И вот здесь возникает ключевой момент. Мы специально выбрали g(x) как ненулевой многочлен минимальной степени среди всех элементов I. Но если остаток r(x) ненулевой, то он тоже находится в I и имеет ещё меньшую степень:

deg r < deg g

Это противоречит нашему выбору g(x)!

Поэтому остаётся только один вариант:

r(x) = 0

Значит, деление прошло без остатка:

f(x) = g(x)q(x)

Иными словами, любой многочлен f(x) из идеала делится на g(x). Следовательно, все элементы I являются кратными g(x):

I ⊆ <g(x)>

С другой стороны, поскольку g(x) ∈ I, все его кратные тоже принадлежат I:

<g(x)> ⊆ I

Поэтому:

I = <g(x)>

Таким образом, любой ненулевой идеал в F[x] является главным. Нулевой идеал тоже главный:

{0} = <0>

А поскольку F[x] является областью целостности, получаем:

F[x] is a PID

Конкретный пример

Рассмотрим кольцо Q[x] — многочлены с рациональными коэффициентами. Пусть идеал I порождён двумя многочленами:

f(x) = x² - 1
g(x) = x² - x

То есть:

I = <x² - 1, x² - x>

Это означает, что I содержит все выражения вида:

a(x)(x² - 1) + b(x)(x² - x)

где a(x) и b(x) — любые многочлены из Q[x]. Но попробуем найти один многочлен, которого достаточно для порождения всего идеала. Вычтем второй порождающий многочлен из первого:

(x² - 1) - (x² - x) = x - 1

Поскольку идеал замкнут относительно вычитания, получаем:

x - 1 ∈ I

А значит, все кратные x - 1 тоже принадлежат I:

<x - 1> ⊆ I

Теперь заметим, что оба исходных многочлена делятся на x - 1:

x² - 1 = (x - 1)(x + 1)

x² - x = x(x - 1)

Следовательно, любая их комбинация:

a(x)(x² - 1) + b(x)(x² - x)

тоже делится на x - 1. Поэтому:

I ⊆ <x - 1>

Получаем:

I = <x - 1>

Мы начали с идеала, порождённого двумя многочленами, а выяснили, что достаточно одного. Именно такое свойство гарантирует теорема о PID для любого идеала в F[x].

Итог

В PID каждый идеал можно описать с помощью одного порождающего элемента. Для Z это связано с делимостью целых чисел и наибольшим общим делителем. Для F[x] — с делением многочленов с остатком: ненулевой многочлен минимальной степени в идеале обязательно делит все остальные элементы этого идеала.

Поэтому:

Z is a PID

F[x] is a PID, если F — поле

Но это не означает, что любое кольцо многочленов является PID. Например, Z[x] не является PID.

Как найти порождающий многочлен идеала

Мы доказали, что F[x] является PID, если F — поле. Значит, любой идеал в F[x] можно породить одним многочленом. Но как найти этот многочлен?

Для этого существует простой критерий:

Если I — ненулевой идеал в F[x], то любой ненулевой многочлен минимальной степени в I порождает весь идеал.

То есть если мы нашли такой g(x) ∈ I, что среди ненулевых элементов I нет многочленов меньшей степени, то:

I = <g(x)>

Почему? Мы уже показали, что любой многочлен из I должен делиться на g(x) без остатка. Иначе остаток тоже принадлежал бы I, но имел бы меньшую степень. Это противоречило бы выбору g(x).

Верно и обратное: если ненулевой g(x) порождает весь идеал, то он имеет минимальную степень среди ненулевых элементов I. Ведь все остальные элементы идеала — его кратные и не могут иметь меньшую степень.

Пример

Рассмотрим идеал в Q[x]:

I = <x² - 1, x² - x>

Вычтем один порождающий многочлен из другого:

(x² - 1) - (x² - x) = x - 1

Поскольку идеал замкнут относительно вычитания:

x - 1 ∈ I

Мы нашли многочлен степени 1. Может ли в I находиться ненулевой многочлен ещё меньшей степени, то есть константа? Нет. Оба исходных многочлена обращаются в ноль при x = 1. Следовательно, любая их комбинация тоже обращается в ноль при x = 1. Но ненулевая константа никогда не обращается в ноль.

Значит, x - 1 имеет минимальную степень среди всех ненулевых многочленов идеала.

По нашему критерию:

I = <x - 1>

Таким образом, чтобы найти один порождающий многочлен идеала в F[x], достаточно найти его ненулевой элемент минимальной степени.

Как получить комплексные числа из многочленов

Рассмотрим довольно неожиданное утверждение:

R[x] / <x² + 1> ≅ C

Оно означает, что фактор-кольцо многочленов с вещественными коэффициентами по идеалу <x² + 1> устроено точно так же, как поле комплексных чисел.

Но почему?

Что означает деление на идеал <x² + 1>

Начнём с кольца:

R[x]

Оно содержит все многочлены с вещественными коэффициентами. Например:

x² + 3x + 5
2x³ - x + 7
4x + 1

Теперь рассмотрим идеал:

I = <x² + 1>

Он состоит из всех многочленов, кратных x² + 1:

I = {(x² + 1)g(x) | g(x) ∈ R[x]}

Когда мы строим фактор-кольцо R[x]/I, мы считаем два многочлена эквивалентными, если их разность принадлежит I.

Например:

x² + 1

и:

0

принадлежат одному классу, поскольку их разность кратна x² + 1.

Значит, в фактор-кольце:

x² + 1 = 0

Здесь и далее под такими равенствами мы понимаем равенство классов в факто-ркольце, а не обычных многочленов в R[x].

Переносим единицу:

x² = -1

Вот главное изменение: в новом кольце квадрат x равен -1. В обычных вещественных числах такого элемента нет. Но в комплексных числах есть i, для которого:

i² = -1

Получается, что x в нашем факторкольце ведёт себя точно как мнимая единица i.

Что происходит с многочленами

Мы знаем, что в фактор-кольце:

x² = -1

Поэтому:

x³ = x·x² = -x
x⁴ = (x²)² = 1

И так далее.

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

f(x) = x³ + 2x² + 3x + 4

Заменим степени x по нашим правилам:

f(x) = -x + 2·(-1) + 3x + 4

     = 2 + 2x

То есть в фактор-кольце многочлены:

x³ + 2x² + 3x + 4

и:

2 + 2x

представляют один и тот же элемент.

Почему мы всегда можем так упрощать? Потому что любой многочлен можно разделить на x² + 1 с остатком:

f(x) = (x² + 1)q(x) + r(x)

Степень остатка должна быть меньше 2, поэтому:

r(x) = a + bx

где a, b ∈ R. А поскольку (x² + 1)q(x) принадлежит идеалу I, в фактор-кольце он равен нулю. Следовательно, каждый элемент фактор-кольца можно представить в виде:

a + bx

Но это практически запись комплексного числа! Ведь любое комплексное число имеет вид:

a + bi

Разница только в том, что вместо i мы используем x, для которого действует то же правило:

x² = -1

Проверим умножение

Чтобы убедиться, что сходство не ограничивается внешним видом, попробуем умножить два элемента фактор-кольца:

(1 + x)(2 + x)

Раскрываем скобки:

2 + 3x + x²

Но x² = -1, поэтому:

2 + 3x - 1 = 1 + 3x

А теперь выполним то же умножение с комплексными числами:

(1 + i)(2 + i)
= 2 + 3i + i²
= 1 + 3i

Результаты полностью соответствуют друг другу! Это подсказывает нам, что факторкольцо действительно изоморфно C. Осталось доказать это формально.

Строим гомоморфизм

Определим отображение:

φ: R[x] → C

по правилу:

φ(f(x)) = f(i)

То есть берём многочлен и подставляем вместо x число i.

Например:

φ(x² + 1) = i² + 1 = 0

А для нашего предыдущего многочлена:

φ(x³ + 2x² + 3x + 4)
= i³ + 2i² + 3i + 4
= -i - 2 + 3i + 4
= 2 + 2i

Это гомоморфизм колец, поскольку подстановка сохраняет сложение и умножение:

φ(f + g) = φ(f) + φ(g)

φ(fg) = φ(f)φ(g)

Теперь воспользуемся первой теоремой об изоморфизме. Для этого нужно найти ядро и образ нашего гомоморфизма.

Находим kernel

Вспомним: kernel — это все элементы, которые гомоморфизм отображает в ноль. В нашем случае:

Ker φ = {f(x) ∈ R[x] | f(i) = 0}

Мы уже знаем, что:

φ(x² + 1) = 0

Поэтому x² + 1 принадлежит ядру. Более того, все его кратные тоже принадлежат ядру. Но почему ядро состоит только из таких многочленов? Возьмём любой многочлен f(x) из ядра. Это означает:

f(i) = 0

Разделим его на x² + 1:

f(x) = (x² + 1)q(x) + ax + b

где a и b — вещественные числа.

Подставим x = i:

0 = (i² + 1)q(i) + ai + b

Поскольку i² + 1 = 0, получаем:

0 = ai + b

Но комплексное число b + ai равно нулю только тогда, когда обе его части равны нулю:

a = 0
b = 0

Следовательно, остаток от деления равен нулю. Значит, любой многочлен из ядра делится на x² + 1 без остатка. Поэтому:

Ker φ = <x² + 1>

Иными словами, ядро состоит ровно из многочленов, кратных x² + 1.

Находим image

Теперь выясним, какие комплексные числа можно получить с помощью φ. Любое комплексное число имеет вид:

a + bi

где a, b ∈ R. Но мы можем взять многочлен:

f(x) = a + bx

Тогда:

φ(f(x)) = a + bi

То есть любое комплексное число можно получить подстановкой x = i в некоторый вещественный многочлен. Следовательно, образ гомоморфизма — всё поле комплексных чисел:

Im φ = C

Применяем First Isomorphism Theorem

Теперь у нас есть всё необходимое. Первая теорема об изоморфизме колец утверждает:

R[x] / Ker φ ≅ Im φ

Мы установили, что:

Ker φ = <x² + 1>

и:

Im φ = C

Поэтому:

R[x] / <x² + 1> ≅ C

Что и требовалось доказать.

Почему это важно

Мы начали с обычного кольца вещественных многочленов R[x]. Затем построили факторкольцо по идеалу <x² + 1>. В этом новом кольце выполняется правило:

x² = -1

Оно позволило нам представить любой элемент в виде:

a + bx

где x ведёт себя как мнимая единица i. А с помощью гомоморфизма мы доказали, что полученная структура действительно изоморфна C.

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

В дальнейшем мы будем использовать похожий подход для построения конечных полей:

F_p[x] / <f(x)>

где f(x) — неприводимый многочлен над F_p. Если его степень равна n, полученное поле содержит:

p^n

элементов.