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

2 x ≡ r ≡ 2 x' (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, удовлетворяющий соотношению

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

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

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

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

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

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

Предположим теперь, что r ≠ r 0и s ≠ r 0. Тогда противники команды х в 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 -м туре играет с командой у , то команда у в этом туре играет с командой х .

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

Более того,

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

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

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

2 64= (2 32) 2≡ (-17) 2= 289 ≡ 16 (mod 91),

так что

2 90= 2 64• 2 16 • 2 8• 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 5= 2 2ˆ5+ 1 = 2 32+ 1 = 4294967297

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

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

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

Если сравнение (8.4.1) выполняется для некоторого числа а , взаимно простого с числом N , то число N может как быть простым, так и не быть им. При этом случаи, когда сравнение выполняется для составного числа N , являются исключительными, поэтому при выполнении сравнения мы можем быть почти уверены в том, что число N — просто. Однако для многих целей хотелось бы знать наверняка, является ли данное число простым. Это удается сделать с помощью усовершенствованного метода, основанного на следующем замечании: N является простым числом в том случае, если сравнение (8.4.1) выполняется для степени N — 1, но не выполняется ни для какой степени, являющейся делителем числа N — 1.

Имеется другой подход, эффективный для не слишком больших чисел N. Возьмем а = 2. Американские математики Пуль и Лемер нашли с помощью ЭВМ все значения чисел N ≤ 100 000, исключительные в том смысле, что выполняется сравнение

2 N -1≡ 1 (mod N ), (8.4.3)

но число N является составным. Такие числа N иногда называют псевдопростыми . Для каждого из этих чисел N были указаны также наибольшие простые множители.

С помощью таблиц Пуля и Лемера можно определить простоту любого числа N ^ 100 000 000. Сначала проверяется выполнимость сравнения (8.4.3). Если это сравнение не выполняется, то число N — составное. Если же это сравнение выполняется и число N есть в таблицах, то оно также составное, и мы можем прочесть в таблицах его простой множитель. И наконец, если сравнение (8.4.3) выполняется и числа N нет в таблицах, то оно простое.