вася

2.1. Отношение сравнимости

Определение2.1. Пусть . Целые числа аи bназываются сравнимыми по модулю т (обозначается ), если разностьделится нат.

Отношение сравнимости обладает следующими свойствами.

Рефлексивность: ).

Симметричность: если , то.
Транзитивность: если , и, то.

Сравнения можно почленно складывать (вычитать): если ,, то.

Доказательство. Из определения отношения сравнимости имеем: делится на т, делится на m. Тогда, по свойству 2 делимости, сумма и разность делятся на т, откуда делится на т. □

Сравнения можно почленно перемножать: если ,, то.

Доказательство. Покажем, что разность делится на т. Прибавим к этому выражению и вычтем из него число . Получим: . Так как оба слагаемых в последней сумме делятся на т, то и вся сумма делится на т. □

Обе части сравнения и модуль можно разделить на их общий делитель: если , то .

Доказательство. Выражение означает, что разность ас−bс делится на тс, то есть, по определению делимости, существует такое целое число d, что ас − bc = mcd. Вынесем общий множитель c за скобки: (a − b)c = mcd. Тогда а − b = md, то есть a−bделится на m. □

Обе части сравнения можно разделить на их общий делитель d, если d взаимно прост с модулем.

Доказательство. Пусть , гдеa = a₁d, b = b₁d, НОД(d, m)=l. По определению отношения сравнимости разность - делится нат. Числа d и mвзаимно просты, значит, по свойству 2 взаимно простых чисел, разность делится на т. □

Если m₁ —делитель числа т и , то .
Если — полином с целыми коэффициентами и, то.

Отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности. Таким образом, отношение сравнимости является отношением эквивалентности на множестве целых чисел.

Отношение эквивалентности разбивает множество, на котором оно определено, на классы эквивалентности. Любые два класса эквивалентности либо не пересекаются, либо совпадают.

Классы эквивалентности, определяемые отношением сравнимости, называются классами вычетов по модулю т. Класс вычетов, содержащий число а, обозначается a(mod т) или и представляет собой множество чисел вида a+km, где ; число а называется представителем этого класса вычетов.

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

Определение 2.2. Полной системой вычетов по модулю m называется совокупность m целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю m. Совокупность чисел 0, 1, 2,…, m−1 называется системой наименьших неотрицательных вычетов. Совокупность чисел

при нечётном m;

при чётном m

называется системой абсолютно наименьших вычетов по модулю т. Каждый из абсолютно наименьших вычетов по абсолютной ветчине не превосходит половины модуля. Часть полной системы вычетов, состоящая из чисел, взаимно простых с модулем, называется приведенной системой вычетов.

Определение2.3. Функция , ставящая в соответствие каждому натуральному числут количество натуральных чисел, меньшихт и взаимно простых с т, называется функцией Эйлера. При этом полагают .

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

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

Доказательство [2]. Пусть — приведенная система вычетов по модулют, составленная из наименьших неотрицательных вычетов. Сопоставим каждому из чисел его наименьший неотрицательный вычет, где, то есть,,..., , и покажем, что системы вычетов и совпадают с точностью до порядка элементов.

Действительно, поскольку НОД(а, т)=1 (по условию теоремы) и НОД(,m) = 1 для всех i=1,2,..., (по определению приведенной системы вычетов), то по свойству 3 взаимно простых чисел НОД(, т) = 1 для всех i=1, 2,..., . Из сравненияследует существование такого целого числаz_i ,что гдеi = 1, 2,...,. Тогда, согласно лемме 1.6, НОД(т)= НОД(, т)=НОД(т)= 1, то есть наименьшие неотрицательные вычеты взаимно просты с числомт. Значит, каждому из чисел соответствует некоторое число .

Осталось показать, что все числа различны. Действительно, если выполняется равенство, то. Числааит взаимно просты, поэтому можем поделить обе части сравнения на а. Получим . Но— наименьшие неотрицательные вычеты, тогда должно выполняться равенство, а этоне так. Значит, и среди чисел нет одинаковых, и эти две системы вычетов совпадают.

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

Теорема 2.2 (малая теорема Ферма). Пусть число p простое, число а целое, а не делится на р. Тогда .

Рассмотрим способ вычисления функции Эйлера.

Теорема2.3. Если число р простое, число n натуральное, то .

Доказательство. Число р простое, тогда любое число а, не превосходящее и не взаимно простое с, делится на р, то есть является элементом множества Р = {р, 2р, ..., }. Функция Эйлера будет

задавать число элементов множества {р, 2р, ..., }\Р. Это число равно .

Из свойства мультипликативности функции Эйлера и теоремы 2.3 следует, что если число n > 1 и —его каноническое разложение, то

Эту формулу называют формулой Эйлера. С ее помощью можно дать еще одно доказательство первой теоремы Евклида о простых числах (теорема 1.12). Как и ранее, предположим, что p₁, p₂,…, p_s — все простые числа, и составим число N=p₁p₂...p_s. Тогда должно выполняться равенство = 1 (все числа, не превосходящие N, должны делиться хотя бы на одно из простых чисел р₁, р₂,…, р_s,). Но по формуле Эйлера

Содержание