Номер 1.36, страница 25, часть 2 - гдз по алгебре 10 класс учебник Мордкович, Семенов

1.36. Докажите, что:

а) наименьший отличный от 1 делитель натурального числа n, большего 1, есть простое число;

б) наименьший отличный от 1 делитель составного числа n не больше $\sqrt{n}$;

в) если $p_1 < p_2 < \dots < p_n$ — простые числа, то число $p_1 p_2 \dots p_n + 1$ является либо простым числом, либо делится на простое число $p$, большее чем $p_n$;

г) простых чисел бесконечно много.

а) Доказательство проведем от противного. Пусть $n$ — натуральное число, большее 1, и пусть $d$ — его наименьший делитель, отличный от 1. Предположим, что $d$ не является простым числом. Поскольку $d > 1$, это означает, что $d$ — составное число.

По определению составного числа, у $d$ существует делитель $k$, такой что $1 < k < d$. Так как $k$ является делителем $d$, а $d$ является делителем $n$, то $k$ также является делителем $n$ (если $n = d \cdot m$ и $d = k \cdot l$, то $n = (k \cdot l) \cdot m = k \cdot (l \cdot m)$).

Таким образом, мы нашли делитель $k$ числа $n$, который удовлетворяет неравенству $1 < k < d$. Это противоречит нашему первоначальному условию, что $d$ является наименьшим делителем числа $n$, отличным от 1.

Следовательно, наше предположение о том, что $d$ является составным числом, неверно. Значит, $d$ должно быть простым числом.

Ответ: наименьший отличный от 1 делитель натурального числа $n > 1$ является простым числом, что и требовалось доказать.

б) Пусть $n$ — составное число. По определению, оно имеет хотя бы один делитель, отличный от 1 и самого себя. Пусть $p$ — наименьший отличный от 1 делитель числа $n$. Из пункта а) мы знаем, что $p$ является простым числом.

Поскольку $p$ — делитель $n$, мы можем записать $n = p \cdot k$, где $k$ — некоторое целое число. Так как $n$ — составное, то $k > 1$.

Поскольку $p$ — наименьший делитель числа $n$, то любой другой делитель (в частности, $k$) должен быть не меньше $p$. Таким образом, $k \ge p$. Если бы было $1 < k < p$, то $k$ был бы делителем $n$, меньшим чем $p$, что противоречит определению $p$.

Умножим обе части неравенства $k \ge p$ на $p$. Так как $p > 1$, знак неравенства сохранится: $p \cdot k \ge p \cdot p$.

Подставляя $n = p \cdot k$, получаем $n \ge p^2$.

Извлекая квадратный корень из обеих частей этого неравенства, получаем $\sqrt{n} \ge p$, или $p \le \sqrt{n}$.

Ответ: наименьший отличный от 1 делитель составного числа $n$ не больше $\sqrt{n}$, что и требовалось доказать.

в) Пусть даны простые числа $p_1 < p_2 < \dots < p_n$. Рассмотрим число $N = p_1 p_2 \dots p_n + 1$. Согласно основной теореме арифметики, число $N$ (которое очевидно больше 1) имеет хотя бы один простой делитель. Обозначим этот простой делитель как $p$.

Рассмотрим два возможных случая:

1. Число $N$ само является простым. В этом случае его единственный простой делитель это $p=N$. Очевидно, что $N = p_1 p_2 \dots p_n + 1 > p_n$. Таким образом, $N$ является простым числом, большим чем $p_n$.

2. Число $N$ является составным. Тогда у него существует простой делитель $p$. Покажем, что $p$ не может быть равен ни одному из чисел $p_1, p_2, \dots, p_n$. При делении $N$ на любое из этих чисел $p_i$ (для $1 \le i \le n$), мы получаем в остатке 1, так как произведение $p_1 p_2 \dots p_n$ делится на $p_i$ нацело. Следовательно, $p$ не может быть ни одним из $p_1, p_2, \dots, p_n$.

Таким образом, любой простой делитель $p$ числа $N$ не входит в список $p_1, \dots, p_n$. Поскольку $p_1 < p_2 < \dots < p_n$ - это упорядоченный список, то любой простой делитель $p$ числа $N$ должен быть больше $p_n$, если предположить, что в списке $\{p_1, \dots, p_n\}$ содержатся все простые числа до $p_n$. В контексте доказательства бесконечности простых чисел это стандартное допущение.

Следовательно, в любом случае число $N$ либо само является простым (и большим, чем $p_n$), либо делится на простое число $p$, которое больше $p_n$.

Ответ: число $p_1 p_2 \dots p_n + 1$ является либо простым числом, либо делится на простое число $p$, большее чем $p_n$, что и требовалось доказать.

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

Предположим, что множество простых чисел конечно. Это означает, что существует конечное число простых чисел, и мы можем их все перечислить: $p_1, p_2, \dots, p_n$, где $p_n$ — самое большое простое число.

Теперь построим число $N$, равное произведению всех этих простых чисел плюс единица: $N = p_1 p_2 \dots p_n + 1$.

Число $N$ больше 1, поэтому оно должно иметь хотя бы один простой делитель (согласно утверждению из пункта а)). Назовем этот простой делитель $p$.

По нашему предположению, $p$ должен быть одним из чисел в нашем списке $\{p_1, p_2, \dots, p_n\}$, так как мы предположили, что этот список содержит все простые числа.

Однако, как следует из пункта в), число $N$ не делится ни на одно из простых чисел $p_1, p_2, \dots, p_n$. Следовательно, его простой делитель $p$ не может находиться в этом списке. Более того, из пункта в) следует, что $p$ должен быть больше $p_n$.

Это приводит к противоречию. Мы нашли простое число $p$, которое больше предполагаемого самого большого простого числа $p_n$. Наше исходное предположение о том, что множество простых чисел конечно, было неверным.

Ответ: простых чисел бесконечно много, что и требовалось доказать.