Алгебра

Глава 1. Натуральные числа

1.4. Делитель и кратное. Простые и составные числа

Теорема 1 (Евклида)

Множество положительных простых чисел бесконечно.

Доказательство:

Предположим, что множество положительных простых чисел конечно и состоит из чисел p_1, p_2, ... , p_k. Рассмотрим число p= p_1\cdot p_2 \cdot ... \cdot p_k+1 . Тогда либо натуральное число p, большее единицы, само является простым, либо оно разложимо в произведение положительных простых чисел и поэтому обладает хотя бы одним простым делителем. По предположению p не может быть простым, так оно не совпадает ни с одним из чисел p_1, p_2, ... , p_k. Если же p разложимо, то его делитель должен быть отличен от чисел p_1, p_2, ... , p_k, так как в противном случае этот делитель делит числа p_1\cdot p_2 \cdot ... \cdot p_k и p , а значит делит и разность p-p_1\cdot p_2 \cdot ... \cdot p_k=1, а это невозможно. Следовательно, простых чисел бесконечно.

Теорема доказана.

Теорема 2

Для любого целого числа k \geq 1 в натуральном ряду можно найти k составных чисел, непосредственно следующих друг за другом.

Доказательство:

Возьмем число n = (k+1)! и рассмотрим k следующих друг за другом чисел n_1= n+2, n_2=n+3, … , n_k = n+ (k+1). Каждое число в этом списке является составным, так как n_1 делится на 2, n_2 делится на 3, n_3 делится на 4, … , n_k делится на k+1.

Теорема доказана.

Определение

Каноническим разложением натурального числа n>1 называется представление n в виде n=p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_s^{k_s}, где p_1, p_2, ... , p_s — попарно различные простые числа, а k_1, k_2, ... , k_s — натуральные числа. Для отрицательных целых чисел n каноническим разложением считается представление в виде n=-p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_s^{k_s} .

Пусть число p — наименьший среди простых делителей p_1, p_2, ... , p_s . Тогда n=p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_s^{k_s}\geq p^2. Отсюда, p \leq \sqrt {n} . Следовательно, если n — составное число, то оно имеет простой делитель p такой, что p \leq \sqrt {n} . Если число n не имеет простых делителей, не превосходящих \sqrt{n} , то n — простое число.

Теорема 3

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

Доказательство:

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

Теорема доказана.

Определение

Представление натурального числа n в виде произведения двух натуральных чисел ab называется разложением на множители.

Определение

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

Считается, что если n — простое число, то оно имеет разложение на простые множители, состоящее из одного числа n . Два разложения на множители называются одинаковыми, если они отличаются только порядком множителей. Например, разложения 42= 2 \cdot 3\cdot 7 и 42= 7 \cdot 2\cdot 3 считаются одинаковыми.

Теорема 4 ( основная теорема арифметики)

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

Пример 1

Сколько существует способов разложения числа n=p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_s^{k_s} в произведение двух взаимно простых множителей?

Решение:

Пусть имеется разложение n=n_1 \cdot n_2, где числа n_1 и n_2 — взаимно просты, т.е. (n_1 ,n_2 )= 1 . Это будет возможно в случае, когда эти числа не содержат ни одного общего множителя p_i (1 \leq i \leq s ). Поэтому искомое количество способов разложения будет равно количеству способов разбиения множества чисел { p_1, p_2 , ... , p_s} на две непересекающиеся группы.

Рассмотрим строчки все строки( , , ... , ) из S позиций, в которых в i -й позиции стоит 1, если p_i входит в множитель n_1, и 0, если p_i входит в множитель n_2 . Для заполнения каждой позиции имеется 2 способа. Всего s позиций. Две позиции можно заполнить 2 \cdot 2 = 2^2 способами, три – 2 \cdot 2 \cdot 2 = 2^3 способами и т.д. Соответственно, всего имеется 2^s различных строчек. Исключая строчки из одних 1 (в этом случае n_1=n ) и одних 0 (в этом случае n_2= n), получаем искомое число, равное 2^s- 2 .

Ответ:

2^s-2.