О. ОРЕ - Приглашение в теорию чисел

dN ≡ d1600 — 2с + Y + [1/4 с] + [1/4 Y] (mod 7). (8.2.7)

Применим эту формулу к 1968 году, в котором 1 марта падает на пятницу, следовательно, d1968 = 5.

Здесь с = 19, [1/4 c] = 4, Y = 68, [1/4 Y] = 17,

и мы находим d1968 = 5 ≡ d + 2 (mod 7).

Это даст нам, что d1600 = 3, следовательно, 1 марта 1600 года было средой. Когда мы вставим полученное значение в (8.2.7). мы придем к формуле

dN = 3 — 2с + Y + [1/4 с] + [1/4 Y] (mod 7) (8.2.8)

для номера дня недели 1 марта N-го года.

Вторым этапом будет определение количества дней по модулю 7 от 1 марта до произвольно взятого дня этого года. Так как количество дней в месяце

меняется, то для этого требуется некоторая хитрость. Начнем с нахождения количества дней, которые нужно прибавить к номеру дня 1 марта, чтобы получить номер дня 1 числа любого другого месяца по модулю 7.

Так как в марте 31 день, то для получения номера 1 апреля нужно добавить 3, для получения номера 1 мая мы должны добавить 3 + 2 дней, так как в апреле 30 дней. Продолжая рассмотрение для последующих месяцев, мы получаем добавочные слагаемые в виде следующей таблицы:

§ 3. Расписания соревнований

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

Обозначим количество участников (или команд) через N. Если число N — нечетное, то в каждом туре соревнований невозможно разбить все команды на пары — каждый раз одна из команд будет свободна от игры. Мы можем обойти эту трудность, добавив фиктивную команду T0 и составляя расписание для (N + 1)-й команды, включая команду Т0. В каждом туре команда, которой выпадает играть с командой Т0, будет свободна от игры.

Из сказанного следует, что можно считать количество команд N четным числом. Каждой команде мы сопоставим число

х = 1, 2…, N—1, N.

Общее количество туров, которое должна сыграть каждая команда, равно N — 1.

Предположим теперь, что х принадлежит множеству {1, 2…, N-1}. (8.3.1)

В качестве противника команды х в r-м туре мы назначим команду с номером у, из множества (8.3.1), где число yr удовлетворяет сравнению

x + yr ≡ r (mod (N — 1)). (8.3.2)

Чтобы увидеть, что при этом разные команды х имеют разных противников, заметим, что сравнение

x + yr ≡ r ≡ x' + yr (mod (N — 1))

означает, что

x ≡ x' (mod (N — 1))

или х = x', так как эти числа принадлежат множеству (8.3.1).

Единственная сложность возникает в том случае, когда х = yr, и таким образом в формуле (8.3.2) получаем

2x ≡ r (mod (N — 1)). (8.3.3)

Существует лишь одно значение х во множестве (8.3.1), для которого выполняется это соотношение. Действительно, если

2x ≡ r ≡ 2x' (mod (N — 1)),

то отсюда следует, что

2(x — x') ≡ 0 (mod (N — 1)),

или

х = х' (mod (N — 1)),

так как N — 1 — нечетное число. Решение сравнения (8.3.3) на множестве (8.3.1) всегда существует, а именно:

x = r/2, если r — четное,

x = (r + N — 1) / 2, если r—нечетное.

С помощью соотношения (8.3.2) мы приписали в r-м туре для каждой команды х ее противника, за исключением номера х0, который удовлетворяет условию (8.3.3). Команда х0 в этом туре будет встречаться с командой, имеющей номер N.

Осталось показать, что в результате такого подбора любая команда в каждом туре r = 1, 2…, N играет с различным противником. Сначала мы удостоверимся в этом для команды с номером N, имеющей в некотором смысле особое положение. В r-м туре она играет с командой х0, определяемой из соотношения (8.3.3). Предположим, что s ≠ r; тогда в s-м туре N-я команда играет с командой, имеющей номер x'0, удовлетворяющий соотношению

2x'0 ≡ s (mod (N — 1)).

При этом не может случиться, что х0 = х', так как это привело бы к тому, что

2х0 = 2х'0 ≡ r ≡ s (mod (N — 1))

и, следовательно, r = s.

Теперь рассмотрим различных противников команды х, принадлежащей множеству (8.3.1). С командой, имеющей номер N, эта команда играет только один раз, а именно в туре r0, где r0 определяется из сравнения

2x ≡ r0 (mod(N — 1)).

Предположим теперь, что r ≠ r0 и s ≠ r0. Тогда противники команды х в r-м и s-м турах будут определяться из соотношения (8.3.2):

х + уr ≡ r (mod (N—1)) и х + ys = s (mod (N —1)). Вновь из равенства yr = ys будет следовать r = s, откуда мы делаем вывод, что yr ≠ ys.

Построим таблицу соревнований, проходящих по круговой системе, для N = 6 команд с помощью изложенного метода. Проведя несколько простых вычислений, получим приведенную ниже таблицу. На пересечении r-й строки и x-го столбца стоит номер того противника команды с номером х, с которым она играет в r-м туре.

r  х 1 2 3 4 5 6

 1    5 4 6 2 1 3

 2    6 5 4 3 2 1

 3    2 1 5 6 3 4

 4    3 6 1 5 4 2

 5    4 3 2 1 6 5

Система задач 8.3.

1. Постройте таблицу для N = 8 игроков.

2. Покажите, что когда r = 2, команды 1, 2…, N встречаются с командами N, N — 1…, 2, 1 соответственно.

3. Почему команда с номером N—1 в r-м туре играет всегда с r-й командой, за исключением r = N—1? С какой командой она играет в этом исключительном случае?

4. Убедитесь, что если в соответствии с формулой команда х в r-м туре играет с командой у, то команда у в этом туре играет с командой х.

§ 4. Простое или составное?

В заключение обсудим применение сравнений в качестве метода определения того, является ли некоторое большое число простым или составным. Этот очень эффективный метод особенно хорош, когда речь идет о некотором числе, выбранном наугад. Он основан на малой теореме Ферма (7.5.8).

Пусть N — исследуемое число. Выберем небольшое число а взаимно простое с N. Удобно в качестве числа а брать некоторое небольшое простое число, не являющееся делителем числа N, например, 2, 3 или 5. Если бы N было простым числом, то для него было бы справедливо сравнение

аN-1 ≡ 1 (mod N), (8.4.1)

в соответствии с малой теоремой Ферма. Следовательно, если мы проверим это сравнение (8.4.1) и убедимся, что оно не выполняется, то можно утверждать, что число N является составным.

Пример. Возьмем N = 91 и выберем а = 2. Тогда

aN-1 = 290 = 264 • 216 • 28 • 22

Более того,

28 = 256 ≡ -17 (mod 91),

216 = (28)2 ≡ (-17)2 = 289 ≡ 16 (mod 91),

232 = (216)2 ≡ (16)2 = 256 ≡ -17 (mod 91),

264 = (232)2 ≡ (-17)2 = 289 ≡ 16 (mod 91),

так что

290 = 264 • 216 • 28 • 22 ≡ 16 • 16 • (-17) • 4 ≡ 64 ≠ 1 (mod 91).

Отсюда делаем вывод, что число N составное. И действительно, 91 = 7 • 13.

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