§ 2. Сравнения

1. Общие понятия.

Всякий раз, как приходится говорить о делимости целых чисел на некоторое определенное целое число все рассуждения становятся яснее и проще, если пользоваться отношением сравнения, введенным Гауссом, и соответствующими обозначения.

Чтобы ввести понятие сравнения, рассмотрим остатки, получающиеся при делении различных чисел, например, на 5. Мы получаем:

Заметим, что остатком при делении на 5 может быть только одно из чисел 0, 1, 2, 3, 4. Говорят, что два числа а и сравнимы по модулю 5, если при делении на 5 они дают один и тот же остаток. Так, все числа сравнимы по модулю 5, так как при делении на 5 все они дают остаток 2. Вообще, говорят, что два числа а и b сравнимы по модулю некоторое целое число), если при делении на они дают один и тот же остаток; другими словами, если существует такое целое число (положительное, отрицательное или нуль), что Например, 27 и 15 сравнимы по модулю 4, так как

Для отношения сравнения введено специальное обозначение — если а и b сравнимы по модулю то пишут: [Если же а не сравнимо с по модулю , то пишут ] Если ясно, какой модуль имеется в виду, то приписку опускают.

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

Прежде чем перейти к более детальному рассмотрению сравнений и их свойств, пусть читатель проверит, что следующие утверждения в точности эквивалентны:

1. а сравнимо с по модулю d.

2. где целое.

3. делится на

Введенные Гауссом обозначения для сравнений подчеркивают то обстоятельство, что сравнения обладают многими свойствами обычных равенств. Напомним эти свойства:

1) Всегда

2) Если то

3) Если

Кроме того, если то

Эти же свойства сохраняются, если соотношение равенства заменяется соотношением сравнения Именно:

1) Всегда

(Проверьте! — это нетрудно.)

Точно так же, если то

Таким образом, сравнения одному и тому же модулю можно складывать, вычитать и умножать. В самом деле, из

вытекают:

что и приводит к нужным заключениям.

Рис. 6. Геометрическое представление целых чисел

Рис. 7. Геометрическое представление целых чисел по модулю 6

Сравнения допускают великолепное геометрическое представление. Если хотят дать геометрическое представление целым числам, то обыкновенно выбирают прямолинейный отрезок единичной длины и затем откладывают кратные отрезки в обе стороны. Таким образом, для каждого целого числа получается соответствующая ему точка на прямой — числовой оси (рис. 6). Но если приходится иметь дело с числами по данному модулю два сравнимых числа — поскольку речь идет о делимости на рассматриваются как нечто неразличимое, так как дают одни и те же остатки. Чтобы изобразить все это геометрически, возьмем окружность, разделенную на равных частей. Всякое целое число при делении на дает в качестве остатка одно из чисел : эти числа мы и расставим по окружности на равных расстояниях. Каждое число сравнимо с одним из

этих чисел по модулю и, следовательно, представляется соответствующей точкой; два числа сравнимы, если изображаются одной и той же точкой. Рис. 7 сделан для случая Циферблат часов может также служить моделью.

В качестве примера применения мультипликативного свойства сравнений 6) определим остатки, получающиеся при делении на одно и то же число последовательных степеней числа 10. Так как то

Умножая многократно это сравнение само на себя, получаем дальше

Отсюда можно заключить, что всякое целое число, запись по десятичной системе которого имеет вид:

дает тот же остаток при делении на 11, что и сумма его цифр, взятая с чередующимися знаками

В самом деле, мы имеем:

Так как все выражения сравнимы с нулем по модулю 11, то также сравнимо с нулем, и потому 2 при делении на 11 дает тот же остаток, что и В частности, число делится на 11, т. е. дает остаток 0 при делении в том и только в том случае, если знакочередующаяся сумма его цифр делится на 11. Например, число Делится на 11, так как делится на 11. Найти таким же образом правило делимости на 3 или на 9 еще проще, так как и 9), и потому и 9) при любом Отсюда следует, что число делится на 3 и на 9 в том и только в том случае, если сумма его цифр

Делится соответственно на 3 и на 9.

Если в качестве модуля возьмем 7, то получим

Далее остатки повторяются. Таким образом, z делится на 7 в том и только в том случае, если выражение

делится на 7.

Упражнение. Найти подобный же признак делимости на 13.

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

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

Из второй таблицы видно, что произведение сравнимо с нулем по модулю 5 только в том случае, если а или . Это наводит на мысль о существовании следующего общего закона:

7) только в том случае, если или что является распространением хорошо известного свойства обыкновенного умножения:

Но закон 7) действителен только при том условии, что модуль есть простое число. Действительно, сравнение

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

С другой стороны, закон теряет силу при составном: можно тогда написать где оба множителя меньше, чем так что

и, однако,

Например, , но .

Упражнение. Покажите, что имеет место следующее правило сокращения на простой множитель.

Упражнения.

(см. скан)