Любое составное число с может быть записано в виде произведения с = ab, причем ни один из делителей не равен 1 и каждый из них меньше, чем с; например,

72 = 8 • 9, 150 = 10 • 15.

При разложении числа с на множители один из них, и даже оба (а и b) могут оказаться составными. Если а — составное, то разложение на множители можно продолжить:

а = a₁ • a₂, с = a₁ • a₂ • b.

Примерами этого могут служить рассмотренные выше числа

72 = 2 • 4 • 9, 150 = 2 • 5 • 15.

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

Таким образом мы показали, что

Каждое целое число, большее 1, является простым числом или произведением простых чисел.

Последовательное разложение числа на множители может быть выполнено многими способами. При этом можно использовать таблицу делителей. Сначала найдем наименьшее простое число р₁, делящее число с, так что с = р₁с₁. Если с₁ — составное число, то по таблице делителей найдем наименьшее простое число р₂, делящее с₁, так что

c₁ = р₂ • с₂,   c = p₁ • p₂ • с₂.

Затем найдем наименьший простой делитель числа с₂ и т. д.

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

Этот результат мы можем кратко выразить следующим образом:

разложение числа на простые множители единственно.

Возможно, что вы так часто слышали об этой так называемой «основной теореме арифметики» и пользовались ею, что она представляется вам очевидной, но это совсем не так. Эта теорема может быть доказана несколькими различными способами, однако ни один из них не тривиален. Здесь мы приведём доказательство, используя способ «от противного», который часто называют его латинским названием reductio ad absurdum (приведением к абсурду). Этот способ заключается в следующем: предположив ложность теоремы, которую нужно доказать, показывают, что это предположение приводит к противоречию.

Доказательство. Предположим, что наша теорема о единственности разложения на множители неверна. Тогда должны существовать числа, имеющие по крайней мере два различных разложения на простые множители. Выберем из них наименьшее и обозначим его через с₀. Для небольших чисел, скажем, меньших 10, истинность теоремы можно установить прямой проверкой. Число с₀ имеет наименьший простой множитель р₀, и мы можем записать:

c₀ = p₀ d₀.

Так как d₀ < c₀, то число d₀ единственным образом раскладывается на простые множители. Отсюда следует, что разложение числа c₀ на простые множители, содержащее число р₀, единственно.

А так как, по предположению, имеется по крайней мере два разложения числа c₀ на простые множители, то должно быть разложение, не содержащее число р₀. Наименьшее простое число в этом разложении мы обозначим через р₁ и запишем

c₀ = p₁ d₁. (3.1.1)

Так как p₁ > p₀, то d₁ < d₀ и, следовательно, p₀ d₁ < c₀. Рассмотрим число

c₀' = c₀ — p₀ d₁ = (p₁ - p₀) • d₁. (3.1.2)

Так как оно меньше, чем число c₀, то оно должно раскладываться на простые множители единственным способом; при этом простые множители числа c₀ состоят из простых множителей чисел p₁ - p₀ и d₁. Так как число c₀ делится на p₀, то из выражения (3.1.2) следует, что число c₀' также делится на p₀. Следовательно, p₀ должно быть делителем либо числа d₁, либо p₁ - p₀. Но любой простой делитель числа d₁ больше, чем p₀, так как p₁ — наименьшее простое число в разложении (3.1.1). Таким образом, остается единственная возможность: p₀ должно быть делителем числа p₁ - p₀ и, следовательно, оно делит p₁. Итак, мы пришли к противоречию, потому что p₁ является простым числом и не может делиться на другое простое число p₀.

Выше мы отмечали, что единственность разложения числа на простые множители совсем не очевидна. В действительности, существуют «арифметики», в которых аналогичная теорема не выполняется. Простейшим примером такой арифметики может служить арифметика четных чисел

2, 4, 6, 8, 10, 12…

Некоторые из них могут быть разложены на два четных множителя, а другие — нет; последние мы называем чётно-простыми числами. Это числа, которые делятся на 2, но не делятся на 4:

2, 6, 10, 14, 18….

Очевидно, что каждое четное число либо является четно-простым, либо записывается в виде произведения чётно-простых чисел. Но такое разложение на чётно-простые числа не всегда будет единственным. Например, число 420 может быть разложено на четно-простые числа различными способами:

420 = 6 • 70 = 10 • 42 = 14 • 30.

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

1. Найдите разложение на простые множители каждого из чисел 120, 365, 1970.

2. Проделайте то же самое для чисел, указанных в задаче 1 системы задач 2.1 (стр. 25).

3. Запишите все разложения числа 360 на чётно-простые числа.

4. В каких случаях четные числа обладают единственным разложением на четно-простые множители?

Разложим на множители какое-нибудь число, скажем, 3600. Это разложение

3600 = 2 • 2 • 2 • 2 • 3 • 3 • 5 • 5

может быть записано как

3600 = 2⁴ • 3² • 5².

Вообще при разложении числа n на множители аналогично можно собирать одинаковые простые множители в виде степеней и записывать

n = p₁^α₁ • p₂^α₂ • …. • р_r^α_r, (3.2.1)

