Линейные сравнения с одним неизвестным (стр. 2 )

Если некоторое число удовлетворяет этой системе, то есть если и - наименьшее общее кратное этих чисел, а - любое число, такое, что , то по свойствам сравнимости для всех , а, следовательно, , то есть .

Мы видим, что вместе с каждым числом , удовлетворяющим системе (9), этой же системе удовлетворяет и любое число класса по модулю М. Перейдем теперь к рассмотрению системы сравнений первой степени с одним неизвестным. Рассмотрим сначала систему вида: (10).

Теорема 4. Пусть - наименьший общий делитель, а М – наименьшее кратное и ; тогда если не делит , то система сравнений (10) не имеет решений, а если делит , то система имеет одно решение, представляющее собой класс по модулю М.

Доказательство. Из первого сравнения (10) получаем . Задача нахождения решений системы сводится, таким образом, к тому, чтобы выбрать такие , при которых удовлетворяет и второму сравнению, то есть найти все целые , такие, что . Следовательно, надо решить сравнение

(11).

Если и не делит , то сравнение (11) не имеет решений, а, следовательно, и система (10) также не имеет решений.

Если же делит , то решение сравнения (11) можно записать в виде . Подставляя эти значения в уравнение , выделяем из множества значений , удовлетворяющих первому сравнению, те, которые удовлетворяют и второму: . Эти значения образуют класс по модулю М, то есть , что и является решением системы (10), причем оно единственное.

Теорема 5. Система (12)

либо совсем не имеет решений, либо имеет одно решение.

Доказательство проводится индукцией по .

Теорема 6. Если - попарно взаимно простые числа, то система (12) совместна и имеет одно решение, представляющее собой класс по модулю .

Доказательство проводится индукцией по .

Пусть два натуральных числа и взаимно просты. Поставим перед собой задачу: найти целое число, которое при делении на эти числа образует данные остатки и . Существование такого числа вытекает из того, что уравнение разрешимо в целых числах и , а именно, искомым является, например, число .

Оказывается, что аналогичное утверждение справедливо и для случая .

Теорема 7. (Китайская теорема об остатках). Пусть - натуральные числа, каждые два из которых взаимно просты, - произвольные целые числа. Существуют целые числа , удовлетворяющие системе уравнений .

Доказывается индукцией по .

Название теоремы объясняется тем, что если каждые два из натуральных чисел взаимно просты, то существует целое число, которое при делении на эти числа дает любые заданные остатки . Увеличивая его на любые кратные числа , мы получим бесконечное множество натуральных чисел, дающих при делении на соответственно остатки . Китайцы довольно давно владели этой теоремой, во всяком случае в III веке.

Рассмотрим членов арифметической прогрессии

(13)

где a – целое число, а - взаимно простое с . Часто бывает очень полезной следующая теорема.

Теорема 8. Среди чисел прогрессии (13) имеется ровно одно, делящееся на .

Доказательство. Разность -го т -го чисел (13), равная не делится на . Иначе оказалось бы, что делится на , что невозможно, так как . Тем самым числа (13) попарно не сравнимы по модулю и поэтому дают различные остатки при делении на . Следовательно, среди чисел (13) представлены все классы по модулю , то есть для каждого из остатков ровно одно из чисел (13) сравнимо с ним по модулю .