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

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 4• 3 2• 5 2.

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

n = p 1 α 1 • p 2 α 2 • …. • р r α r , (3.2.1)

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

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

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

3600 = d • d 1.

Приведенное разложение на простые множители показывает, что единственными числами среди множителей числа 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 • d 1

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

d = p 1 δ 1• p 2 δ 2 • …. • р r α r , (3.2.2)

Простое число p 1может содержаться не более α 1 раз, как и в самом числе n ; аналогично — для p 2и других простых чисел. Это значение для числа δ 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, имеет наибольшее количество делителей

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

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

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

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

n = p 1 2.

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