где p₁, p₂ …. р_r — различные простые множители числа n, причем число p₁ входит α₁ раз, p₂ входит α₂ раз и т. д.

Если мы знаем вид (3.2.1) для числа, то мы сможем тотчас же ответить на некоторые вопросы об этом числе.

Например, если мы захотим, то можем узнать, какие числа делят число n. Возьмем для примера рассмотренное выше число 3600. Предположим, что число d является одним из его делителей, т. е.

3600 = d • d₁.

Приведенное разложение на простые множители показывает, что единственными числами среди множителей числа d будут лишь 2, 3, 5. Кроме того, число 2 может содержаться не более 4 раз, а числа 3 и 5 не более, чем по 2 раза каждое. Итак, мы видим, что возможными делителями числа 3600 будут числа вида

d = 2^δ₁ • 3^δ₂ • 5^δ₃,

при этом показатели степени могут принимать значения:

δ₁ = 0, 1, 2, 3, 4;

δ₂ = 0, 1, 2;

δ₃ = 0, 1, 2.

Так как эти значения могут сочетаться всеми возможными способами, то число делителей равно

(4 + 1)•(2 + 1)•(2 + 1) = 5 • 3 • 3 = 45.

Для любого числа n, разложение которого на простые множители дается формулой (3.2.1), положение точно такое же. Если число d является делителем числа n, т. е.

n = d • d₁

то единственными простыми числами, на которые может делиться число d, будут только те, которые делят число n, а именно: p₁…, р_r. Таким образом, мы можем записать разложение числа d на простые множители в виде

d = p₁^δ₁ • p₂^δ₂ • …. • р_r^α_r, (3.2.2)

Простое число p₁ может содержаться не более α₁ раз, как и в самом числе n; аналогично — для p₂ и других простых чисел. Это значение для числа δ₁ мы можем выбрать α₁ + 1 способом:

δ₁ = 0, 1…, α₁;

аналогично и для других простых чисел. Так как каждое из α₁ + 1 значений, которые может принимать число δ₁, может сочетаться с любым из α₂ + 1 возможных значений числа δ₂ и т. д., то мы видим, что общее число делителей числа n задается формулой

τ(n) = (α₁ + 1) (α₂ + 1)… (α_r + 1). (3.2.3)

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

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

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

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

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

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

3 = (α₁ + 1) (α₂ + 1)… (α_r + 1).

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

n = p₁².

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

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

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

n = 2^q-1.

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

4 = (α₁ + 1) (α₂ + 1),

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

α₁ = 3, α₂ = 0 или α₁ = α₂ = 1.

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

n = p₁³, n = p₁  p₂;

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

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

6 = (α₁ + 1) (α₂ + 1),

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

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

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

n = p₁⁵, n = p₁² p₂;

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

p₁ = 2, p₂ = 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. Охарактеризуйте все натуральные числа, количество делителей которых является произведением двух простых чисел.

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

Делители или аликвотные части[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(2² — 1),

28 = 2²  7 = 2²(2³ — 1),

496 = 24  31 = 2⁴(2⁵ — 1).

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

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

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

где

q = 2^p — 1

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

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

1, 2, 2²…, 2^р-1,

q, 2q, 2²q…, 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 + 2² +… +2^р-1 + 2^р,

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

S = 2^p — 1 = q.

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

2^pq = 2 • 2^p-1q,

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

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

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

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

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

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

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

220 = 2² • 5 • 11, 284 = 2² • 71.

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

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

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

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

17 296 = 2⁴ • 23 • 47, 18 416 = 2⁴ • 1151.

Поиски пар дружественных чисел чрезвычайно удобно вести с помощью ЭВМ. Для каждого числа n при помощи машины определяются все делители этого числа (≠ n) и их сумма m. После этого производится такая же операция с числом m. Если при этом вновь получается первоначальное число n, то пара чисел (n, m) оказывается дружественной. Недавно этим способом в Йельском университете на ЭВМ IBM 7094 были проверены все числа до одного миллиона. В результате была получена коллекция из 42 пар дружественных чисел; некоторые из них оказались ранее неизвестными. Все пары дружественных чисел до 100 000 приведены в табл. 2. При помощи этого метода, как нетрудно видеть, одновременно «вылавливаются» и совершенные числа. Если возникает желание продолжать поиски дальше, то, конечно, это можно сделать, но придется затратить большое количество машинного времени.

Таблица 2

Дружественные числа до 100 000

В действительности мы очень мало знаем о свойствах пар дружественных чисел, однако, можно на основе наших таблиц высказать несколько предположений. Например, отношение одного из них к другому, по-видимому, должно все больше и больше приближаться к 1 по мере того, как они увеличиваются. Из таблицы видно, что эти числа бывают либо оба четными, либо оба нечетными, но не было найдено случая, когда одно число четно, а другое нечетно, хотя поиски дружественных чисел такого вида были проведены среди всех чисел n ≤ 1 3 000 000 000.

Примечания:

6

Аликвотные дроби — дроби вида 1/n; в древности было принято всякую дробь представлять в виде суммы аликвотных дробей. Например, 5/12 = 1/12 + 1/3. (Прим. перев.)

7

Американская фирма, выпускающая вычислительное оборудование. (Прим. перев.)