Mnogochlen

на множестве A[x] , а для любого многочлена [F ] обратным к нему (относительно операции сложения) будет элемент [¡F ].

¤

Операция умножения многочленов. На множестве формальных сумм одно-

ij

положим:

Предложение 2.3. Для любого k 2 N [ f0g:

X

¤

Ввиду Предложения 2.4. можно определить операцию умножения на множестве многочленов A[x], полагая

Доказательство. Пусть F; G; H 2 A[x]. Для любого k 2 N [ f0g:

Предложение 2.3 X X m+l=k i+j=m

11

¤

Кольцо многочленов от одной буквы (переменной).

Теорема 2.6 Множество A[x] многочленов от одной буквы является кольцом относительно операций сложения (2.1) и умножения (2.6), определенных выше.

Доказательство. Ввиду Предложений 2.2, 2.5, достаточно проверить дистрибутивность. Проверим дистрибутивность. Для любых F; G; H 2 A[x] и для k 2 N[ f0g:

i+j=k

Аналогично проверяется [H]([F ] + [G]) = [H][F ] + [H][G].

¤

Теорема 2.7 Если A-коммутативное кольцо, то и A[x]-коммутативное кольцо.

Доказательство. Следует из Предложения 2.3.

¤

Теорема 2.8 Если A- кольцо c единицей, то и A[x]- кольцо с единицей.

Доказательство. Пусть 1 2 A-единица кольца A. Тогда класс [1] одночлена 1A является единицей кольца A[x]. Это следует из определения операции умножения (2.5), (2.6).

¤

Соглашение. Единицу кольца A[x] также обозначаем символом 1.

Определение алгебраических операций на кольце многочленов через нормальную форму.

Можно определить операции те же сложения и умножения на A[x] используя лишь нормальные формы многочленов. А именно, пусть

f = a0xn + a1xn¡1 + ¢ ¢ ¢ + an; g = b0xm + b1xn¡1 + ¢ ¢ ¢ + bm;

где a0; b0 =6 0. Предположим, n ¸ m. Положим

b00 = 0; : : : ; b0n¡m = b0; b0n¡m+1 = b1; : : : ; b0n = bm; c00 = a0 + b00; c01 = a1 + b01; : : : ; c0n = an + b0n:

12

Если c0i = 0 для любого i , положим

def def

f + g = g + f = 0:

Пусть c0i =6 0 для некоторого i. Тогда положим

r = minfs j c0s =6 0g;

c0 = c0r; c1 = c0r+1; : : : ; cn¡r = c0n;

def def n¡r n¡r¡1

f + g = g + f = c0x + c1x + ¢ ¢ ¢ + cn¡r:

Очевидно, приведенное определение суммы двух многочленов соответствует предыдущему. Действительно, мы просто указали алгоритм построения нормальной формы для [f + g].

Далее, положим для любого k 2 [1; n + m]:

c0 = c0r; c1 = c0r+1; : : : ; cn+m¡r = c0n+m;

def n+m¡r n+m¡r¡1

fg = c0x + c1x + ¢ ¢ ¢ + cn+m¡r:

Oпределение произведения двух многочленов так же соответствует предыдущему. Действительно, ввиду пердложения 2.3

Пусть l = maxfk j ak(fg) =6 0g. Очевидно, l · n + m. Положим r = (n + m) ¡ l. Тогда l = (n + m) ¡ r и нормальная форма многочлена [fg] имеет вид

al(fg)xl + al¡1(fg)xl¡1 + ¢ ¢ ¢ + a0(fg):

Пусть теперь ck = al¡k(fg) для k = 0; : : : ; l = n + m ¡ r. Тогда

c0xn+m¡r + c1xn+m¡1 + ¢ ¢ ¢ + cn+m¡r

нормальная форма многочлена [fg]. С другой стороны,

13

Таким образом, определение коэффициентов в первом и во втором случае одно и то же.

Указанный выше способ определения операций на A[x] через нормалные формы позволяет определять многочлены как их нормальные формы, сохраняя возможность сложения и умножения таких форм. Здесь однако, следует проверять свойства операций, используя эти новые определения. В нашем случае такая проверка ненужна, поскольку мы показали , что второе определение можно рассматривать как вычисление нормальных форм в классах [f +g]; [fg], т.е. согласованность нового определения операций со старым, для которого соответствующая проверка свойств уже проведена.

Из алгоритмов построения нормальных форм в классах [f + g]; [fg] вытекает следующее

Предложение 2.9

deg(f + g) · maxfdeg f; deg gg; deg fg · deg f + deg g:

¤

Более того для умножения многочленов верно следующее уточнение

Предложение 2.10 Пусть f = a0xn+a1xn¡1+¢ ¢ ¢+an; g = b0xm+b1xn¡1+¢ ¢ ¢+bm;, где a0; b0 6= 0. Предположим, a0b0 6= 0. Тогда

deg fg = deg f + deg g:

Более того,

fg = c0xn+m + ¢ ¢ ¢ + ckxn+m¡k + ¢ ¢ ¢ + cn+m;

i+j=k

для любого k = 0; : : : ; n + m. В частности, c0 = a0b0.

Доказательство. Следует из (2.7) и условия a0b0 =6 0.

¤

Следствие 2.11 Пусть A-поле f; g 2 A[x]; f; g 6= 0. Тогда deg fg = deg f + deg g: Кроме того, старший коэффициент многочлена fg равен произведению старших коэффициентов многочленов f; g

Доказательство. Если A-поле и a0; b0 2 A; a0; b0 6= 0, то a0b0 6= 0.

¤

14

x 3: Наибольший обший делитель и наименшее общее кратное

в коммутативных кольцах.

Делимость в коммутативных кольцах.

Пусть S-коммутативное кольцо . Будем говорить, что элемент a 2 S делится на элемент b 2 S ( соответственно, элемент b делит элемент a), если существует элемент c 2 S такой,что a = bc. В этом случае будем писать a : b ( соответственно, a j b). (Для некоммутативных колец нужно было бы вводить понятия делимости слева a = bc и справа a = c0b в данном курсе мы будем расмматривать только коммутативные кольца, хотя определения многочлена давалось для произвольных колец.)

УПРАЖНЕНИЯ.

Докажите следующие простейшие своства делимости в коммутативном кольце . 1)

0 : a для любого a:

6)

1 2 S ) a : a; a : 1 для любого a:

