Читаем Приглашение в теорию чисел полностью

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

Если сравнение (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 нет в таблицах, то оно простое.

Наименьшим составным числом, удовлетворяющим сравнению (8.4.3), является

N = 341 = 11 • 31.

В пределах 1000 существуют еще два таких числа,

а именно:

N = 561= 3 • 11 • 17,

N = 645 = 3 • 5 • 43.

Число 561 является замечательным, так как соответствующее сравнение (8.4.1) выполняется для каждого целого числа а, взаимно простого с числом N. Мы называем такие особые числа числами, имеющими свойство Ферма. По таким числам в последнее время было проведено огромное количество исследований.

<p>РЕШЕНИЯ ИЗБРАННЫХ ЗАДАЧ</p>

Система задач 1.3.

Ответы для обеих задач можно найти в табл. 3 на стр. 61.

Система задач 1.4.

1. Предположим, что верно соотношение

T_n_-1 = 1/2 (n-1) n.

Можно проверить его для n= 2, 3, 4. Из рис. 4 видно, что Т_n получается из T_n_-1 прибавлением числа n, поэтому

Т_n = Т_n-1 + n = 1/2 n (n + 1).

2. Из рис. 5 видно, что для того, чтобы получить Р_n, нужно прибавить к Р_n_-1 число

1 +3 (n — 1) = Зn — 2.

Если мы уже знаем, что

P_n_-1 = 1/2 (3 (n — 1)² — (n — 1))

(это справедливо для п = 2, 3, 4, в соответствии с последовательностью (1.4.3)), то отсюда следует, что

Р_n = P_n_-1 + 3n — 2 = 1/2 (Зn² — n).

3. Мы можем получить n-е k-угольное число из (n — 1) — го, прибавив к нему

(k — 2) (n — 1) + 1

и выводя формулу таким же способом, как и в задаче 2. Задачи 2 и 3 могут быть решены иначе: делением точек на треугольники, как указано на рис. 5, и использованием формулы для Т_n. Проведите это доказательство во всех деталях.

Система задач 1.5.

1. Например, квадрат

16 3 2 13

9 6 7 12

5 10 11 8

4 15 14 1

полученный перестановкой второй и третьей строк квадрата Дюрера, также является магическим. Менее тривиальным является квадрат

16 4 1 13

9 5 8 12

6 10 11 7

3 15 14 2

2. Так как числа в квадрате 4 × 4 не превышают 16, возможны лишь два года, 1515 и 1516. Первый, очевидно, исключается, во втором случае построить квадрат оказывается невозможным.

Система задач 2.1.

2. 1979.

3. Числа от 114 до 126 все составные.

Система задач 2.3.

1. n = 3, 5, 15, 17,51,85

2. Имеем

360°/51 = 6 360°/17 — 360°/3.

3. Количество различных произведений чисел Ферма (от одного до пяти чисел в одном произведении) равно

5 + 10 + 10 + 5 + 1 = 31.

Таково количество чисел, для которых могут быть построены многоугольники. Наибольшим значением является

n = 3 • 5 • 17 • 257 • 65537 = 4 294 967 295.

Система задач 2.4.