АГ-1 МП ПЗ 1-27 Теорминимум 1-й семестр

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

ТЕОРМИНИМУМ к ПЗ по курсу «Алгебра и геометрия»

Практическое занятие 1. Решето Эратосфена п.1.1 Понятие делимости целых чисел и его свойства

Множество целых чисел будем обозначать прописной буквой Z, множество натуральных чисел – буквой N. Сами целые числа будем обозначать малыми (строчными) буквами латинского алфавита.

Определение. Говорят, что целое число a 0 делит целое число b (целое число b делится на целое число a 0 ), если существует целое число с, такое, что b ac . Число а называется делителем числа b, а число b называется кратным числа а.

Обозначение: a | b .

Такимобразом, поопределению, длялюбыхдвухцелыхчисел a 0 иb,

df

a | b c Z : b ac .

Замечание. В записи a | b молчаливо будем предполагать, что числа а

и b являются целыми, и число a 0 . Если число а не делит число b, то будем писать a | b .

Теорема. (Свойства делимости целых чисел.) 1) Свойство рефлексивности.

Для любого целого числа a 0 , a | a .

2) Свойство транзитивности.

Если целые числа а, b и с таковы, что a | b и b | c , то a | c .

3)x Z, x 0, ax | bx a | b .

4)Если a | b , то x Z, a | bx .

5) Если a | n и a | m , то x, y Z, a | xn ym

6)Если a | n и b | m , то ab | nm .

7)Если a | b и b | a , то a b .

Следствие.

1)Если a 0 , то a | 0 .

2)Если a | b , то a | ( b) .

1

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

3)Если a | n и a | m , то a | n m .

4)Если a |1, то a 1.

п.1.2 Простые и составные числа

Из определения делимости целых чисел следует, что любое целое число n 1 имеет, по крайней мере, два положительных делителя, это число 1 и само число n.

Определение. Пусть n 1. Числа 1 и n называются тривиальными (несобственными) делителями числа n. Все остальные положительные делители числа n, если они существуют, называются собственными делителями числа n.

Другими словами, если 1 a n и a | n , то число а называется собственным делителем числа n.

Определение. Натуральное число p 1 называется простым числом,

если оно не имеет собственных делителей. В противном случае, целое число p 1 называется составным.

Теорема. (О наименьшем собственном делителе.) Наименьший собственный делитель составного числа является простым числом.

Теорема. (Об оценке наименьшего собственного делителя.) Пусть n 1 – составное число и р – его наименьший собственный делитель. Тогда p2 n .

Другими словами, любое составное число n кратно простому числу p n . На этом свойстве составных чисел основан алгоритм состав-

ления таблиц простых чисел, который называется решетом Эратосфена. Имея, например, под рукой таблицу простых чисел из промежутка от 2 до 100, легко получить каноническое разложение любого натурального числа из промежутка от 2 до 10000.

п.1.3 Решето Эратосфена

Пусть дано целое число n 1.

1-й шаг. Выписываем по возрастанию последовательность всех целых

2

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

чисел от 2 до n. Будем называть эту последовательность целых чисел списком №1:

2, 3, 4, 5, …, n.

2-й шаг. Выписываем по возрастанию последовательность всех простых чисел, начиная с простого числа 2 до простого числа р, для кото-

рого выполняется неравенство p2 n . Будем называть эту последова-

тельность простых чисел списком №2:

2, 3, 5, 7, …, р,

где p2 n , и если q – простое число, которое следует за простым числом р, то q2 n .

3-й шаг. Вычеркнем из списка №1 все числа кратные числу 2, кроме самого числа 2. Далее, вычеркнем из списка №1 все числа кратные числу 3, кроме самого числа 3. Следующее простое число в списке №2 стоит простое число 5. Вычеркнем из списка №1 все числа кратные числу 5, кроме самого числа 5. Продолжаем этот процесс до тех пор, пока не вычеркнем из списка №1 все числа, кратные простым числам из списка №2, кроме них самих.

В результате такого вычеркивания, формируется список №3, состоящий из невычеркнутых из списка №1 чисел.

Теорема. Список №3 состоит из всех простых чисел из промежутка от 2 до n, и только из них.

п.1.4 Основная теорема арифметики Теорема. (Евклид) Простых чисел бесконечно много.

Теорема. (Основная теорема арифметики.) Любое натуральное число, отличное от 1, можно представить в виде произведения простых множителей и притом единственным способом, если не учитывать порядок сомножителей.