7)

a : b; b : c ) a : c:

Наибольший общий делитель последовательности элементов коммутативного кольца.

15

Определение. 3.1. Пусть S-коммутативное кольцо.Общим делителем элементов s1; : : : ; sn 2 S называется такой элемент d 2 S, что s1 : d; : : : ; sn : d. Наибольшим общим делителем элементов s1; : : : ; sn 2 S называется такой общий делитель элементов s1; : : : ; sn, который делится на любой общий делитель этих элементов.

Наибольший общий делитель элементов s1; : : : ; sn 2 S будем обозначать символом

(s1; : : : ; sn).

Замечание. Напомним, что для кольца целых чисел S = Z наибольший общий делитель d = (z1; : : : ; zn) определялся как максимум среди общих делителей чисел z1; : : : ; zn. При таком определении наибольший общий делитель существует (если последовательность-неулевая), единственный и является натуральным числом. Если в качестве определения наибольшего общего делителя для S = Z взять Определение 2.1, то кроме натурального наибольшего общего делителя (z1; : : : ; zn) = d 2 N мы получим также отрицательный наибольший общий делитель (z1; : : : ; zn) = ¡d. Таким образом, в данном определении символ (s1; : : : ; sn) обозначает любой наибольший общий делитель. Отметим, что множество наибольших общих делителей в произволном кольце может быть очень велико (например, если S-поле, а s1; : : : ; sn 2 S, то любой ненулевой элемент поля является наибольшим общим делителем последовательности s1; : : : ; sn 2 S. Наибольший общий делитель последовательности (даже ненулевой) вообще может не существовать.

Пример.

Предложение 3.1 Пусть S-коммутативное кольцо. Предположим, что существует наибольший общий делитель элементов s1; : : : ; sn¡1 2 S и наибольший общий делитель элементов (s1; : : : ; sn¡1); sn 2 S. Тогда существует наибольший общий делитель элементов s1; : : : ; sn. При этом,

((s1; : : : ; sn¡1); sn) = (s1; : : : ; sn¡1; sn):

Доказательство. Пусть d = ((s1; : : : ; sn¡1); sn); d1 = ((s1; : : : ; sn¡1). Тогда:

Так как d j sn, то d- общий делитель для s1; : : : ; sn. Пусть d0- общий делитель для s1; : : : ; sn. Так как d0 общий делитель для s1; : : : ; sn¡1, то d0 j d1, а так как d0 j d1; d0 j sn, то d0 j d. Таким образом, d = ((s1; : : : ; sn¡1); sn) делится на любой общий делитель для s1; : : : ; sn.

¤

16

Следствие 3.2 Пусть S-коммутативное кольцо и s1; : : : ; sn¡1 2 S . Предположим, что существуют наибольшие общие делители

(s1; s2) = d1; ((s1; s2); s3) = d2; : : : ; (: : : ; ((s1; s2); s3) : : :)sn) = dn¡1:

Тогда

dn¡1 = (s1; : : : ; sn):

Доказательство. Индукция по n.

¤

Предложение 3.3 Пусть S-коммутативное кольцо с единицей и a = bc 2

S; b; c; 2 S. Тогда

b = (a; b):

Доказательство. a : b; b : b (Свойство 6). Таким образом, b-общий делитель a; b. Далее,

d j a; b ) d j b:

