Приглашение в теорию чисел

ОРЕ О.

Так как оно меньше, чем число 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. В каких случаях четные числа обладают единственным разложением на четно-простые множители?

§ 2. Делители

Разложим на множители какое-нибудь число, скажем, 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 задается формулой