Следствие. Любое натуральное число n 1 можно единственным способом записать в виде n p1 1 p2 2 ...pmm , где p1 p2 ... pm – простые числа, 1 , 2 ,..., m N .

разложением числа n в произведение простых множителей.

3

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Практическое занятие 2. Алгоритм Евклида п.2.1 Наибольший общий делитель, алгоритм деления с остатком и алгоритм Евклида

Определение. Пусть а и b два целых числа, одновременно не равных нулю. Наибольшим общим делителем чисел а и b называется натуральное число D, удовлетворяющее следующим двум условиям:

1)D | a и D | b ;

2)если d целое число, такое, что d | a и d | b , то d D .

Обозначение: D D(a,b) н.о.д.(a,b) .

Замечание. НОД большего количества чисел определяется аналогично. Можно доказать, что

D(a1 ,a2 ,...,an ) D(a1 ,D(a2 ,...,an )) .

Справедлива и более общая формула:

D(a1 ,a2 ,...,an ) D(D(a1 ,...,ak ),D(ak 1,...,an )) , k {1,2,...,n 1}.

Теорема. (Свойства НОД)

1)D(a,b) D(b,a)

2)Если a | b , то D(a,b) a .

3)Для любого целого числа n, D(a,b) D(a nb,b) .

Теорема. (Алгоритм деления с остатком.) Для любых целых чисел а, b 0 , существует единственная пара целых чисел (q, r), удовлетворяющих двум условиям:

a bq r и 0 r b .

Определение. В обозначениях предыдущей теоремы, число q называется неполным частным, а r – остатком от деления числа а на число b. Если остаток r 0 , то q называется частным от деления числа а на число b.

Следующая последовательность делений с остатком называется алгоритмом Евклида. Пусть а, b 0 – произвольные целые числа. Выполним деление с остатком числа а на число b:

a bq1 r1 , где 0 r1 b .

4

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Пустьостаток r1 0 . Выполнимделениесостаткомчислаb наостаток r1 :

b r1q2 r2 , где 0 r2 r1 .

Пусть остаток r2 0 . Выполним деление с остатком предыдущего остатка r1 на остаток r2 :

r1 r2q3 r3 , где 0 r3 r2 .

Если остаток r3 0 , то делим r2 на r3 :

r2 r3q4 r4 , где 0 r4 r3 .

Процесс деления не может продолжаться бесконечно, так как после каждого шага остаток уменьшается, но остается при этом целым неотрицательным числом. Следовательно, через конечное число шагов этот процесс заканчивается получением нулевого остатка:

rn 1 rn qn 1 .

Теорема. Наибольший общий делитель двух целых чисел равен последнему ненулевому остатку в алгоритме Евклида, т.е. D(a,b) rn .

п.2.2 Свойство линейной представимости НОД Теорема. (Свойство линейной представимости НОД)

Пусть а, b 0 – произвольные целые числа и D – их наибольший общий делитель. Тогда существуют целые числа х и у, такие, что

D ax by .

Определение. Числа х и у в линейном представлении НОД называются коэффициентами линейного представления.

Теорема. Пусть а, b 0 – произвольные целые числа и D rn – их

наибольший общий делитель, вычисленный с помощью алгоритма Евклида, где rn – последний ненулевой остаток. Пусть q1 ,q2 ,...,qn –

все неполные частные алгоритма Евклида деления числа а на число b. Тогда

D axn bn y ,

числа xn и yn могут быть последовательно вычислены по следую-

щим рекуррентным формулам:

x0 0, x1 1, xk xk 2 xk 1qk ,

5

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

y0 1, y1 q1, yk yk 2 yk 1qk , k 2,3,...,n .

На практике удобно последовательно заполнять клетки следующей таблицы:

п.2.3 Наименьшее общее кратное и его свойства

Определение. Пусть а и b два целых числа, отличных от нуля. Наименьшим общим кратным чисел а и b называется натуральное число K, удовлетворяющее следующим двум условиям:

1)a | K и b | K ;

2)если k целое число, такое, что a | k и b | k , то K k .

Замечание. НОК большего количества чисел определяется аналогично. Можно доказать, что

K(a1 ,a2 ,...,an ) K(a1 ,K(a2 ,...,an )) .

Справедлива и более общая формула:

