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

τ(n) = (α1 + 1) (α2 + 1)… (αr + 1). (3.2.3)

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

1. Сколько делителей имеет простое число? Сколько делителей имеет степень простого числа рα?

2. Найдите количество делителей у следующих чисел: 60, 366, 1970, вашего почтового индекса.

3. Какое натуральное число (или числа), не превосходящее 100, имеет наибольшее количество делителей

§ 3. Несколько задач о делителях

Существует единственное число n = 1, которое имеет только один делитель. Числами с ровно двумя делителями являются простые числа n = р: они делятся на 1 и на р. Наименьшим числом, имеющим два делителя, является, таким образом, р = 2.

Исследуем числа, имеющие ровно 3 делителя. В соответствии с (3.2.3) имеем

3 = (α1 + 1) (α2 + 1)… (αr + 1).

Так как 3 — простое число, то справа может существовать лишь один множитель, не равный 1. Отсюда r = 1, a α1 = 2. Таким образом,

n = p12.

Наименьшим числом с 3 делителями является n = 22 = 4. Это соображение, примененное к общему случаю, когда число делителей q является простым числом, позволяет получить, что

q = α1 + 1, т. е. α1 = q — 1 и n = р1q-1;

наименьшим из таких чисел является

n = 2q-1.

Рассмотрим следующий случай, когда существует ровно 4 делителя. Тогда соотношение

4 = (α1 + 1) (α2 + 1),

возможно только тогда, когда

α1 = 3, α2 = 0 или α1 = α2 = 1.

Это приводит к двум возможностям:

n = p13, n = p1  p2;

наименьшее число с 4 делителями — это n = 6.

В том случае, когда имеется 6 делителей, должно выполняться соотношение

6 = (α1 + 1) (α2 + 1),

что возможно лишь тогда, когда

α1 = 5, α2 = 0 или α1 = 2, α2 = 1.

Это дает две возможности:

n = p15, n = p12 p2;

при этом наименьшее значение имеет место в последнем случае, когда

p1 = 2, p2 = 3, n =12.

Этот метод можно использовать для вычисления наименьших натуральных чисел, имеющих любое заданное количество делителей.

Существуют таблицы, указывающие количество делителей для различных чисел. Они начинаются следующим образом:

Вы легко можете ее самостоятельно продолжить.

Будем говорить, что натуральное число n является сверхсоставным, если количество делителей у каждого числа, меньшего n, меньше, чем количество делителей у числа n. Глядя на нашу небольшую таблицу, мы видим, что

1, 2, 4, 6, 12

являются первыми пятью сверхсоставными числами. О свойствах этих чисел известно еще очень мало.

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

1. Взвод из 12 солдат может маршировать 6-ю различными способами: 12 × 1, 6 × 2, 4 × 3, 3 × 4, 2 × 6, 1 × 12. Какую наименьшую численность должны иметь группы людей, которые могут маршировать 8, 10, 12 и 72 способами?

2. Найдите наименьшие натуральные числа, имеющие: а) 14 делителей, б) 18 делителей ив) 100 делителей.

3. Найдите два первых сверхсоставных числа, следующих за числом 12.

4. Охарактеризуйте все натуральные числа, количество делителей которых является произведением двух простых чисел.

§ 4. Совершенные числа

Нумерология (или гематрия, как ее иногда еще называют) была распространенным увлечением у древних греков. Естественным объяснением этому является то, что числа в Древней Греции изображались буквами греческого алфавита, и поэтому каждому написанному слову, каждому имени соответствовало некоторое число. Люди могли сравнивать свойства чисел, соответствующих их именам.

Делители или аликвотные части[6] чисел играли важную роль в нумерологии. В этом смысле идеальными, или, как их называют, совершенными числами являлись такие числа, которые составлялись из своих аликвотиых частей, т. е. равнялись сумме своих делителей. Здесь следует отметить, что древние греки не включали само число в состав его делителей.

Наименьшим совершенным числом является 6:

6 = 1 + 2 + 3.

За ним следует число 28:

28 = 1 + 2 + 4 + 7 + 14,

далее число 496:

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.

Часто математик, увлеченный решением какой-либо проблемы и имеющий одно или несколько частных решений этой задачи, пытается найти закономерности, которые смогли бы дать ключ к нахождению общего решения. Указанные нами совершенные числа могут быть записаны в виде

6 = 2  3 = 2(22 — 1),

28 = 22  7 = 22(23 — 1),

496 = 24  31 = 24(25 — 1).

Это наталкивает нас на гипотезу:

Число является совершенным, если оно представляется в виде

Р = 2p-1(2p — 1) = 2р q, (3.4.1)

где

q = 2p — 1

является простым числом Мерсенна.

Этот результат, известный еще грекам, несложно доказать. Делителями числа Р, включая само число Р, очевидно, являются следующие числа:

1, 2, 22…, 2р-1,

q, 2q, 22q…, 2р-1q.

Запишем сумму этих делителей

1 + 2 +… + 2р-1 + q(1 + 2 +… + 2р-1),

которая равна

(1 + 2 +… + 2р-1)(q + 1) = (1 + 2 +… + 2р-1) 2р

Если вы не помните формулы для суммы членов геометрической прогрессии,

S = 1 + 2 +… + 2р-1,

то умножьте эту сумму на 2:

2S = 2 + 22 +… +2р-1 + 2р,

а затем, вычтя S, получите

S = 2p — 1 = q.

Таким образом, сумма всех делителей числа Р есть

2pq = 2 • 2p-1q,

а сумма всех делителей, кроме самого числа Р = 2p-1q, равна

2 2p-1q — 2p-1q = 2p-1q = Р.

Итак, наше число является совершенным.

Из этого результата следует, что каждое простое число Мерсенна порождает совершенное число. В § 2 второй главы говорилось, что известно всего 23 простых числа Мерсенна, следовательно, мы знаем также и 23 совершенных числа. Существуют ли другие виды совершенных чисел? Все совершенные числа вида (3.4.1) являются четными, можно доказать, что любое четное совершенное число имеет вид (3.4.1). Остается вопрос: существуют ли нечетные совершенные числа? В настоящее время мы не знаем ни одного такого числа, и вопрос о существовании нечетных совершенных чисел является одной из самых знаменитых проблем теории чисел. Если бы удалось обнаружить такое число, то это было бы крупным достижением. Вы можете поддаться соблазну найти такое число, перебирая различные нечетные числа. Но мы не советуем этого делать, так как по последним сообщениям Брайена Такхермана из IBM[7] (1968), нечетное совершенное число должно иметь по крайней мере 36 знаков.

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

1. Используя список простых чисел Мерсенна, найдите четвертое и пятое совершенные числа.

§ 5. Дружественные числа

Дружественные числа также входят в наследство, доставшееся нам от греческой нумерологии. Если у двух людей имена были таковы, что их числовые значения удовлетворяли следующему условию: сумма частей (делителей) одного из них равнялась второму числу, и наоборот, то считалось, что это свидетельствует об их духовной близости. В действительности греки знали всего лишь одну пару таких чисел, а именно:

220 = 22 • 5 • 11, 284 = 22 • 71.

Суммами их делителей являются соответственно

1 + 2 + 4 + 5 +10 + 20 + 11 + 22 + 44 + 55 + 110 = 284,

1 + 2 + 4 + 71 + 142 = 220.

Эта пара дружественных чисел оставалась единственной известной до тех пор, пока Пьеру Ферма не удалось найти следующую пару: