Приглашение в теорию чисел

ОРЕ О.

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

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

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

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

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

или х = x',

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

Единственная сложность возникает в том случае, когда х = y_r, и таким образом в формуле (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– м туре для каждой команды х ее противника, за исключением номера х₀, который удовлетворяет условию (8.3.3). Команда х₀ в этом туре будет встречаться с командой, имеющей номер N.

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

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

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

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

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

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

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

Предположим

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

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

Построим таблицу соревнований, проходящих по круговой системе, для 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 является составным.