Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

Для любых элементов a, b, q евклидовакольца выполнено (a, b) = (a − qb, b).Доказательство. Пусть d — общий делитель a и b, т. е.a = a′ d, b = b′ d. Тогда a − qb = a′ d − qb′ d = (a′ − qb′ )d, такчто d является общим делителем a − qb и b. И наоборот, еслиa−qb = cd, b = b′ d, то a = qb+cd = (qb′ +c)d. Значит, множествообщих делителей для пар a, b и a − qb, b одинаково.108Глава 2.КольцаУтверждение 2.38. Решениями однородного линейного уравнения с двумя переменными ax + by = 0 с коэффициентамииз евклидова кольца R (a и b не равны одновременно нулю)являютсяbax = t , y = −t , d = (a, b), t ∈ R.ddДоказательство. Разделив обе части уравнения на наибольший общий делитель (a, b), получим равносильное уравнение,коэффициенты которого взаимно просты. Поэтому достаточнорешить уравнение ax + by = 0 со взаимно простыми коэффициентами.Если (a, b) = 1, то по теореме 2.28 для некоторых u, v ∈ Rвыполнено au + bv = 1. Умножим равенство ax + by = 0 на u:u(ax + by) = ua + uby = (1 − bv)x + uby = x + b(by − vx) = 0.Таким образом, x = tb при некотором t ∈ R.

Но тогда by == −ax = −tab и y = −ta. С другой стороны, любая пара(tb, −ta) является решением уравнения ax + by = 0.Расширенный алгоритм Евклида работает следующим образом. Вначале вычисляется последовательность остатков(собственно алгоритм Евклида):ai = qi+1 ai+1 + ai+2 ,a0 = a, a1 = b,пока ai+2 6= 0. Последние числа в этой последовательностиat = qt+1 at+1 , at+1 , причем at+1 = (a0 , a1 ) = (a, b).Почему алгоритм Евклида работает конечное число шагови дает правильный ответ? Нормы элементов ai уменьшаютсяпри i > 1, поскольку каждый следующий элемент являетсяостатком от деления на предыдущий. Значит, после конечногочисла шагов остаток станет нулю.

Корректность ответа следует из утверждения 2.37:(a0 , a1 ) = (a1 , a2 ) = · · · = (at , at+1 ) = at+1 .Вторая часть алгоритма (расширенный алгоритм Евклида) строит последовательность пар xi , yi , начиная с xt = −1,yt = qt+1 + 1 по следующим рекуррентным формуламxi = yi+1 ,yi = xi+1 − qi+1 yi+1 .2.8.109Основная теорема арифметикиПо индукции проверяется, чтоxi ai + yi ai+1 = (a0 , a1 ).(2.9)Это верно при i = t, так какxt at + yt at+1 = −qt+1 at+1 + (qt+1 + 1)at+1 = at+1 = (a0 , a1 ).Если (2.9) верно при i + 1, то оно верно и при i:xi ai + yi ai+1 = yi+1 ai + (xi+1 − qi+1 yi+1 )ai+1 == yi+1 (qi+1 ai+1 + ai+2 ) + (xi+1 − qi+1 yi+1 )ai+1 == xi+1 ai+1 + yi+1 ai+2 = (a0 , a1 ).Пара (x0 , y0 ), полученная в результате работы второй части алгоритма, будет решением уравнения ax + by = (a, b).Остальные решения отличаются от этого на решение однородного уравнения, так как если ax0 + by0 = (a, b) и ax + by == (a, b), то (ax + by) − (ax0 + by0 ) = a(x − x0 ) + b(y − y0 ) = 0.Поэтому общее решение линейного неоднородного уравненияимеет видbax = x0 + t , y = y0 − tddd = (a, b), t ∈ R.2.8.

Основная теорема арифметикиОдним из следствий теоремы 2.36 является то, что в кольцеклассов вычетов по модулю (p), где (p) — простой идеал, нетделителей нуля (выше было доказано, что их нет в любом теле). Из этого факта получается важное усиление теоремы 2.35.Теорема 2.39. Каждый элемент евклидова кольца однозначно разлагается в произведение простых элементов с точностью до делителей единицы. Это означает, что если естьдва разложения в произведение простыхa = εp1 p2 . .