K(a1 ,a2 ,...,an ) K(K(a1 ,...,ak ),K(ak 1 ,...,an )) , k {1,2,...,n 1}.

Теорема. (Связь НОД и НОК.) Пусть а и b два произвольных натуральных числа. Тогда

ab D(a,b) K(a,b) .

Теорема. (О вынесении общего множителя за знак НОД и НОК.) Общий множитель двух целых чисел можно выносить за знаки их НОД и НОК, т.е. если m ac, n bc , то

D(m,n) D(ac,bc) cD(a,b) ,

K(m,n) K(ac,bc) cK(a,b) .

Определение. Два целых числа называются взаимно простыми, если их наибольший общий делитель равен 1.

6

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Следствие. Наименьшее общее кратное двух взаимно простых натуральных чисел равно их произведению.

п.2.4 Свойства взаимно простых чисел Теорема. (Свойства взаимно простых чисел.)

1)D(a,b) 1 x, y Z : ax by 1 ;

2)d D(a,b) D a , b 1 ;

d d

3)если числа а и b взаимно просты с третьим числом n, то их произведение ab также взаимно просто с числом n:

D(a,n) 1 и D(b,n) 1, то D(ab,n) 1;

4)если число k кратно каждому из взаимно простых чисел а и b, то оно кратно и их произведению:

D(a,b) 1 и a | k, b | k , то ab | k ;

5)если a | bc и D(a,b) 1, то a | c .

Теорема. (Основное свойство простого числа.) Натуральное число р является простым тогда и только тогда, когда из того, что p | ab и

p | a следует, что p | b , где а, b – произвольные целые числа.

Практическое занятие 3. Сравнения по модулю п.3.1 Сравнение по модулю

Определение. Пусть m 1 – произвольное натуральное число, а и b – произвольные целые числа. Число а называется сравнимым с числом b по модулю m, если

m | a b .

Обозначение: a b (mod m) . Таким образом, по определению,

a b (mod m) m | a b .

Замечание. Если число а кратно положительному числу b 1, то этот факт можно описать двумя равносильными способами:

b | a a 0 (mod b) .

7

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Следствие. Равные числа сравнимы друг с другом по любому модулю.

Теорема. (Свойства сравнений.) Сравнение целых чисел по модулю натурального числа m 1 обладает следующими свойствами:

1)свойство рефлексивности: a Z , a a (mod m) ;

2)свойство симметричности: a,b Z ,

если a b (mod m) , то b a (mod m) ; 3) свойство транзитивности: a,b,c Z ,

если a b (mod m) и b c (mod m) , то a c (mod m) .

Следствие. Отношение сравнимости целых чисел по модулю является отношением эквивалентности.

п.3.2 Действия со сравнениями Теорема. Сравнения по одному и тому же модулю можно почленно

складывать, вычитать и умножать, т.е. если a b (mod m) и c d (mod m) , то

a c b d (mod m) и ac bd (mod m) .

Следствие. (Свойства сравнений.)

1)К обеим частям сравнения можно прибавить одно и то же слагае-

мое или сократить его, т.е. для любого целого числа k a b (mod m) a k b k (mod m) .

2)Обе части сравнения можно умножить на одно и то же число, т.е.

для любого целого числа k

a b (mod m) ak bk (mod m) .

3)Любое слагаемое, находящееся в одной части сравнения, можно перенести слагаемым в другую его часть с противоположным зна-

ком, т.е.

a k b (mod m) a b k (mod m) .

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

ab (mod m) an bn (mod m) , где n N .

5)К любой части сравнения можно прибавить слагаемое, кратное модулю или заменить его нулем, т.е. если k 0 (mod m) , то

a b (mod m) a 0 b (mod m) a k b (mod m) .

8

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

6)Любое число, кратное модулю и стоящее множителем в любой части сравнения, можно заменить нулем, т.е. если k 0 (mod m) , то

ab ck (mod m) a b c 0 (mod m) a b (mod m) .

7)Любое число, стоящее слагаемым или множителем в любой части сравнения, можно заменить любым другим числом, с которым оно сравнимо по данному модулю, т.е. если a b (mod m) , то

d a c (mod m) d b c (mod m) , d ak c (mod m) d bk c (mod m) ,

d an k c (mod m) d bn k c (mod m) , где n N .

п.3.3 Сокращения в сравнениях

Теорема. Пусть k и m 1 – произвольные натуральные числа, а и b – произвольные целые числа. Тогда

