Таблицы Брадиса

Это отношение и называется сравнимостью

Это отношение и называется сравнимостью

Элементы математики в задачах - Г. А. Мерзон

Этот листок посвящен более подробному изучению остатков от деления целых чисел на целые. На этом примере происходит факти­чески знакомство с понятиями группы, кольца и поля.

При решении многих задач важно уметь правильно выделять су­щественные свойства рассматриваемых объектов. Так, в ряде задач теории чисел, переходя к остаткам от деления, мы сохраняем те свойства числа, которые нам понадобятся, отбрасывая ненужные, и решение задачи упрощается, а иногда становится очевидным. При переходе к остаткам отношению равенства чисел соответствует ра­венство их остатков отделения на некоторое число т. Это отношение и называется сравнимостью по модулю т. Технике работы со сравне­ниями и остатками и посвящен данный листок.

Некоторые из задач листка возникают, как мы увидим позднее, в теории конечных абелевых групп и конечных полей; они играют важную роль и в практических приложениях математики (например, в криптографии — при проверке простоты чисел) — отметим, прежде всего, китайскую теорему об остатках и малую теорему Ферма.

Определение 1. Числа а и b сравнимы по модулю т = 0, если а — b. m.

Обозначение: а = b (mod m).

Задача 1. Докажите, что а сравнимо с b по модулю т тогда и только тогда, когда остаток от деления а на т равен остатку от деления b на т.

Решение. Действительно, а = b (mod т) означает по определению, что а — b. т, то есть а — b = кт. Разделим b на т с остатком: b = 1т + + г. Мы показали, что а = b (mod т) равносильно а — (1т + г) = кт, b = 1т + г, или (что то же самое) а = (l + к)т + г, b = 1т + г. Но последнее условие и означает совпадение остатков а и b при делении на т.

Задача 2. Докажите, что сравнимость по модулю т является отно­шением эквивалентности.