. pn = δq1 q2 . . . qm(ε, δ — делители единицы), то n = m и существует такаяперестановка индексов σ, что pi = εi qσ(i) , где εi — делителиединицы.110Глава 2.КольцаДоказательство. Индукция по длине кратчайшего разложения в произведение простых.База индукции: n = 0, делители единицы. Пусть делитель единицы ε является произведением простых элементовq1 q2 . . .

qm . Тогда q1 — делитель единицы, так как ε−1 q2 . . . qmявляется обратным к q1 . Но это противоречит определениюпростоты. Значит, m = 0.Пусть утверждение теоремы выполнено для всех элементовкольца, которые разлагаются в произведение не более чем nпростых. Рассмотрим два разложения на простые:εp1 p2 . . . pn pn+1 = δq1 q2 .

. . qm ,m > n.Поскольку в кольце вычетов по модулю (pn+1 ) нет делителейнуля, один из сомножителей в правой части должен делиться на pn+1 . С точностью до перенумерации элементов можносчитать, что это — qm . Из простоты pn+1 , qm вытекает, чтоpn+1 = εn+1 qm . Значит,εεn+1 p1 p2 . . . pn = δq1 q2 .

. . qm−1 .Осталось применить предположение индукции к этим разложениям.Кольцо целых чисел Z евклидово (см. пример 2.24). Делителями единицы в этом кольце являются ±1. Поэтому из теоремы 2.39 вытекает следствие, известное как основная теорема арифметики: всякое положительное целое число разлагается в произведение простых чисел однозначно с точностью до перестановки множителей.Замечание 2.40. Кольца, в которых любой элемент однозначно в смысле теоремы 2.39 разлагается на простые множители, называются факториальными.

Теорема 2.39 утверждает,что все евклидовы кольца факториальны. Обратное неверно.Можно, например, доказать, что кольцо многочленов от двухпеременных Q[x, y] является факториальным. Но это кольцо не является евклидовым, потому что не является кольцомглавных идеалов. Многочлены, у которых свободный член равен 0, образуют в этом кольце идеал и легко проверить, чтоэтот идеал не является главным.2.9.111Китайская теорема об остатках2.9. Китайская теорема об остаткахВ этом разделе мы приведем еще одно важное следствиеобщей теории евклидовых колец.Теорема 2.41. Для взаимно простых элементов p1 , p2 евклидова кольца R имеет место изоморфизм колец R/(p1 p2 ) ∼=R/(p1 ) ⊕ R/(p2 ).Доказательство. Рассмотрим гомоморфизмϕ : R → R/(p1 ) ⊕ R/(p2 ),ϕ : r 7→ ({r}1 , {r}2 ),где {r}i обозначает класс вычетов по модулю pi .Теорема 2.28 утверждает, что в кольце найдутся такие элементы x1 , x2 , для которых x1 p1 + x2 p2 = (p1 , p2 ) = 1.

Изэтого равенства следует, что p1 является делителем единицыв R/(p2 ), а p2 является делителем единицы в R/(p1 ).Пусть r = y1 p1 = y2 p2 ∈ Ker ϕ. Тогда y1 p1 = y2 p2 = 0̄в R/(p1 ). Поскольку p2 — делитель единицы, то y2 = 0̄, т. е.y2 = ap1 . Значит, r = ap1 p2 . Поэтому ядро гомоморфизма ϕсовпадает с (p1 p2 ).При этом гомоморфизм ϕ сюръективен, так как для любойпары классов вычетов ({r1 }1 , {r2 }2 ) найдется элемент кольцаs = r1 +(r2 −r1 )x1 p1 = r2 −(r2 −r1 )x2 p2 , который отображаетсяв эту пару при гомоморфизме ϕ.Осталось применить теорему о гомоморфизме колец.Теорема 2.41 имеет очевидные следствия для колец вычетов, циклических групп и колец вычетов по модулю идеаловкольца многочленов.Следствие 2.42.

