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

Действительно, если у какогото остатка

Действительно, если у какогото остатка

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

Набросок решения. Заметим, что вторая часть нам по сути уже извест­на. Действительно, если у какого-то остатка имеется два прообраза относительно v, то их разность делится на каждое из ai, то есть (так как ai взаимно просты) эти числа сравнимы по модулю П ai; что и означает инъективность V.

Таким образом V — инъективное отображение конечных мно­жеств с одинаковым количеством элементов, а значит, V — биекция, что и требовалось доказать.

Ш Отметим еще, что V является гомоморфизмом (переводит сумму в сумму, а произведение в произведение), поэтому V является не просто биекцией множества, а изоморфизмом колец Z/ i ai Z и i Z/aiZ.

Такой изоморфизм позволяет сводить разные вопросы об остат­ках по произвольному модулю к вопросам об остатках по модулям вида pk. Это соображение можно применить, например, к решению уравнения х2 = 1 (mod n) (да и любого другого).

Целые числа 3. Сравнения                           189

Задача 14*. Найдите все решения системы сравнений

x = 3 (mod 5) x = 1 ( mod 7) x = 4 (mod 9).

Ответ. x = 148 + 315k.

Решение. Предыдущая задача гарантирует, что множество решений имеет вид x0 + 5 ■ 7 ■ 9k = x0 + 315k, где x0 —какое-то решение.

Будем решать задачу, последовательно добавляя уравнения (см. также решение предыдущей задачи). Множество решений первого уравнения имеет вид 3 + 5k; найдем среди них какое-нибудь реше­ние второго уравнения. Перебирая последовательно k, видим, что подходит уже 3 + 5 = 8 = 1 + 7. Таким образом, у нас имеется полное решение системы первых двух уравнений: 8 + 5 ■ 7k = 8 + 35k, и в этой последовательности надо найти какое-нибудь решение последнего сравнения. Несложный перебор показывает, что подходит k = 4, то есть x0 = 148 является (частным) решением системы.