Дискретная математика. Теория чисел. Ерош И.Л. - 5 стр.

UptoLike

Составители:

Рубрика:

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

1.1. Делимость целых чисел

Что общего между числами множества 9, 16, 23, 30, 37, 44 кроме

того, что они все целые? Казалось бы, ничего. Однако если ввести опе-

рацию деления с остатком и интересоваться только целым положитель-

ным остатком от деления чисел этого множества на 7, то окажется, что

все они будут иметь одинаковый остаток, равный 2. Эти числа эквива-

лентны по этому свойству. Тогда приведенную последовательность мож-

но продолжить дальше: 51, 58, 65, 72, 79 … Это множество чисел явля-

ется бесконечным и счетным, все числа множества объединяет одно

общее свойство: при делении на 7 они дают целый положительный оста-

ток 2. Говорят, что эти числа a сравнимы по модулю 7. Такое свойство

множества обозначают

a ≡ 2 mod 7.

Можно рассмотреть другое множество чисел, например, 3, 12, 21, 30,

39, 48, ... и убедиться в том, что при делении на число 9, все они дают

остаток 3; т.е. общее свойство чисел a этого множества можно запи-

сать так:

a ≡ 3 mod 9.

Произвольное целое число a единственным образом может быть

представлено в виде

a = mt + r,

где m > 0 – целое положительное число (делитель); t – частное; r –

остаток

( 0 ≤ r < m).

Так, например, если a = 17, m = 5, то 17 = 5*3 + 2.

В дальнейшем мы будем использовать операцию деления и интере-

соваться только остатком, не обращая внимание на частное. Так, на-

пример, число 16 при делении на 11 дает остаток 5.

Наименьший положительный остаток от деления некоторого числа a

на число m обычно называют наименьшим неотрицательным вычетом