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

В особенности это относится к числам Ферма

Fn = 22ⁿ+1,

которые мы обсуждали в § 3 главы 2. Как мы уже отмечали, они являются простыми для n = 0, 1, 2, 3, 4. Чтобы проверить число

F5 = 22ˆ5 + 1 = 232 + 1 = 4294967297

с помощью теоремы Ферма, можно взять а = 3. Если бы F5 было простым числом, мы бы имели, что

З2ˆ32 ≡ 1 (mod F5). (8.4.2)

Чтобы вычислить остаток степени в левой части сравнения, мы должны возвести число 3 в квадрат 32 раза и всякий раз привести полученный результат по модулю F5. Мы избавим читателя от подробностей. Можно найти, что сравнение (8.4.2) не выполняется, следовательно, число F5 является составным. Известный множитель 641 был найден путем проб. Тот же самый метод был использован для того, чтобы показать, что несколько больших чисел Ферма не являются простыми. Для некоторых из них нам известны множители, а для других нет.

Если сравнение (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,

где р и 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 не имеют общих множителей. Возводя в квадрат это соотношение, получаем 2b2 = a.

По теореме о единственности разложения число а делится на 2, следовательно, а2 делится на 4. И вновь по теореме о единственности разложения, примененней к числу b2, получаем, что b делится на 2, что противоречит предположению о том, что числа а и b не имеют общих множителей. Полученное противоречие показывает, что √2 — число иррациональное.

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

1. Нечетные числа.

2. Если простое число р является делителем чисел n и n + 1, то оно будет делителем числа (n + 1) — n = 1.

3. Никакие из них не являются взаимно простыми.

4. Да.

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

2. D(220, 284) = 4, D(1184, 1210)=2, D(2620, 2924)= 4, D(5020, 5564) = 4.

3. Чтобы определить наибольшую степень числа 10, на которую делится число n = 12•3… n, мы должны сначала найти наибольшую степень числа 5, на которую оно делится. Каждое пятое число 5, 10, 15, 20, 25, 30 делится на 5, всего таких чисел, не превосходящих числа n, [n/5]. Однако некоторые из них делятся на вторую степень числа 5, а именно, 25, 50, 75, 100…; таких чисел существует [n/25]. Некоторые из них делятся на третью степень числа 5, т. е. на 125: 125, 250, 375; их существует [n/53] и т. д. Это показывает, что выражение для точной степени числа 5, делящей число n! таково: