Теория остатков (стр. 5 из 10)
· Каждое евклидово кольцо 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 различны и взяты из полной системы вычетов.
Поскольку все числа из данного класса эквивалентности получаются из одного числа данного класса прибавлением числа, кратного m , то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m .
Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ( m ) штук вычетов, где ( m )– функция Эйлера – число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.
Пример. Пусть m = 42. Тогда приведенная система вычетов суть:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) Любые ( m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .
2) Если ( a,m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то аx так же пробегает приведенную систему вычетов по модулю m .
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ( m ) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 (ax.m)=1 . Значит, числа аx образуют приведенную систему вычетов.