Приглашение в теорию чисел
Шрифт:
x + yr ≡ r (mod (N — 1)). (8.3.2)
Чтобы увидеть, что при этом разные команды х имеют разных противников, заметим, что сравнение
x + yr ≡ r ≡ x' + yr (mod (N — 1))
означает, что
x ≡ x' (mod (N — 1))
или х = x',
Единственная сложность возникает в том случае, когда х = 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 ≡ 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– м туре играет с командой у, то команда у в этом туре играет с командой х.
§ 4. Простое или составное?
В заключение обсудим применение сравнений в качестве метода определения того, является ли некоторое большое число простым или составным. Этот очень эффективный метод особенно хорош, когда речь идет о некотором числе, выбранном наугад. Он основан на малой теореме Ферма (7.5.8).
Пусть N — исследуемое число. Выберем небольшое число а взаимно простое с N. Удобно в качестве числа а брать некоторое небольшое простое число, не являющееся делителем числа N, например, 2, 3 или 5. Если бы N было простым числом, то для него было бы справедливо сравнение
аN– 1 ≡ 1 (mod N), (8.4.1)
в соответствии с малой теоремой Ферма. Следовательно, если мы проверим это сравнение (8.4.1) и убедимся, что оно не выполняется, то можно утверждать, что число N является составным.