a b (mod m) ak bk (mod mk) .

Теорема. (Закон сокращения в сравнениях.) Обе части сравнения можно сократить на один и тот же множитель, если он взаимно простой с модулем, т.е. если D(k,m) 1, то

ak bk (mod m) a b (mod m) .

Следствие. Если D(k,m) 1, то a b (mod m) ak bk (mod m) .

п.3.4 Признаки делимости

Теорема. Любое натуральное число n единственным способом можно записать в виде:

n a0 a1 10 a2 102 ... am 10m am am 1...a2a1a0 ,

где

k 0,1,2,...,m : ak {0,1,2,...,9} и am 0 .

Определение. Запись натурального числа в виде n amam 1...a2a1a0 ,

где k 0,1,2,...,m : ak {0,1,2,...,9} и am 0 , называется позицион-

ной формой записи числа в системе счисления с основанием равным 10 или записью числа в десятичной системе счисления, числа ak , k 0,1,2,...,m называются его цифрами.

9

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Замечание. В дальнейшем, как и прежде, при записи целых чисел мы пользуемся только десятичной системой счисления.

Введем для удобства записи следующие обозначения. Пусть

n amam 1...a2a1a0 – произвольное натуральное число. Обозначим че-

рез:

S(n) a0 a1 ... am – сумму цифр числа n; S(n) a0 a1 ... ( 1)m am ;

S3 (n) a2a1a0 a5a4a3 ... am ... , где последнее слагаемое будет равно

amam 1am 2 , если m 2 (mod3) или amam 1 , если m 1(mod3) или am am , если m 0 (mod3) ;

S3 (n) a2a1a0 a5a4a3 ... ( 1)t am ..., где t равно полному или неполному частному от деления числа m на 3.

Теорема. Пусть n amam 1...a2a1a0 . Тогда:

1)n 0 (mod 2) a0 0 (mod 2) ;

2)n 0 (mod3) S(n) 0 (mod3) ;

3)n 0 (mod 4) a1a0 0 (mod 4) ;

4)n 0 (mod5) a0 0 (mod5) ;

5)n 0 (mod7) S3 (n) 0 (mod7)

6)n 0 (mod8) a2a1a0 0 (mod8) ;

7)n 0 (mod9) S(n) 0 (mod9) ;

8)n 0 (mod11) S3 (n) 0 (mod11) S(n) 0 (mod11) ;

9)n 0 (mod13) S3 (n) 0 (mod13) ;

10)n 0 (mod 25) a1a0 0 (mod 25) ;

11)n 0 (mod37) S3 (n) 0 (mod37) .

п.3.5 Классы вычетов Определение. Любое целое число х сравнимое с данным числом а по

данному модулю m называется вычетом числа а по модулю m.

10

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Таким образом, если x a (mod m) , то х – вычет числа а по модулю m.

Определение. Множество всех вычетов числа а по модулю m называ-

ется классом вычетов числа а по модулю m, и обозначается a .

Другими словами, класс вычетов числа а по модулю m a {x Z | x a (mod m)}

является, по определению, множеством состоящим из всех целых чисел сравнимых с числом а по модулю m.

Теорема. Любые два числа из класса вычетов по модулю m сравнимы друг с другом по модулю m, т.е. если b,c a , то b c (mod m) .

Теорема. (О равенстве классов вычетов.) Пусть a и b два класса вычетов по модулю m. Тогда

a b a b (mod m) .

Определение. Наименьшее неотрицательное число, содержащееся в классе вычетов числа а по модулю m называется его наименьшим неотрицательным вычетом.

Теорема. (О наименьшем неотрицательном вычете.) Наименьший неотрицательный вычет числа а по модулю m равен остатку от деления числа а на модуль m, и обозначается ra (mod m) .

Замечание. Если модуль фиксированный, то наименьший неотрицательный вычет числа а по модулю m будем обозначать ra .

Таким образом, из последней теоремы следует, что для любого целого числа а, существует единственный его наименьший неотрицательный вычет ra , следовательно,

a ra (mod m) и a ra .

Теорема. (Свойства классов вычетов.) Пусть m 1 – произвольное фиксированное натуральное число. Тогда

11

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

1)Любые два класса вычетов по модулю m либо совпадают, либо не пересекаются.

2)Каждое целое число попадает в один и только один класс вычетов по модулю m.

3)Существует ровно m классов вычетов по модулю m:

0, 1, ..., m 1 ,

где числа 0,1,...,m 1 являются наименьшими неотрицательными вычетами в своих классах вычетов.

4)Объединение всех классов вычетов по модулю m совпадает с множеством целых чисел:

Z 0 1 ... m 1.

Замечание. Множество всех классов вычетов по модулю m обозначается Zm . Из теоремы следует, что

Zm {0, 1, ..., m 1} .

Теорема. Все числа любого класса вычетов по модулю m образуют бесконечную (в обе стороны) арифметическую прогрессию с разностью прогрессии m. Все члены этой прогрессии можно описать формулой:

at a0 t m, t Z ,

где a0 – наименьший неотрицательный вычет.

п.3.6 Полная и приведенная система вычетов Определение. Множество чисел, взятых в точности по одному из ка-

ждого класса вычетов по модулю m, называется полной системой вычетов по модулю m.

Определение. Любой вычет числа а по модулю m называется пред-

ставителем класса вычетов a .

Замечание. Обычно, из каждого класса вычетов в качестве его представителя берется наименьший неотрицательный вычет. В результате, полная система вычетов по модулю m имеет вид

{0,1,...,m 1}.

Определение. Вычет b числа а по модулю m называется абсолютно

12

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

наименьшим вычетом, если он по абсолютной величине не превосхо-

дит половины модуля, т.е. если | b | m2 .

Определение. Полнаясистемавычетовпомодулюm называетсяполной системойабсолютнонаименьшихвычетов, есликаждыйвычетвэтойсистемепоабсолютнойвеличиненепревосходитполовинымодуля.

Теорема. Если a b (mod m) , то D(a,m) D(b,m) .

Другими словами, все числа из одного класса вычетов по модулю m имеют с модулем m одинаковый наибольший общий делитель.

Определение. Класс вычетов a числа а по модулю m называется примитивным, если числа а и m взаимно простые, т.е. D(a,m) 1.

Определение. Множество чисел, взятых в точности по одному из каждого примитивного класса вычетов, называется приведенной системой вычетов по модулю m.

Замечание. Если из каждого примитивного класса вычетов по модулю m взять в качестве его представителя наименьший неотрицательный вычет, то в случае простого модуля, т.е. когда m p – простое

число, приведенная система вычетов будет иметь вид: {1, 2, ..., p 1} .

В случае произвольного модуля приведенную систему вычетов обозначают

{a1 ,a2 ,...,at },

где t – число примитивных классов вычетов.

Множество всех примитивных классов вычетов по модулю m обозначается Z*m . Таким образом, по определению

Z*m {a1 ,a2 ,...,at } ,

где t – число примитивных классов вычетов по модулю m.

13

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

п.3.7 Теоремы Эйлера и Ферма Определение. Количество чисел в последовательности

0,1,...,m 1

взаимно простых с числом m называется функцией Эйлера и обозначается (m) .

Замечание. Из последнего определения следует, что число примитивных классов вычетов по модулю m равно (m) , и приведенная систе-

ма вычетов по модулю m содержит t (m) чисел. В частности, если m p – простое число, то (p) p 1 .

Теорема. (Свойства функции Эйлера.)

1)Свойство мультипликативности. Если m и n – взаимно простые натуральные числа, то

(m n) (m) (n) .

2)(1) 1

3)Если р – простое число, то для любого натурального числа n

(pn ) pn pn 1 .

Замечание. Свойства функции Эйлера позволяют вычислять ее значения для любого натурального числа. Пусть имеется каноническое разложение натурального числа n в произведение простых множителей:

n p1 1 p2 2 ...pmm .

Тогда

(n) (p1 1 ) (p2 2 )... (pmm ) (p1 1 p1 1 1 )(p2 2 p2 2 1 )...(pmm pmm 1 )

Теорема. (Теорема Эйлера.) Пусть m 1 – произвольное натуральное число. Тогда для любого целого числа а взаимно простого с m верно сравнение

a (m) 1(mod m) .

Теорема. (Малая теорема Ферма) Пусть р – простое число. Тогда для любого целого числа а верно сравнение ap a (mod p) .

14

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Практическое занятие 4. Сравнения 1-й степени п.4.1 Действия с классами вычетов

Пусть m 1 – произвольное натуральное число, a, b Zm – два произ-

вольных класса вычетов по модулю m. Определим сложение и умножение классов вычетов по следующим правилам:

a b a b, a b a b .

Определение. Класс вычетов a b по модулю m называется суммой классов вычетов a и b по модулю m. Класс вычетов ab по модулю m

называется произведением классов вычетов a и b по модулю m.

Замечание. Из определений следует, что для сложения классов вычетов достаточно из каждого слагаемого выбрать по одному представителю и сложить их. Полученная сумма представителей будет представителем класса суммы. Аналогично для умножения классов. Можно доказать, что результат сложения и умножения классов вычетов по заданному модулю не зависит от выбора представителей этих классов.

Так как число классов вычетов по модулю конечно, то для множества Zm можно составлять таблицы сложения и умножения. Такие табли-

цы называются таблицами Кэли. Смотрите ниже, в пункте 3, примеры.

Теорема. Множество примитивных классов вычетов замкнуто относительно умножения, т.е. произведение двух примитивных классов вычетов есть примитивный класс вычетов:

a,b Z*m , a b a b Z*m .

Последняя теорема позволяет составлять таблицу умножения для множества Z*m .

п.4.2 Понятие группы

Пусть дано произвольное множество G. Что из себя представляют элементы множества G нас пока не будет интересовать. Это могут быть числа, функции, многочлены, векторы, классы вычетов или чтото другое, это неважно. Важно, что на множестве G определено сложение его элементов или умножение.

15

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Определение. Говорят, что на множестве G определена операция сложения (умножения), если для любых двух его элементов a,b G

определен элемент a b G ( ab G ), который называется суммой (произведением) элементов а и b.

Замечание. Если сумма a b (произведение ab ) любых элементов а и b множества G также является его элементом, то в этом случае говорят, что множество G замкнуто относительно операции сложения (умножения) его элементов. Если мы сами определяем на некотором множестве правило сложения или умножения, то мы должны позаботиться о том, чтобы данное множество было замкнутым относительно определяемых операций.

Определение. Пусть на множестве G определена операция сложения.

Если существует такой элемент G , который обладает свойством:

a G, a a a ,

тогда элемент называется нулевым элементом или просто нулем, и часто обозначается цифрой 0.

Определение. Пусть на множестве G определена операция умножения.

Если существует такой элемент e G , который обладает свойством:

a G, ae ea a ,

тогда элемент е называется единичным элементом или просто единицей, и часто обозначается цифрой 1.

Определение. Пусть на множестве G определена операция сложения и существует нулевой элемент 0 G . Пусть a G – какой-нибудь элемент множества G. Если существует элемент b G , для которого выполняется равенство:

a b b a 0 ,

тогда элемент b называется противоположным элементу а, и обозначается a .

Таким образом, по определению противоположного элемента a ( a) ( a) a 0 . Заметим, что из определения противоположного

элемента следует, что элемент а является противоположным элементу

a , т.е. a ( a) .

16

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Определение. Пусть на множестве G определена операция умножения и существует единичный элемент e G . Пусть a G – какойнибудь элемент множества G. Если существует элемент b G , для которого выполняется равенство:

ab ba e ,

тогда элемент b называется обратным элементу а, и обозначается a 1 . При этом сам элемент а называется обратимым элементом.

Таким образом, по определению обратного элемента a a 1 a 1 a e .

Заметим, что из определения обратного элемента следует, что элемент а является обратным элементу a 1 , т.е. a (a 1 ) 1 .

Определение. Операция сложения (умножения), определенная на множестве G, называется ассоциативной (подчиняется закону ассоциативности), если для любых трех его элементов a,b,c G верно ра-

венство

(a b) c a (b c) ( (ab)c a(bc) ).

Определение. Операция сложения (умножения), определенная на множестве G, называется коммутативной (подчиняется закону коммутативности), если для любых двух его элементов a,b G верно равен-

ство

a b b a ( ab ba ).

Определение. Множество G называется группой относительно операции сложения, если на этом множестве определена операция сложения, которая удовлетворяет следующим трем условиям, которые называются аксиомами группы:

1)сложение подчиняется закону ассоциативности;

2)в множестве G есть нулевой элемент G ;

3)для любого элемента a G в множестве G есть противоположный ему элемент a G .

Определение. Множество G называется группой относительно операции умножения, если на этом множестве определена операция умно-

17

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

жения, которая удовлетворяет следующим трем аксиомам:

1)умножения подчиняется закону ассоциативности;

