Теория остатков
b
1
![]()
b / r 1
b
![]()
r 1
1
![]()
r 1 / r 2
r 1
![]()
r 2
1
![]()
r 2 / r 3
r n -2
![]()
r n -1
1
![]()
r n -1 / r n
r n -1
![]()
r n
Значит:

где q 1 , q 2 ,..., q n +1 - как раз те самые неполные частные из алгоритма Евклида (вот откуда название этих чисел в цепных дробях). Таким образом, в случае рационального числа a / b , процесс разложения в цепную дробь конечен и дробь содержит не более b этажей. Наиболее одаренные читатели в этом месте уже поняли, что основная теорема о цепных дробях для рациональных чисел оказалась почти доказана (не доказали только единственность разложения, но она в случае конечных цепных дробей почти очевидна - приравняйте две цепных дроби и, рассуждая по индукции, получите, что у равных дробей совпадают все неполные частные).
Пример. Пример заимствован из книги И. М. Виноградова "Основы теории чисел". Итак: разложить 105/38 в цепную дробь.
Включаем алгоритм Евклида:
105 = 38 · 2 + 29
38 = 29 · 1 + 9
29 = 9 · 3 + 2
9 = 2 · 4 + 1
2 = 1 · 2
Неполные частные я специально подчеркнул потому, что теперь для написания ответа нужно аккуратно расположить их подряд на этажах цепной дроби перед знаками плюс:

2 Делимость в кольцах
2.1 Область целостности
Область целостности (или целостное кольцо, или область цельности) — понятие абстрактной алгебры: ассоциативное коммутативное кольцо с единицей, в котором 0≠1 и произведение двух ненулевых элементов не равно нулю. Условие 0≠1 исключает из рассмотрения тривиальное кольцо {0}.
Эквивалентное определение: область целостности — это ассоциативное коммутативное кольцо, в котором нулевой идеал {0} является простым. Любая область целостности является подкольцом своего поля частных.
Примеры
Простейший пример области целостности — кольцо целых чисел .
Любое поле является областью целостности. С другой стороны, любая артинова область целостности есть поле. В частности, все конечные области целостности суть конечные поля.
Кольцо многочленов с коэффициентами из некоторого целостного кольца также является целостным. Например, целостными будут кольцо многочленов одной переменной с целочисленными коэффициентами и кольцо многочленов двух переменных с вещественными коэффициентами.
Множество действительных чисел вида есть подкольцо поля , а значит, и область целостности. То же самое можно сказать про множество комплексных чисел вида a + bi, где a и b целые (множество Гауссовых целых).
Пусть U — связное открытое подмножество комплексной плоскости . Тогда кольцо H(U) всех голоморфных функций будет целостным. То же самое верно для любого кольца аналитических функций, определённых на связном подмножестве аналитического многообразия.
Если K — коммутативное кольцо, а I — идеал в K, то факторкольцо K / I целостное тогда и только тогда, когда I — простой идеал.
Делимость, простые и неприводимые элементы
Пусть a и b — элементы целостного кольца K. Говорят, что «a делит b» или «a — делитель b» (и пишут ), если и только если существует элемент такой, что ax = b.
Делимость транзитивна: если a делит b и b делит c, то a делит c. Если a делит b и c, то a делит также их сумму b + c и разность b - c.
Для кольца K с единицей элементы , которые делят 1, называются делителями единицы, а иногда и просто единицами. Они и только они, обратимы в K. Единицы делят все остальные элементы кольца.
Элементы a и b называются ассоциированными, если a делит b и b делит a. a и b ассоциированны тогда и только тогда, когда a = b * e, где e — обратимый элемент.
Необратимый элемент q целостного кольца называется неприводимым, если его нельзя разложить в произведение двух необратимых элементов.
Ненулевой необратимый элемент p называется простым, если из того, что , следует или . Это определение обобщает понятие простого числа в кольце , однако учитывает и отрицательные простые числа. Если p — простой элемент кольца, то порождаемый им главный идеал (p) будет простым. Любой простой элемент неприводим, но обратное верно не во всех областях целостности.
Свойства
Любое поле, а также любое кольцо с единицей, содержащееся в некотором поле, является областью целостности.
Обратно, любая область целостности может быть вложена в некоторое поле. Такое вложение дает конструкция поля частных.
Если A ― область целостности, то кольцо многочленов и кольцо формальных степенных рядов над A также будут областями целостности.
Если A ― коммутативное кольцо с единицей и I ― некоторый идеал в A, то кольцо A / I является областью целостности тогда и только тогда, когда идеал I прост.
Кольцо будет областью целостности тогда и только тогда, когда его спектр есть неприводимое топологическое пространство.
Прямое произведение колец никогда не бывает областью целостности, так как единица первого кольца, умноженная на единицу второго кольца, даст 0.
Тензорное произведение целостных колец тоже будет целостным кольцом.
Вариации и обобщения
Иногда в определении области целостности не требуют коммутативности. Примерами некоммутативных областей целостности являются тела, а также подкольца тел, содержащие единицу, например целые кватернионы. Однако, вообще говоря, неверно, что любая некоммутативная область целостности может быть вложена в некоторое тело.
2.2 Кольцо частных
В коммутативной алгебре кольцом частных S-1R кольца R (коммутативного с единицей) по мультипликативной системе называется пространство дробей с числителями из R и знаменателями из S с арифметическими операциями и отождествлениями, обычными для дробей.
Мультипликативной системой в кольце R называется подмножество S в R, содержащее 1, не содержащее нуля и замкнутое по умножению (в кольце R). Для мультипликативной системы S множество образует идеал в кольце R. В случае, когда множество S не содержит делителей нуля кольца R, идеал IS = (0) и система S называется регулярной. Если R - целостное кольцо, в ней всякая мультипликативная система регулярна.
Элементами кольца частных кольца R по мультипликативной системе S являются формальные дроби вида r/s, где r - произвольный элемент R, а s - элемент множества S. Две дроби r1 / s1 и r2 / s2 считаются эквивалентными (представляют один и тот же элемент кольца частных), если . Операции сложения и умножения определяются как обычно:
Проверяется, что если в сумме или произведении дроби заменить на эвивалентные, новый результат будет выражаться дробью, эквивалентной прежней. С такими операциями множество S − 1R приобретает структуру коммутативного кольца с единицей. Нулём в нём служит дробь 0/1, единицей - дробь 1/1.
Свойства
Кольцо частных имеет каноническую структуру алгебры над кольцом R, так как вместе с кольцом S-1R сразу определён и канонический гомоморфизм кольца R в S-1R (каждому элементу r из R соответствует дробь r/1). Ядром этого гомоморфизма является идеал IS. В случае, если система S регулярна (не содержит делителей нуля), этот гомоморфизм инъективен, и кольцо R, таким образом, вложено в своё кольцо частных по системе S. При этом дробь r/s является единственным решением уравнения sx = r.
Если оба элемента r и s принадлежат S, тогда в кольце S-1R содержатся дроби r/s и s/r. Их произведение равно 1, следовательно, они обратимы. Обратно: каждый обратимый элемент кольца S-1R имеет вид er/s, где r и s принадлежат S, а e - обратимый элемент кольца R.
Если кольцо R не имеет (собственных) делителей нуля (т.е. это целостное кольцо), множество всех ненулевых элементов образует мультипликативную систему S. Соответствующее кольцо частных будет полем, которое называется полем частных целостного кольца. Отсюда следует, что каждое целостное кольцо вложено в некоторое поле, а именно - в своё поле частных.
Если R - евклидово кольцо, то всякое кольцо, промежуточное между R и его полем частных, является кольцом частных кольца R по некоторой мультипликативной системе S.
Если система S состоит из одних только обратимых элементов кольца R, канонический гомоморфизм кольца R в S-1R превращается в изоморфизм, так как каждая дробь r/s оказывается сократимой в кольце R.
Если кольцо R' является подкольцом кольца R, то множество всех элементов из R', обратимых в кольце R, образует регулярную мультипликативную систему S в кольце R'. Тогда каждой дроби r/s однозначно соответствует некоторый элемент кольца R. Множество всех таких элементов кольца R образует кольцо частных кольца R' в кольце R.
Примеры
Полем частных кольца целых чисел является поле рациональных чисел .
Степени числа 10 в образуют мультипликативную систему. Кольцом частных по ней будет кольцо конечных десятичных дробей.
Полем частных кольца многочленов k[X1,X2,...,Xn] над полем k будет поле рациональных функций k(X1,X2,...,Xn).
Пусть — простой идеал в R. Тогда дополнение к нему - мультипликативная система. Кольцо частных по ней называется локализацией кольца R по простому идеалу .
Чётные числа в образуют простой идеал. Локализацией кольца по нему будет кольцо рациональных дробей, у которых в несократимом виде знаменатель — нечётное число.
2.3 Евклидовы кольца
Неформально, евклидово кольцо — в абстрактной алгебре — кольцо, в котором «работает» алгоритм Евклида.
Евклидово кольцо — это область целостности R, для которой определена евклидова функция (евклидова норма) , причём , и возможно деление с остатком, по норме меньшим делителя, то есть для любых имеется представление a = bq + r, для которого d(r) < d(b).
Замечание
Часто на евклидову норму накладывают дополнительное ограничение: для любых a и ненулевых b из кольца R. Если на R задана норма, не удовлетворяющая этому условию, её можно поправить, переопределив:
Такая норма нужному неравенству удовлетворяет, однако прежний алгоритм деления с остатком уже не годится — его тоже надо поправлять. Пусть таков, что d'(b) = d(bx). Разделим с остатком ax на bx: ax = bxq' + r'x, где r' = a − bq' и d(r'x) < d(bx) = d'(b). Так как из определения , мы получили представление a = bq' + r' с d'(r') < d'(b), что и требовалось.
Тем не менее бонусов от такой нормы не так много — все обратимые элементы имеют одно и то же значение нормы, причём минимальное из всех (конечных), собственные делители элемента a имеют меньшее значение нормы, а также упрощается непосредственное доказательство факториальности евклидовых колец (без ссылки на факториальность колец главных идеалов, доказательство чего требует применения трансфинитной индукции). Основные же свойства евклидовых колец остаются в силе и без этого дополнительного свойства.
Примеры
Кольцо целых чисел Z. Пример евклидовой функции — абсолютное значение .
Кольцо целых гауссовых чисел Z[i] (где i — мнимая единица, i2 = − 1) с нормой d(a + ib) = a2 + b2 — евклидово.
Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.
Кольцо многочленов в одной переменной K[x] над полем K. Пример евклидовой функции — степень deg.
Кольцо формальных степенных рядов K[[x]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).
Обобщая предыдущий пример, всякое локальное кольцо является евклидовым, если в нём максимальный идеал является главным и пересечение всех его степеней состоит только из нуля. Норма обратимого элемента — 0, необратимого ненулевого — равна максимальной степени максимального идеала, которая содержит данный элемент, а норма нуля — минус бесконечность.
Кольцо функций H(K), голоморфных на связном компакте K в C (каждая из них должна быть голоморфна в какой-нибудь окрестности этого компакта; две такие функции считаются равными в H(K), если они совпадают в некоторой окрестности K), тоже евклидово. За норму ненулевой функции принимается число нулей (с учётом кратности), которые она принимает на K.
Счётное пересечение евклидовых колец (подколец в каком-нибудь кольце) не обязано быть евклидовым кольцом (и даже нётеровым или факториальным). Например, кольцо функций H(D), голоморфных в открытом круге D, является пересечением евклидовых колец функций H(K), голоморфных на замкнутых кругах K, содержащихся внутри D (см. предыдущий пример), однако оно ни нётерово, ни факториально, соответственно, и неевклидово.
Кольцо частных S-1R евклидова кольца R по мультипликативной системе S тоже является евклидовым. Нормой дроби x из S-1R принимается
, где dR — евклидова норма в R, а dS — норма в S-1R.
Деление с остатком определяется так. Пусть есть две ненулевые дроби x = r / t и y из S-1R. По определению нормы в S-1R существует элементы u в R и s в S, такие что y = u / s и dS(y) = dR(u). Произведём деление с остатком в кольце R элементов rs и u:
rs = uq + r', так что dR(r') < dR(u). Тогда r / t = (u / s)(q / t) + r' / ts. Из построения следуют неравенства .
Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z.
Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C[x].
Алгоритм Евклида
В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента a0 и a1, причём и . Деление с остатком даёт элемент a2 = a0 − a1q1 с d(a2) < d(a1). Если он не равен нулю, можно опять применить деление с остатком, и получить элемент a3 = a1 − a2q2, и т. д. Таким образом генерируется цепочка значений с . Однако эта цепочка прерывается, поскольку всякое число из может строго превосходить лишь конечное количество других таких чисел. Это означает, что при некотором n остаток an+1 равен нулю, а an не равен, он и есть НОД элементов a0 и a1. Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.
Свойства евклидовых колец
В евклидовом кольце каждый идеал — главный (в частности, все евклидовы кольца нётеровы).
Пусть I — произвольный идеал в евклидовом кольце. Если он содержит лишь 0, — он главный. В противном случае среди его ненулевых элементов найдётся элемент f с минимальной нормой (принцип минимума для натуральных чисел). Он делит все остальные элементы идеала: Если g — произвольный элемент идеала I, представим его в виде g = fq + r с d(r)<d(f). Тогда r - тоже элемент идеала I и он обязан быть нулём, так как его норма меньше, чем у f. Следовательно, идеал I содержится в идеале (f). С другой стороны, всякий идеал, содержащий элемент f, содержит идеал (f). Значит, I = (f) - главный идеал.
Каждое евклидово кольцо факториально, то есть каждый элемент представим конечным произведением простых элементов, и притом однозначно (с точностью до их перестановки и умножения на обратимые элементы). Факториальность - общее свойство всех колец главных идеалов.
Каждое евклидово кольцо R целозамкнуто, то есть если дробь , является корнем многочлена со старшим коэффициентом, равным 1, тогда a делится на b. Целозамкнутость - общее свойство всех факториальных колец.
Свойства модулей над евклидовым кольцом
Пусть R - евклидово кольцо. Тогда конечнопорождённые R-модули обладают следующими свойствами:
Всякий подмодуль N конечнопорождённого R-модуля M конечно порождён. (следствие нётеровости кольца R)
Ранг подмодуля N не превосходит ранга модуля M. (следствие главности идеалов в R)
Подмодуль свободного R-модуля свободен. (то же)
Гомоморфизм конечнопорождённых R-модулей всегда приводится к нормальной форме. То есть существуют образующие (базис, если модуль свободен) модуля N, образующие (базис) модуля M, номер и - элементы кольца R, такие что ai делит ai + 1 и при i>k Aui = 0, а при остальных — Aui = aivi. При этом коэффициенты определены однозначно с точностью до умножения на обратимые элементы кольца R. (Тут прямо задействована евклидовость кольца R.)
3 Сравнения и арифметика остатков
Определение. Пусть а, b Z , m N . Говорят, что число а сравнимо с b по модулю m , если а и b при делении на m дают одинаковые остатки. Запись этого факта выглядит так:
a b(mod m) .
Очевидно, что бинарное отношение сравнимости m (неважно, по какому модулю) есть отношение эквивалентности на множестве целых чисел, а любители алгебры скажут, что это отношение является даже конгруэнцией кольца Z , фактор-кольцо по которой Z/ m называется кольцом вычетов и обозначается Z m .
Ясно, что число a сравнимо с b по модулю m тогда и только тогда, когда a-b делится на m нацело. Очевидно, это, в свою очередь, бывает тогда и только тогда, когда найдется такое целое число t , что a=b+mt . Знатоки алгебры добавят к этим эквивалентным утверждениям, что сравнимость a с b по модулю m означает, что a и b представляют один и тот же элемент в кольце Z m .
Свойство 1. Сравнения по одинаковому модулю можно почленно складывать.
Доказательство. Пусть a1b1(mod m), a2b2(mod m). Это означает, что a 1 =b 1 +mt 1 , a 2 =b 2 +mt 2 . После сложения последних двух равенств получим a 1 +a 2 =b 1 +b 2 +m(t 1 +t 2 ) , что означает a 1 +a 2 b 1 +b 2 (mod m).
Свойство 2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный.
Доказательство.