¤

Предложение 3.4 Пусть S-коммутативное кольцо с единицей и a = bc + d 2 S; b; c; d 2 S. Наибольший общий делитель (a; b) существует тогда и только тогда, когда существует наибольший общий делитель (b; d). При этом,

(a; b) = (b; d):

Доказательство. Предположим существует наибольший общий делитель (a; b). Тогда

Таким образом, (a; b)-общий делитель b; d. Пусть e-общий делитель b; d. Тогда e j a (Свойства 2),3). Следовательно, e-общий делитель a; b, а значит e делит наибольший общий делитель (a; b). Поэтому (a; b)- это также и наибольший общий делитель b; d.

Доказательство того, что наибольший общий делитель b; d-это также и наибольший общий делитель a; b проводится аналогично.

¤

Наименьшее общее кратное последовательности элементов коммутативного кольца.

17

Определение. 3.2. Пусть S-коммутативное кольцо.Общим кратным элементов s1; : : : ; sn 2 S называется такой элемент m 2 S, что s1 j m; : : : ; sn j m. Наименьшим общим кратным элементов s1; : : : ; sn 2 S называется такое общее кратное элементов s1; : : : ; sn, которое делит любое общее кратное этих элементов.

Наименьшее общее кратное элементов s1; : : : ; sn 2 S будем обозначать символом

[s1; : : : ; sn].

Замечания , сделанные к определению наибольшего общего делителя также справедливы и к данному определению наименьшего общего кратного. Кроме того, справедливы аналогичные утверждения Предложению 3.1 и Следствию 3.2 (проверьте!). Таким образом, если существуют

[s1; s2] = m1; [[s1; s2]; s3] = m2; : : : ; [: : : ; [[s1; s2]; s3] : : :]sn = mn¡1:

Тогда

mn¡1 = [s1; : : : ; sn]:

x 4: Наибольший общий делитель

вкольце многочленов над полем.

Вданном параграфе K-поле, а S = K[x]-кольцо многочленов от одной буквы над полем K. Напомним, что такое кольцо является коммутативным кольцом с единицей (Теоремы 2.7, 2.8), в котором произведение ненулевых элементовтакже ненулевой элемент (Следствие 2.11).

Здесь мы рассмотрим свойства наибольшего общего делителя пары элементов в кольце K[x].

Деление с остатком.

Определение. 4.1. Будем говорить, что многочлен f 2 K[x] делится с остатком на многочлен g 2 K[x], если существует такие многочлены q; r 2 K[x], что deg r < deg g или r = 0 и

f = gq + r:

При этом многочлен g называется делителем f, многочлен q частным от деления f на g , а r остатком.

18

Замечание 4.1. В данном определении делимость f на g эквивалентна деленимости с нулевым остатком.

Теорема 4.1 Пусть f; g 2 K[x]; g 6= 0. Тогда f делится с остатком на g. При этом, частное и отаток такого деления определены однозначно многочленами f; g

Доказательство.

I. Возможность деления с отатком.

1) Случай : deg f < deg g. Тогда положим q = 0; r = f. Получим деление с остатком:

f = g0 + f (deg f < deg g):

2) Случай : deg f ¸ deg g. Проведем доказательство индукцией по n = deg f. База индукции - предыдущий случай n < deg g (можно считать deg g ¸ 1, поскольку при deg g = 0; g =6 0 всегда имеем деление с остатком 0: f = g(g¡1f) + 0). Предположим, для любого многочлена Á 2 K[x]; deg Á < n возможно деление с остатком Á на g. Пусть

f = a0xn + a1xn¡1 + ¢ ¢ ¢ + an; g = b0xm + b1xn¡1 + ¢ ¢ ¢ + bm;

где a0; b0 =6 0. Имеем

Ввиду предположения индукции

(f ¡ a0b¡0 1xn¡mg) = gq0 + r; q0; r 2 K[x]; deg r < deg g:

¤

Замечание 4.2. Индукционный переход (4.1) дает алгоритм деления с остатком. А именно, вычисляем:

f1 = f ¡ a0b¡0 1xn¡mg = a01 xn1 + ¢ ¢ ¢ + an1 ; a01 =6 0; m · n1 < n; f2 = f1 ¡ a01 b¡0 1xn1¡mg = a02 xn2 + ¢ ¢ ¢ + an2 ; a02 =6 0; m · n2 < n1;

19

: : :

fk¡1 = fk¡2 ¡ a0k¡2 b¡0 1xnk¡2¡mg = a0k¡1 xnk¡1 + ¢ ¢ ¢ + ank¡1 ; a0k¡1 =6 0; m · nk¡1 < nk¡2; fk = fk¡1 ¡ a0k¡1 b¡0 1xnk¡1¡mg = a0k xnk + ¢ ¢ ¢ + ank ; a0k =6 0; nk < m:

Полагаем

r := fk; q = a0b¡0 1xn¡m + a01 b¡0 1xn1¡m + ¢ ¢ ¢ + a0k¡1 b¡0 1xnk¡1¡m:

Суммируя равенства получим:

f1 + f2 + ¢ ¢ ¢ + fk = f + f1 + ¢ ¢ ¢ + fk¡1 ¡ gq:

Отсюда

f = gq + r:

Приведенный алгоритм -это и есть хорошо известный алгоритм деления с остатком "столбиком".

Замечание 4.3. Заметим, что в приведенном выше алгоритме требуется лишь обратимость старшнего коэффициента b0. Поэтому, возможность ( и единственность !) деления с остатком возможна и в кольце многочленов A[x] над кольцом с единицей при условии, что старший коэффициент делителя b0 обратим в A (т.е. , существует b¡1 2 A). Заметим также, что делимость с остатком на двучлен g = x ¡ a возможна ( и единственна !) над любым кольцом (здесь мы просто опускаем b¡0 1).

Алгоритм Евклида.

Определение. 4.2. Алгоритмом Евклида в кольце K[x] называется последовательность операций деления с остатком:

f = gq1 + r1; f; g; q1; r1 2 K[x]; g =6 0; deg r1 < deg g;

которая начинается с пары многочленов f; g (g 6= 0) и каждый следующий шаг которой есть деление пердыдущего остатка ri¡1 на последующий ri (многочлен g считаем r0-остатком). Закначивается алгоритм на шаге, на котором происходит деление нацело (т.е. с нулевым остатком):

20