Защита информации 2 5 (стр. 2 из 14)

(2.1)

(где все

-положительные целые числа и ) до тех пор, пока не получится остаток, равный 0. Этот последний остаток можно не писать, так что ряд равенств (2.1) закончится следующим образом:

(2.2)

Последний положительный остаток

в этом процессе и является наибольшим общим делителем чисел и .

/Пример/

Найдем НОД (175,77).

175=77*2+21;

77=21*3+14;

21=14*1+7;

14-7*2.

Последний положительный остаток равен 7. Следовательно (175,77)=7.

Наименьшее общее кратное. Всякое целое, кратное всех данных чисел, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным (НОК) и обозначается

.

Классы вычетов. Числа, сравнимые по модулю

, образуют классвычетов по модулю . Все числа из одного класса имеют один и тот же остаток от деления на . Любое число из класса вычетов называется вычетом по модулю .Соответствующий класс обозначается через . Поскольку соотношение является бинарным отношением эквивалентности, то имеем разбиение целых чисел на классы эквивалентности (классы вычетов). Всего имеется классов вычетов по модулю : .

Функция Эйлера. Арифметическая функция

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

Сравнения. Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное число

. Каждому целому числу отвечает определенный остаток от деления его на ; если двум целым и отвечает один и тот же остаток , то они называются равностаточными по модулю или сравнимыми по модулю . Сравнимость чисел и по модулю записывается так:

(2.3)

это читается следующим образом:

сравнимо с по модулю .

*Доказательство*

Из

следует, что

(

- остаток от деления на , - неполное частное)

откуда

Обратно, из

представляя в виде

выводим

т.е.

. □

Сравнимость чисел

и по модулю равносильна: возможности представить в виде , где - целое.

Свойства сравнений.

1. Два числа, сравнимые с третьим, сравнимы между собой.

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

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

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

5. Обе части сравнения можно возвести в одну и ту же степень.

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

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

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

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

10. Если сравнение

имеет место по нескольким модулям, то оно имеет место и по модулю, равному общему наименьшему кратному этих модулей.

11. Если сравнение имеет место по модулю

, то оно имеет место и по модулю , равному любому делителю числа .

12. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.

Первообразные корни. При

существуют положительные с условием , например (теорема Эйлера) .Наименьшее из них называется: показатель, которому принадлежит по модулю .