Свойство 3. К любой части сравнения можно прибавить любое число, кратное модулю.
Доказательство.

Свойство 4. Сравнения по одинаковому модулю можно почленно перемножать и, следовательно,
Свойство 5. Обе части сравнения можно возвести в одну и ту же степень.
Доказательство.

Как следствие из вышеперечисленных свойств, получаем
Свойство 6. Если
a 0 b 0 (mod m) , a 1 b 1 (mod m) ,..., a n b n (mod m) , x y(mod m) ,
то a 0 x n +a 1 x n-1 +...+a n b 0 y n +b 1 y n-1 +...+b n (mod m)
Свойство 7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.
Доказательство. Пусть a b(mod m) , a=a 1 d , b=b 1 d . Тогда (a 1 -b 1 ) d делится на m . Поскольку d и m взаимно просты, то на m делится именно (a 1 -b 1 ) , что означает a 1 b 1 (mod m) .
Свойство 8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.
Доказательство.
a b(mod m) a=b+mt ak=bk+mkt ak bk(mod mk) .
Свойство 9. Если сравнение a b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
Доказательство. Если a b(mod m 1 ) и a b(mod m 2 ) , то a-b делится на m 1 и на m 2 , значит a-b делится на наименьшее общее кратное m 1 и m 2 .
Свойство 10. Если сравнение имеет место по модулю m , то оно имеет место и по модулю d , равному любому делителю числа m .
Доказательство очевидно следует из транзитивности отношения делимости: если a b(mod m) , то a-b делится на m , значит a-b делится на d , где d|m .
Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.
Доказательство.
a b(mod m) a=b+mt .
Отношение m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности m (знатоки скажут - "индекс эквивалентности m ") в точности равно m .
Определение. Любое число из класса эквивалентности m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет называется абсолютно наименьшим, если наименьший среди модулей вычетов данного класса.
Пример : Пусть m = 5 . Тогда:
0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;
-2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.
Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5 .
Лемма 1. 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .
2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы аx+b , где b - любое целое число, тоже пробегают полную систему вычетов по модулю m .
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Чисел аx+b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 +b ax 2 +b(mod m) . Тогда, по свойствам сравнений из предыдущего пункта, получаем:
ax 1 ax 2 (mod m)
x 1 x 2 (mod m)
– противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.
Поскольку все числа