Если p, q — взаимно простые числа, тоZpq ∼= Zp ⊕ Zq .Следствие 2.43. Если p, q — взаимно простые числа, тоCpq ∼= Cp ⊕ Cq .Следствие 2.44. Пусть K — поле. Если многочлены f, g ∈K[x] взаимно просты, то K[x]/(f g) ∼= K[x]/(f ) ⊕ K[x]/(g).Приведем еще один пример использования китайской теоремы об остатках. Функция Эйлера ϕ(n) равна количеству112Глава 2.Кольцанатуральных чисел, меньших n и взаимно простых с n (т. е.количеству обратимых элементов кольца вычетов Zn ).Теорема 2.45. Функция ϕ(n) мультипликативна, т.

е. если(n, m) = 1, то ϕ(nm) = ϕ(n)ϕ(m).Доказательство. Обратимые элементы в кольце Zn ⊕ Zm —это те элементы, у которых в каждой компоненте — обратимыйэлемент. Значит, количество обратимых элементов в кольцеZnm ∼= Zn ⊕Zm равно количеству пар (x, y), где x — обратимыйв Zn , а y — обратимый в Zm .2.10. Задачи2.1.

Выяснить, какие из следующих множеств являются кольцами (но не полями) и какие полями относительноуказанных операций. (Если операции не указаны, то подразумеваются сложение и умножение чисел.)а) целые числа Z;б) четные числа;в) целые числа, кратные данному числу d (рассмотреть вчастности, случай d = 0);г) рациональные числа Q;д) действительные числа R;е) комплексные числа C;√ж) действительные числа вида x + y√ 2, где x, y ∈ Z;з) действительные числа вида x + y 3 2, где x, y ∈ Q;и) комплексные числа вида n + mi, где n, m ∈ Z (гауссовычисла);к) множество комплексных чисел вида x + yi, где x, y ∈ Q;л) матрицы порядка n с целыми элементами относительносложения и умножения матриц;м) матрицы порядка n с действительными элементами относительно сложения и умножения матриц;н) функции с действительными значениями, непрерывныена отрезке [−1, +1] относительно обычных сложения и умножения функций;2.10.113Задачио) многочлены от одного неизвестного x с целыми коэффициентами относительно обычных операций сложения и умножения;п) многочлены от одного неизвестного x с действительными коэффициентами относительнообычных операций;a bр) матрицы видас рациональными или действи2b aтельными a, b относительно сложения и умножения матриц;с) Образуют ли кольцо все тригонометрические полиномыa0 +nXak cos(kx) + bk sin(kx)k=1с действительными коэффициентами?Выяснить то же для поPnлиномоводнихкосинусовa+acos(kx) и одних синусов0kk=1Pna0 + k=1 ak sin(kx).2.2.

Образует ли кольцо относительно обычных операцийсложения и умноженияа) множество рациональных чисел, в несократимой записикоторых знаменатели делят фиксированное натуральное число n ∈ N;б) множество рациональных чисел, в несократимой записикоторых знаменатели не делятся на фиксированное простоечисло p;в) множество рациональных чисел, в несократимой записи которых знаменатели являются степенями фиксированногопростого числа p;√г) числа вида x + y 3 2, где x, y ∈ Q (для определенностиберется действительное значение корня);д) множество комплексных чисел вида a1 z1 + a2 z2 + .

. . ++ an zn , где a1 , a2 , . . . , an — действительные числа, а z1 , z2 ,. . . , zn — комплексные корни n-й степени из 1;√Dе) множество комплексных чисел вида m+in, где D —2фиксированное целое число, свободное от квадратов (не делящееся на квадрат простого числа), n, m — целые числа одинаковой четности.2.3. Образует ли указанное множество матриц кольцо относительно матричного сложения и умножения:114Глава 2.Кольцаа) множество действительных симметрических матриц порядка n;б) множество действительных ортогональных матриц порядка n;в) множество верхних треугольныхматрицпорядка n;m nг) множество матриц вида, где D — фиксироDn mванное целое число, n, m ∈ Z; m nд) множество матриц вида, где D — фиксироDn mванный элемент некоторого кольца K; n, m ∈ K;mn, где D — фиксие) множество матриц вида 12Dn mрованное целое число, свободное от квадратов (не делящеесяна квадрат простого числа), n, m — целые числа одинаковойчетности;zwж) множество комплексных матриц вида;−w̄ z̄з) множество вещественных матриц видаx −y ztyx −t z  .−ztx y−t −z −y x2.4.

Характеристики

Список файлов книги