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

Начнем со случая 2.

Начнем со случая 2.

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

Указание. Начните с n = 2.

Набросок решения. Начнем со случая n = 2. Как мы уже знаем, все решения первого сравнения имеют вид x = x1 + ya1, где x1 = b1. Нам нужно найти среди них решения второго сравнения. Запишем, что это значит: b1 + ya1 = b2 (mod a2), то есть a1 y = (b2 — b1) (mod a2). Так как a1 и a2 взаимно просты, у этого сравнения имеются решения, причем все они имеют вид y = c + ka2. Подставляя в выражение для x получаем, что (все) решения исходной системы имеют вид

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

х = x2 + la1a2, где l — произвольное число, а x2 — некоторое фикси­рованное решение (в наших обозначениях х2 = х1 + a^).

Если теперь посмотреть, что же произошло, станет видно, что мы доказали эквивалентность системы из двух сравнений

х = bi (mod ai), i = 1, 2,

системе из одного сравнения

х = х2 (mod a1 a2).

Теперь нетрудно изучить и системы из любого числа сравнений: можно просто последовательно уменьшать их количество, и в конце концов свести к одному сравнению по модулю a1.. . an (что, собствен­но, и требовалось доказать).

Ш Достоинство этого решения заключается в том, что оно объясняет, как именно искать решения такой системы (см. следующую задачу).

Ш Задачу можно переформулировать следующим образом. Первая часть утверждает, что естественное отображение v: Z ^ ®i Z/a{Z (приведение по модулям a1,..., an) является сюръективным. Далее, так как прибавление числа, кратного ai, не меняет остаток по мо­дулю ah значение v зависит только от остатка по модулю .. .an; то -е-                            есть имеется отображение v из Ж/(П; a;)Z в ф; Z/a;Z. Вторая часть                            (Т)

утверждает, что v инъективно.

В такой формулировке решать задачу естественно следующим об­разом.