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

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 является составным.

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

a^N-1 = 2⁹⁰ = 2⁶⁴ • 2¹⁶ • 2⁸ • 2²

Более того,

2⁸ = 256 ≡ -17 (mod 91),

2¹⁶ = (2⁸)² ≡ (-17)² = 289 ≡ 16 (mod 91),

2³² = (2¹⁶)² ≡ (16)² = 256 ≡ -17 (mod 91),

2⁶⁴ = (2³²)² ≡ (-17)² = 289 ≡ 16 (mod 91),

так что

2⁹⁰ = 2⁶⁴ • 2¹⁶ • 2⁸ • 2² ≡ 16 • 16 • (-17) • 4 ≡ 64 ≠ 1 (mod 91).

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

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

В особенности это относится к числам Ферма

F_n = 2^2ⁿ+1,

которые мы обсуждали в § 3 главы 2. Как мы уже отмечали, они являются простыми для n = 0, 1, 2, 3, 4. Чтобы проверить число

F₅ = 2^2ˆ5 + 1 = 2³² + 1 = 4294967297

с помощью теоремы Ферма, можно взять а = 3. Если бы F₅ было простым числом, мы бы имели, что

З^2ˆ32 ≡ 1 (mod F₅). (8.4.2)

Чтобы вычислить остаток степени в левой части сравнения, мы должны возвести число 3 в квадрат 32 раза и всякий раз привести полученный результат по модулю F₅. Мы избавим читателя от подробностей. Можно найти, что сравнение (8.4.2) не выполняется, следовательно, число F₅ является составным. Известный множитель 641 был найден путем проб. Тот же самый метод был использован для того, чтобы показать, что несколько больших чисел Ферма не являются простыми. Для некоторых из них нам известны множители, а для других нет.