2)в множестве G есть единичный элемент e G ;

3)любой элемент a G является обратимым в множестве G, то есть существует обратный ему элемент a 1 G .

Определение. Группа G относительно операции сложения или умножения называется абелевой или коммутативной, если групповая операция (т.е. сложение или умножение) подчиняется закону коммутативности.

п.4.3 Понятие кольца и поля Определение. Множество А, на котором определены две алгебраиче-

ские операции – сложение и умножение, называется кольцом, если относительно сложения множество А является абелевой группой, и выполняется условие (закон дистрибутивности умножения относительно сложения):

x, y,z A, x(y z) xy xz, (y z)x yx zx .

Определение. Если в кольце А существует единичный элемент отличныйотнулевогоэлемента, токольцоАназываетсякольцомсединицей.

Определение. Если умножение в кольце А подчиняется закону коммутативности, то кольцо А называется коммутативным кольцом.

Определение. Если в кольце А для некоторых его ненулевых элементов a,b A, a 0 b верно равенство

ab 0 ,

то элемент а называется левым делителем нуля, а элемент b – правым делителем нуля.

Замечание. В коммутативном кольце нет смысла различать левый и правый делители нуля, так как ab ba , поэтому говорят просто о делителях нуля.

Определение. Если в кольце нет делителей нуля, тогда оно называется кольцом без делителей нуля.

18

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Определение. Коммутативное кольцо с единицей и без делителей нуля называется областью целостности или просто областью.

Определение. Коммутативное кольцо с единицей называется полем, если любой его ненулевой элемент является обратимым в этом кольце.

Другими словами, полем называется множество K, на котором определены операции сложения и умножения, относительно которых множество K является коммутативным кольцом с единицей 1 K , причем 1 0 , где 0 K – нулевой элемент, и x K, x 0 существу-

ет x 1 K .

Теорема. В поле нет делителей нуля.

п.4.4 Кольцо и поле классов вычетов Теорема. Множество классов вычетов по любому модулю является коммутативным кольцом с единицей.

Теорема. Множество примитивных классов вычетов относительно их умножения является коммутативной группой.

Таким образом, Zm – кольцо классов вычетов по модулю m, Z*m – группа примитивных классов вычетов по модулю m.

Теорема. Кольцо классов вычетов по простому модулю является полем.

Пусть р – простое число, тогда Zp {0, 1,...,p 1} – поле классов вычетов по простому модулю р.

Теорема. Класс вычетов a по модулю m является обратимым элементом

вкольцеклассоввычетов Zm тогдаитолькотогда, когдаклассвычетов a являетсяпримитивнымклассомвычетовподанномумодулюm.

Теорема. В поле классов вычетов по простому модулю линейное уравнение a x b имеет единственное решение x (a) 1 b .

19

Головизин В.В. Теорминимум ПЗ курса «Алгебра и геометрия», УдГУ, Ижевск – 2011, с.51

Теорема. В кольце классов вычетов по произвольному модулю m ли-

нейное уравнение a x b разрешимо тогда и только тогда, когда D | b , где D D(a,m) . Если это уравнение разрешимо, то оно имеет D

решений. Если x0 – какое-нибудь решение данного уравнения, то ос-

тальные D 1 решений можно найти по формуле x x0 mD k , где число k пробегает числа 1, 2, …, D – 1.

Замечание. Уравнение a x b в кольце классов вычетов по модулю m равносильно сравнению ax b (mod m) . Поэтому последние теоре-

мы можно сформулировать на языке сравнений. Эти теоремы составляют теорию сравнений 1-й степени, смотрите следующий пункт.

п.4.5 Сравнения 1-й степени

Определение. Пусть m 1 – произвольное натуральное число, а и b – произвольные целые числа. Сравнение

ax b (mod m) ,

где х – неизвестное целое число, называется сравнением первой степени с одним неизвестным.

Замечание. Пусть r – произвольный класс вычетов по модулю m, тогда, по определению,

r {x Z | x r (mod m)} ,

т.е. это множество описывается как множество всех целых чисел х, удовлетворяющих сравнению

x r (mod m) .

Далее, так как

x r (mod m) m | x r x r tm ,

где t Z , то

xr (mod m) x r tm, t Z .

Вдальнейшем, именно так мы и будем записывать классы вычетов по заданному модулю.

x x0 tm, t Z из класса вычетов x x0 (mod m) также будет удов-

20