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

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

2N– 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. Мы называем такие особые числа числами, имеющими свойство Ферма. По таким числам в последнее время было проведено огромное количество исследований.

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

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

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

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

Tn– 1 = 1/2 (n– 1) n.

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

Тn = Тn– 1 + n = 1/2 n (n + 1).

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

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

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

Pn– 1 = 1/2 (3 (n — 1)2 — (n — 1))

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

Рn = Pn– 1 + 3n — 2 = 1/2 (Зn2 — n).

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

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

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

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

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