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

July 3, 2026 #абстрактная алгебра #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:

обычно не имеет 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 / константным многочленом.

Например:

являются constant polynomials.

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

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.

Пример division в `Z5[x]`

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

Z5[x]

Пусть:

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

и:

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

Мы хотим найти quotient и remainder:

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

где:

deg r < deg g

Так как:

deg g = 2

остаток должен иметь degree меньше 2, то есть быть linear polynomial или constant:

r(x) = ax + b

После polynomial long division над Z5 получаем:

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

и:

r(x) = 2x + 1

То есть:

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

Важно: все coefficients считаются modulo 5.

Например:

6 ≡ 1 (mod 5)

-1 ≡ 4 (mod 5)

10 ≡ 0 (mod 5)

Поэтому polynomial division выглядит как обычное деление polynomials, но все coefficient operations делаются в Z5.

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 root

Пусть F — field, a ∈ F, и:

f(x) ∈ F[x]

Говорят, что a — zero of multiplicity k, если:

(x - a)^k

divides f(x), но:

(x - a)^(k+1)

уже не divides f(x).

То есть multiplicity показывает, сколько раз factor:

x - a

сидит внутри polynomial.

Пример

Рассмотрим:

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

Тогда 2 — root of multiplicity 3, потому что factor:

x - 2

встречается три раза.

А -1 — root of multiplicity 1, потому что factor:

x + 1

встречается один раз.

Remainder theorem

Пусть F — field, a ∈ F, и:

f(x) ∈ F[x]

Если разделить f(x) на:

x - a

то remainder будет равен:

f(a)

То есть:

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

Это называется Remainder Theorem.

Почему remainder именно `f(a)`

По division algorithm:

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

Так как divisor:

x - a

имеет degree 1, remainder должен иметь degree меньше 1. Значит remainder — это constant:

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

x = a

Получаем:

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

Но:

a - a = 0

поэтому:

f(a) = r

Значит remainder равен:

f(a)

Factor theorem

Пусть F — field, a ∈ F, и:

f(x) ∈ F[x]

Тогда a является zero polynomial f(x) тогда и только тогда, когда:

x - a

is a factor of f(x).

То есть:

f(a) = 0

if and only if:

x - a | f(x)

Почему это следует из remainder theorem

По remainder theorem, при делении f(x) на:

x - a

remainder равен:

f(a)

Если:

f(a) = 0

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

x - a

divides f(x). Обратно, если:

x - a | f(x)

то remainder равен 0, а значит:

f(a) = 0

Пример factor theorem

Рассмотрим:

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

Проверим:

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

Значит по factor theorem:

x - 1

is a factor of f(x).

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

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

Также:

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

поэтому:

x - 3

тоже factor.

Polynomials over a field have at most `n` roots

Ещё одно важное следствие factor theorem:

polynomial degree n over a field has at most n roots, counting multiplicity.

То есть если:

deg f(x) = n

то у f(x) не может быть больше n roots в field F.

Например, polynomial degree 2 не может иметь 5 разных roots over a field.

Почему это верно

Если a — root polynomial f(x), то по factor theorem:

x - a

is a factor of f(x).

То есть:

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

Каждый root даёт хотя бы один linear factor. Если roots несколько, polynomial должен содержать несколько such factors:

(x - a1)(x - a2)...(x - ak)

Но degree произведения этих factors равна k. Поэтому если polynomial имеет degree n, в него нельзя вместить больше чем n linear factors. Значит roots может быть не больше n.

Почему важно “over a field”

Это утверждение работает over fields. В rings with zero divisors всё может ломаться. Например, over Z12 polynomial:

x^2 - 4x + 3

degree 2, но solutions могут быть:

1, 3, 7, 9

То есть roots больше, чем degree. Причина та же: в Z12 есть zero divisors, поэтому привычная логика factor theorem и counting roots работает хуже.

Example: complex zeros of `x^n - 1`

Рассмотрим polynomial:

x^n - 1

over complex numbers. Мы хотим найти все complex roots:

x^n - 1 = 0

То есть:

x^n = 1

Такие числа называются:

nth roots of unity

Одно из них очевидно:

потому что:

1^n = 1

Но over complex numbers есть ещё roots.

Primitive nth root of unity

Определим:

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

Это complex number на unit circle.

По De Moivre’s theorem:

ω^n = 1

Кроме того, powers:

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

дают n разных roots polynomial:

x^n - 1

Так как degree polynomial равна n, других roots быть не может. Поэтому все complex roots of:

x^n - 1

это:

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

Элемент ω называется:

primitive nth root of unity

Principal Ideal Domain

Теперь вернёмся к ideals. Principal ideal / главный идеал — это ideal, generated by one element:

<a> = {ra | r ∈ R}

То есть ideal состоит из всех multiples одного элемента a.

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

<6> = 6Z

Definition: PID

Principal Ideal Domain / PID — это integral domain, в котором every ideal is principal.

То есть R является PID, если:

R — integral domain;
каждый ideal I имеет вид:

I = <a>

для некоторого:

a ∈ R

Иными словами:

в PID любой ideal можно породить одним элементом.

Example: `Z` is a PID

Integers:

