Чтение онлайн

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– м туре.

Система задач 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– м туре играет с командой у, то команда у в этом туре играет с командой х.

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