Если сравнение (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. Например, квадрат
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.
1. В каждой из первых десяти сотен имеется соответственно 24, 20, 16, 16, 17, 14, 16, 14, 15, 14 простых чисел.
2. Существует 11 таких простых чисел.
Система задач 3.1.
1. 120 = 23 • 3 • 5; 365 = 5 • 73; 1970 = 2 • 5 • 197.
3. 360 = 2 • 2 • 90 = 2 • 6 • 30 = 2 • 10 • 18 = 6 • 6 • 10.
Система задач 3.2.
1. Простое число имеет два делителя; рα — степень простого числа, имеет а + 1 делитель.
2. τ(60) = 12, τ(366) = 8, τ(1970) = 8.
3. Наибольшим количеством делителей у числа, не превосходящего 100, является 12. Такое количество делителей имеют числа 72, 84, 90, 96.
Система задач 3 3.
1. 24; 48; 60; 10080.
2. 192; 180; 45360.
3. 24 и 36.
4. Пусть число делителей равно rs, где r и s — простые числа. Тогда
n = prs-1 или n = pr-1 qs-1,