являются PID. Почему? Все ideals в Z имеют вид:

nZ

А:

nZ = <n>

То есть каждый ideal generated by one integer. Например:

12Z = <12>

Поэтому:

Z is a PID

`F[x]` is a PID

Теперь важный theorem:

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

То есть в polynomial ring over a field every ideal is generated by one polynomial.

F[x] is a PID

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

Пусть I — nonzero ideal в:

F[x]

Выберем в I nonzero polynomial минимальной degree:

g(x)

Мы хотим показать:

I = <g(x)>

То есть каждый polynomial из I должен быть multiple of g(x).

Возьмём любой:

f(x) ∈ I

Так как F — field, в F[x] работает division algorithm.

Значит можно разделить f(x) на g(x):

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

где:

r(x) = 0

или:

deg r < deg g

Теперь:

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

Так как f(x) ∈ I, g(x) ∈ I, and I is an ideal, получаем:

r(x) ∈ I

Но g(x) был выбран как nonzero polynomial минимальной degree в I. Поэтому в I не может быть nonzero polynomial меньшей degree.

Значит:

r(x) = 0

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

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

То есть:

f(x) ∈ <g(x)>

А значит:

I = <g(x)>

Поэтому:

F[x] is a PID

Criterion for `I = <g(x)>`

Пусть:

— field, I — nonzero ideal in:

F[x]

и:

g(x) ∈ I

Тогда:

I = <g(x)>

if and only if g(x) is a nonzero polynomial of minimum degree in I. То есть generator ideal можно найти так:

взять ненулевой polynomial минимальной degree внутри ideal.

Это работает именно because F[x] is a PID.

Application: `R[x] / <x^2 + 1>` and complex numbers

Теперь можно аккуратно объяснить старый пример:

R[x] / <x^2 + 1>

Этот quotient ring isomorphic to complex numbers:

R[x] / <x^2 + 1> ≅ C

Идея простая. В quotient ring мы считаем:

x^2 + 1 = 0

то есть:

x^2 = -1

А в complex numbers есть элемент:

для которого:

i^2 = -1

Значит x в quotient ring ведёт себя как i.

Homomorphism `R[x] -> C`

Определим evaluation map:

φ : R[x] -> C

по правилу:

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

То есть мы берём real polynomial и подставляем:

x = i

Например:

φ(x^2 + 1) = i^2 + 1 = -1 + 1 = 0

Значит:

x^2 + 1 ∈ Ker φ

Kernel

Kernel consists of all real polynomials that become 0 after substituting i. То есть:

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

Polynomial:

x^2 + 1

лежит в kernel. Более того:

Ker φ = <x^2 + 1>

Интуитивно: over R, polynomial x^2 + 1 is exactly the minimal polynomial relation that forces x to behave like i.

Image

Image of φ is all of C. Почему? Любое complex number имеет вид:

a + bi

где:

a, b ∈ R

Но это значение polynomial:

a + bx

при:

x = i

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

φ(a + bx) = a + bi

Значит:

φ(R[x]) = C

Apply First Isomorphism Theorem

По First Isomorphism Theorem for rings:

R[x] / Ker φ ≅ φ(R[x])

Подставляем:

Ker φ = <x^2 + 1>

и:

φ(R[x]) = C

Получаем:

R[x] / <x^2 + 1> ≅ C

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

Это один из главных паттернов всей темы:

field/polynomial ring
↓
quotient by ideal
↓
new ring or field with desired relation

В данном случае мы стартовали с real polynomials:

R[x]

и добавили relation:

x^2 = -1

В результате получили complex numbers. Позже похожая идея будет использоваться для finite fields:

F_p[x] / <irreducible polynomial>

Так строятся fields with:

p^n

elements.

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

Что такое coefficient

Polynomial как formal object

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

Пример в Z3[x]

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

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

Addition в R[x]

Multiplication в R[x]

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

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

Degree

Leading coefficient

Monic polynomial

Constant polynomial

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

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

Division algorithm for polynomials

Division algorithm в F[x]

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

Пример division в Z5[x]

Divisibility polynomials

Пример

Zeros / roots polynomial

Multiplicity root

Пример

Remainder theorem

Почему remainder именно f(a)

Factor theorem

Почему это следует из remainder theorem

Пример factor theorem

Polynomials over a field have at most n roots

Почему это верно

Почему важно “over a field”

Example: complex zeros of x^n - 1

Primitive nth root of unity

Principal Ideal Domain

Definition: PID

Example: Z is a PID

F[x] is a PID

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

Criterion for I = <g(x)>

Application: R[x] / <x^2 + 1> and complex numbers

Homomorphism R[x] -> C

Kernel

Image

Apply First Isomorphism Theorem

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

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

Пример в `Z3[x]`

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

Addition в `R[x]`

Multiplication в `R[x]`

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

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

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

Division algorithm в `F[x]`

Пример division в `Z5[x]`

Почему remainder именно `f(a)`

Polynomials over a field have at most `n` roots

Example: complex zeros of `x^n - 1`

Example: `Z` is a PID

`F[x]` is a PID

Criterion for `I = <g(x)>`

Application: `R[x] / <x^2 + 1>` and complex numbers

Homomorphism `R[x] -> C`