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

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