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

но число 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. Предположим, что верно соотношение

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) 2— (n — 1))

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

Р n = P n -1+ 3 n — 2 = 1/2 (З n 2— 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 = 2 3 • 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 = p rs -1или n = p r -1 q s -1,

где р и q — простые числа.

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

1.8 128 и 33550 336.

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

1. а) D (360, 1970) = 10; б) D (30, 365) = 5.

2. Предположим, что √2 — рациональное число, т. е. √2 = a / b . Можем считать, что все сокращения произведены и числа а и b не имеют общих множителей. Возводя в квадрат это соотношение, получаем 2 b 2= a .