Выше мы отмечали, что единственность разложения числа на простые множители совсем не очевидна. В действительности, существуют «арифметики», в которых аналогичная теорема не выполняется. Простейшим примером такой арифметики может служить арифметика четных чисел
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. В каких случаях четные числа обладают единственным разложением на четно-простые множители?
§ 2. Делители
Разложим на множители какое-нибудь число, скажем, 3600. Это разложение
3600 = 2 • 2 • 2 • 2 • 3 • 3 • 5 • 5
может быть записано как
3600 = 24 • 32 • 52.
Вообще при разложении числа n на множители аналогично можно собирать одинаковые простые множители в виде степеней и записывать
n = p1α1 • p2α2 • …. • рrαr, (3.2.1)
где p1, p2 …. рr — различные простые множители числа n, причем число p1 входит α1 раз, p2 входит α2 раз и т. д.
Если мы знаем вид (3.2.1) для числа, то мы сможем тотчас же ответить на некоторые вопросы об этом числе.
Например, если мы захотим, то можем узнать, какие числа делят число n. Возьмем для примера рассмотренное выше число 3600. Предположим, что число d является одним из его делителей, т. е.
3600 = d • d1.
Приведенное разложение на простые множители показывает, что единственными числами среди множителей числа d будут лишь 2, 3, 5. Кроме того, число 2 может содержаться не более 4 раз, а числа 3 и 5 не более, чем по 2 раза каждое. Итак, мы видим, что возможными делителями числа 3600 будут числа вида
d = 2δ1 • 3δ2 • 5δ3,
при этом показатели степени могут принимать значения:
δ1 = 0, 1, 2, 3, 4;
δ2 = 0, 1, 2;
δ3 = 0, 1, 2.
Так как эти значения могут сочетаться всеми возможными способами, то число делителей равно
(4 + 1)•(2 + 1)•(2 + 1) = 5 • 3 • 3 = 45.
Для любого числа n, разложение которого на простые множители дается формулой (3.2.1), положение точно такое же. Если число d является делителем числа n, т. е.
n = d • d1
то единственными простыми числами, на которые может делиться число d, будут только те, которые делят число n, а именно: p1…, рr. Таким образом, мы можем записать разложение числа d на простые множители в виде
d = p1δ1 • p2δ2 • …. • рrαr, (3.2.2)
Простое число p1 может содержаться не более α1 раз, как и в самом числе n; аналогично — для p2 и других простых чисел. Это значение для числа δ1 мы можем выбрать α1 + 1 способом:
δ1 = 0, 1…, α1;
аналогично и для других простых чисел. Так как каждое из α1 + 1 значений, которые может принимать число δ1, может сочетаться с любым из α2 + 1 возможных значений числа δ2 и т. д., то мы видим, что общее число делителей числа n задается формулой
τ(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.
Этот метод можно использовать для вычисления наименьших натуральных чисел, имеющих любое заданное количество делителей.
Существуют таблицы, указывающие количество делителей для различных чисел. Они начинаются следующим образом: