Е.Е. Тыртышников - Основы алгебры (1109873), страница 7
Текст из файла (страница 7)
. , p − 1. 2В качестве следствия легко получается малая теорема Ферма: если p простое и.(a, p) = 1, то ap−1 − 1 .. p. Достаточно перемножить рассмотренные выше равенстваи заметить, что (p − 1)! = r1 . . . rp−1 . В результате находим..(p − 1)! (ap−1 − 1) .. p, ((p − 1)!, p) = 1 ⇒ ap−1 − 1 .. p.Теорему о поле вычетов можно превратить в несколько более общее и более абстрактное утверждение.Теорема 2.2.2 Конечное ассоциативное коммутативное кольцо является полемтогда и только тогда, когда в нем нет делителей нуля.Доказательство. Если делители нуля есть, то это не поле.
Пусть их нет. Предположим, что кольцо имеет m ненулевых элементов a1 , . . . , am . Тогда элементы ak a1 ,ak a2 , . . ., ak am должны быть разными: если ak ai = ak aj , то ak (ai − aj ) = 0. Посколькуделителей нуля нет и ak 6= 0, получаем ai = aj . Значит, для любых ak и al уравнениеak x = al имеет решение в данном кольце. 2Существенно более трудным оказывается следующее интересное утверждение.Теорема 2.2.3 (малая теорема Веддерберна) Конечное ассоциативное кольцос единицей и без делителей нуля является полем.Задача 66. Посчитайте число различных невырожденных матриц с коэффициентами из поля вычетов по простому модулю p.Задача 67.
Пусть p – простое число. Найдите сумму и произведение всех ненулевых вычетов по модулю p.Задача 68. Пусть a и b – произвольные элементы поля вычетов по простомумодулю p. Докажите равенство(a + b)p = ap + bp .Задача 69. Пусть n – натуральное число и Z∗n := {[a] ∈ Zn : (a, n) = 1}. Докажите, что множество Z∗n является группой относительно операции умножениявычетов по модулю n.Задача 70. Докажите следующую теорему Эйлера: если a и n – взаимно простыенатуральные числа, то.aφ(n) − 1 .. n.Задача 71. Докажите, что в поле Zp при простом p ≥ 3 число элементов a, длякоторых уравнение x2 = a имеет решение x ∈ Zp , равно (p − 1)/2 + 1.292.3Кольцо многочленовВсюду в дальнейшем мы будем рассматривать только ассоциативные кольца.Многочленом от переменной (буквы, символа) x над кольцом K называется формальное выражение видаa(x) = a0 + a1 x + a2 x2 + .
. . ,где коэффициенты a0 , a1 , a2 , . . . принадлежат K и лишь конечное их число отличноот нуля. Многочлен однозначно сопоставляется с бесконечной последовательностьюэлементов кольца K, в которой имеется лишь конечное число ненулевых элементов.Множество всех многочленов от x над K обозначается K[x].Выражение ai xi называется одночленом. Если ai 6= 0, то одночлен называетсяненулевым одночленом степени i. В записи многочлена нулевые одночлены можноопускать. Многочлен, все коэффициенты которого являются нулями, называется нулевым.Если an 6= 0 и ak = 0 при k > n, то n называется степенью многочлена a(x).Обозначение: n = deg a(x).
Коэффициент an называется старшим коэффициентоммногочлена. Коэффициент a0 называется свободным членом многочлена. Степеньнулевого многочлена считается неопределенной. Нулевой многочлен и многочленынулевой степени естественно ассоциируются с элементами кольца K и называютсяконстантами.Равенство многочленов определяется именно как равенство формальных выражений. Еслиb(x) = b0 + b1 x + b2 x2 + .
. . .то мы пишем a(x) = b(x) в том и только том случае, когда ai = bi при вcех i.Взяв θ ∈ K, мы можем найти значение многочлена a(x) в точке θ, получаемоепри замене x на θ:a(θ) := a0 + a1 θ + . . . + an θn ∈ K.Если f (θ) = 0, то θ называется корнем или нулем многочлена f (x).Мы имеем право рассматривать многочлен f (x) также как функцию f (θ), определенную при всех θ ∈ K. Если многочлены равны как формальные выражения, тосоответствующие им функции будут принимать одинаковые значения при одних итех же значениях аргумента. Обратное неверно, если кольцо K конечно.
Вот примерравных функций, определяемых разными многочленами f (x), g(x) ∈ Z2 [x]:f (x) = 1,g(x) = 1 + x + x2 .Многочлены можно складывать и умножать. Суммой многочленов a(x) и b(x)называется многочлен c(x) с коэффициентамиci := ai + bi ,i = 0, 1, . . . .Обозначение: c(x) = a(x) + b(x).30Произведением многочленов a(x) и b(x) называется многочлен d(x) с коэффициентамиdi := a0 bi + a1 bi−1 + . . . + ai b0 , i = 0, 1, .
. . .Обозначение: d(x) = a(x)b(x).Утверждение 2.3.1 В случае произвольного кольца K степень произведения двухмногочленов не выше суммы их степеней. Если старшие коэффициенты не являются делителями нуля, то степень произведения равна сумме степеней. То жеверно, если K – кольцо с единицей и хотя бы один из старших коэффициентов двухмногочленов является обратимым.Доказательство. Пусть m = deg a(x) и n = deg b(x). Тогда при i = k + l > m + nимеем k > m или l > n, поэтому ak = 0 или bl = 0 и в любом случае ak bl = 0.Таким образом, di = 0 при i > m + n. Заметим также, что dm+n = am bn . В случаеобратимости am или bn имеем dm+n 6= 0. 2Утверждение 2.3.2 Множество многочленов K[x] с операциями сложения и умножения многочленов образует кольцо.
Кольцо K[x] наследует от K такие свойства,как ассоциативность, коммутативность, наличие единицы и отсутствие делителей нуля. Если K – поле, то K[x] является целостным кольцом с единицей.Доказательство является рутинным упражнением. Отметим лишь причину отсутствия делителей нуля: если в K их нет, тоdeg (a(x)b(x)) = deg a(x) + deg b(x),поэтому нулевой многочлен не может получиться при умножении ненулевых многочленов.Задача 72. Найдите число различных многочленов степени 10 над Z2 . Сколько изних различны как функции, определенные на Z2 ?2.4Деление с остатком и алгоритм ЕвклидаВсюду далее считаем, что K – целостное кольцо с единицей 1.Пусть a(x), b(x) ∈ K[x] и b(x) 6= 0.
Говорят, что многочлен a(x) делится с остатком на многочлен b(x) 6= 0, если для некоторых многочленов q(x), r(x) ∈ K[x] выполняется равенствоa(x) = q(x)b(x) + r(x),r(x) = 0 либо deg r(x) ≤ deg b(x) − 1.Многочлены r(x) и q(x) называются соответственно остатком и неполным частным.Теорема 2.4.1 Пусть K – целостное кольцо с единицей и старший коэффициентмногочлена b(x) над K является обратимым. Тогда для любого многочлена a(x) надK деление с остатком на b(x) выполнимо и остаток и неполное частное определеныоднозначно.31Доказательство. При обратимости старшего коэффициента для b(x) деление состатком реализуется по известному со школы методу деления столбиком. Допустим, что получились два разных представленияa(x) = q1 (x)b(x) + r1 (x),deg r1 (x) ≤ deg b(x) − 1,a(x) = q2 (x)b(x) + r2 (x),deg r2 (x) ≤ deg b(x) − 1.Вычитая второе из первого, находим(q2 (x) − q1 (x))b(x) = r1 (x) − r2 (x).Если q1 (x) 6= q2 (x), то это невозможно, так как степень многочлена слева не меньшестепени многочлена b(x), а степень многочлена справа строго меньше этой степени.2Теорема 2.4.2 (теорема Безу) Остаток при делении многочлена f (x) ∈ K[x] надвучлен x − θ, θ ∈ K, есть многочлен-константа f (θ).Доказательство.
Старший коэффициент двучлена является обратимым, поэтомуделение с остатком выполнимо:f (x) = q(x)(x − θ) + r(x)⇒f (θ) = q(θ)(θ − θ) + r(θ) = r(θ).2Следствие 2.4.1 Если θ ∈ K есть корень многочлена f (x) ∈ K[x], то существуетмногочлен q(x) ∈ K[x] такой, что f (x) = q(x)(x − θ).Следствие 2.4.2 Многочлен степени n не может иметь более n различных корней.Следствие 2.4.3 Пусть K – бесконечное целостное кольцо с единицей. Тогда многочлены a(x) и b(x) равны как функции от x ∈ K в том и только том случае, когдаони имеют одинаковые коэффициенты при одинаковых степенях переменной x.Доказательство. Если многочлен c(x) := a(x) − b(x) не является нулевым и принимает нулевое значение в бесконечном числе точек, то число его различных корнейбольше его степени.
Такой многочлен не может быть ненулевым. 2Пусть при делении a(x) на b(x) остаток равен нулю. Тогда мы говорим, что a(x)делится на b(x), а b(x) делит a(x). Используются два типа обозначений:.a(x) .. b(x) (a делится на b)⇔b(x) | a(x) (b делит a).В этом же случае b(x) называется делителем a(x).Если d(x) | a(x) и d(x) | b(x), то d(x) называется общим делителем многочленовa(x) и b(x).
Делитель называется нетривиальным, если он сам и соответствующееему частное не являются делителями единицы.32Заметим, что в случае кольца многочленов над полем делителем единицы является любая ненулевая константа. Если K = Z, то делителей единицы два: 1 и -1.Наибольшим общим делителем многочленов a(x) и b(x) называется такой общий делитель, который делится на любой общий делитель этих многочленов.
Запись(a(x), b(x)) = d(x) означает, что d(x) является наибольшим общим делителем дляa(x) и b(x).Утверждение 2.4.1 Наибольший общий делитель в кольце многочленов над целостным кольцом с единицей определяется однозначно с точностью до умноженияна делитель единицы.Доказательство. Если d1 (x) и d2 (x) оба являются наибольшим делителем для однойпары многочленов над кольцом K, то d1 (x) | d2 (x) и d2 (x) | d1 (x), т.е. имеют месторазложенияd2 (x) = d1 (x)q1 (x), d1 (x) = d2 (x)q2 (x).Отсюда deg d1 (x) ≤ deg d2 (x) и deg d2 (x) ≤ deg d1 (x). Значит, deg d1 (x) = deg d2 (x)и поэтому deg q1 (x) = deg q2 (x) = 0. Таким образом, q1 и q2 являются константами. Пусть a – старший коэффициент многочлена d2 (x). Благодаря тому, что в Kделителей нуля нет, находимa = a(q1 q2 )⇒a(1 − q1 q2 ) = 0⇒q1 q2 = 1.2Многочлены a(x) и b(x) называются взаимно простыми, если любой их общийделитель является делителем единицы.
В этом и только этом случае (a(x), b(x)) = 1.Теорема 2.4.3 (алгоритм Евклида) Пусть K – поле и заданы отличные отконстант многочлены a(x), b(x) ∈ K[x]. Положимr0 (x) := a(x),r1 (x) := b(x)и рассмотрим следующую последовательность делений с остатком:r0 (x) = q2 (x)r1 (x) + r2 (x),r1 (x) = q3 (x)r2 (x) + r3 (x),...rk−2 (x) = qk (x)rk−1 (x) + rk (x),rk−1 (x) = qk+1 (x)rk (x).deg r2 (x) < deg r1 (x),deg r3 (x) < deg r2 (x),deg rk (x) < deg rk−1 (x),Такая последовательность всегда существует, а последний ненулевой остаток rk (x)является наибольшим общим делителем многочленов a(x) и b(x).Доказательство. Степени остатков не могут понижаться бесконечное число раз.Значит, существует последний ненулевой остаток. Пусть это rk (x).
Из последнегосоотношения ясно, что rk (x) | rk−1 (x). Из предпоследнего находим rk (x) | rk−2 (x).33Просматривая соотношения снизу вверх, приходим к выводу о том, что rk (x) является общим делителем для r( x) и r1 (x). Далее, пусть d(x) – произвольный общий.делителей многочленов r0 (x) и r1 (x). Из первого соотношения видим, что r2 (x) .. d(x)..Просматривая соотношения сверху вниз, получаем rk (x) .. d(x). 2Следствие 2.4.4 (теорема о наибольшем общем делителе) Для отличныхот констант многочленов a(x) и b(x) над полем K и их наибольшего общего делителя d(x) ∈ K[x] существуют многочлены u(x), v(x) ∈ K[x] такие, чтоa(x)u(x) + b(x)v(x) = d(x),deg u(x) < deg b(x),deg v(x) < deg a(x).Доказательство. Рассмотрим первое соотношение алгоритма Евклидаr0 = q2 r1 + r2и запишем его в матричном виде: r10 1r0=.r21 −q2 r1Аналогично, при всех 2 ≤ i ≤ k находим ri−10 1ri−2fi gi r0==,ri1 −qi ri−1ui vi r1где 0 1010 1f i gi:=....ui vi1 −qi 1 −qi−11 −q2В итоге находим rk−1fk gk r0=rkuk vk r1⇒rk = uk r0 + vk r1 .Таким образом,a(x)u(x) + b(x)v(x) = rk (x) при u(x) := uk (x), v(x) := vk (x).Кроме того, при всех 3 ≤ i ≤ k fi gi0 1fi−1 gi−1=,ui vi1 −qi ui−1 vi−1откудаdeg ui = deg qi + deg ui−1 ,deg vi = deg qi + deg vi−1 .Заметив, что deg u2 = 0 и deg v2 = deg q1 , получаемdeg uk = deg q3 + deg q4 + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
