Дискретная математика. Ерош И.Л - 115 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

115
Произвольное целое число a единственным образом может быть
представлено в виде a = mt + r, где m > 0 – целое положительное чис
ло (делитель), t – частное, r – остаток (0 £ r < m). Так, например,
если a = 17, m = 5, то 17 = 5·3 + 2.
В дальнейшем мы будем использовать операцию деления и интере
соваться только остатком, не обращая внимание на частное. Так, на
пример, число 16 при делении на 11 дает остаток 5.
Наименьший положительный остаток от деления некоторого чис
ла a на число m обычно называют наименьшим неотрицательным
вычетом a по модулю m. Если m делит a нацело, то остаток r = 0.
Например, наименьший неотрицательный вычет при делении числа
18 на 6 равен 0.
Пусть имеется два числа a и b. Будем говорить, что они сравнимы
по модулю m, если при делении на m они дают одинаковый целый по
ложительный остаток. Например, числа 8 и 15 при делении на 7 име
ют одинаковый остаток 1, т. е. они сравнимы по модулю 7. Сравнение
чисел будем обозначать так: a º b mod m.
Сравнению a º 0 mod m удовлетворяют все числа a, которые делят
ся на m нацело или, как говорят, кратные m.
6.1.2. Свойства сравнений
От сравнения a º b mod m можно перейти к равенству. Сравнение
a º b mod m справедливо, если выполняется следующее равенство:
a = b + m ·t, где · – умножение, t – некоторое целое (положительное,
отрицательное или 0).
Такая связь между сравнениями и равенствами позволяет распрос
транить понятие сравнения не только на положительные, но и на от
рицательные числа. Например, можем записать 12 º 7 º 2 º –3 º –8 º
–13 … mod 5.
Из связи между сравнениями и равенствами следуют правила экви
валентных преобразований сравнений.
a) Если a º b mod m и b º c mod m, то a º с mod m.
b) Если a º b mod m и с º d mod m, то a+b º с+d mod m. Это правило
можно сформулировать и так: сравнения по одинаковому модулю мож
но почленно складывать.
c) Если a º b mod m, то a º b+m·t mod m, так как справедливо срав
нение m·t º 0 mod m, т. е. к любой части сравнения можно прибавить
модуль, умноженный на любое целое.
d) Если a º b mod m и с – любое целое, взаимно простое с m, то
a·c º b·c mod m, т. е. обе части сравнения можно умножить на любое
целое, если оно взаимно простое с модулем m.

Страницы