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

Пусть числа 1, 2, ...

Пусть числа 1, 2, ...

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

Задача 10. Решите сравнения

а) 3х = 1 (mod 7); б) 6х = 5 (mod 9); в) 4х = 2 (mod 10).

Решение. Заметим, что остаток левой части каждого из сравнений (по соответствующему модулю) зависит только от остатка х. В частности, множество решений периодично (и модуль сравнения является пери-

одом). Поэтому достаточно проверить, какие остатки удовлетворяют сравнению.

а) x = 5 + 7k;

б) решения отсутствуют: действительно, 6x делится на 3, а потому не может иметь вид 5 + 9k = 2 + 3(1 + 3k);

в) x = 3 + 10k, x = 8 + 10k, другими словами, x = 3 + 5k.

Задача 11. Сравнение ax = b (mod m) имеет решение тогда и только тогда, когда b. НОД (a, m).

Решение. Наличие решения у сравнения ax = b (mod m) равносиль­но наличию решения уравнения ax — b = ym (относительно (x, y)). Остается применить задачу 11 из листка «Целые числа 2».

Задача 12. Пусть p — простое число, a = 0 (mod p), тогда сравнение ax = b (mod p) имеет решение, причем любые два решения этого сравнения сравнимы по модулю p.

Решение. Существование решения мгновенно следует из предыдущей задачи; проверим, что любые два решения совпадают по модулю p. Действительно, если x, y — два решения, то ax = ay (mod p), то есть a(x — y).p. Значит (так как p простое), либо a, либо x — y делится на p; но по условию a на p не делится, значит, x = y (mod p).

Ш Последняя задача показывает, что на остатках по простому моду­лю имеется однозначное деление. Таким образом, они образуют не только кольцо, но даже поле.

Задача 13* (китайская теорема об остатках). Пусть числа a1, a2, ..., an попарно взаимно просты. Тогда для любых b1, b2,..., bn найдется x такое, что

x = bi (mod ai), i = 1,..., n,

причем любые два числа, удовлетворяющие этому условию, сравни­мы по модулю a1...an.