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

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

a) любое натуральное число либо взаимно просто с заданным простым числом $p$, либо делится на $p$;

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

Пусть $n$ — произвольное натуральное число, а $p$ — заданное простое число. Рассмотрим их наибольший общий делитель (НОД), который обозначим как $d = \text{НОД}(n, p)$.

По определению НОД, число $d$ является делителем как числа $n$, так и числа $p$. Поскольку $p$ — простое число, его натуральными делителями могут быть только $1$ и само число $p$. Следовательно, для $d$ существуют только две возможности:

1. $d = 1$. В этом случае $\text{НОД}(n, p) = 1$. По определению, это означает, что числа $n$ и $p$ являются взаимно простыми.
2. $d = p$. В этом случае $\text{НОД}(n, p) = p$. Так как $d$ является также и делителем числа $n$, то отсюда следует, что $p$ является делителем числа $n$. Это означает, что $n$ делится на $p$ без остатка.

Таким образом, для любого натурального числа $n$ и простого числа $p$ выполняется ровно одно из двух утверждений: либо они взаимно просты, либо $n$ делится на $p$. Что и требовалось доказать.

Ответ: Утверждение доказано.

Это утверждение известно как лемма Евклида. Докажем его методом математической индукции по количеству множителей. Пусть произведение $N = a_1 \cdot a_2 \cdot \ldots \cdot a_k$ делится на простое число $p$.

База индукции (k=2):
Докажем, что если произведение $a_1 \cdot a_2$ делится на $p$, то либо $a_1$ делится на $p$, либо $a_2$ делится на $p$.

Пусть $p | (a_1 \cdot a_2)$. Предположим, что множитель $a_1$ не делится на $p$. Согласно утверждению, доказанному в пункте а), если натуральное число $a_1$ не делится на простое число $p$, то оно взаимно просто с $p$. То есть, $\text{НОД}(a_1, p) = 1$.

Существует свойство делимости (следствие из тождества Безу): если произведение двух чисел делится на простое число, и одно из этих чисел взаимно просто с ним, то второе число должно делиться на это простое число. Формально: если $p | (a_1 \cdot a_2)$ и $\text{НОД}(a_1, p) = 1$, то $p | a_2$. Таким образом, если $a_1$ не делится на $p$, то $a_2$ обязательно делится на $p$. Следовательно, хотя бы один из множителей ($a_1$ или $a_2$) делится на $p$. База индукции доказана.

Шаг индукции:
Предположим, что утверждение верно для произведения из $k-1$ множителей. То есть, если $p | (a_1 \cdot \ldots \cdot a_{k-1})$, то существует $i \in \{1, \ldots, k-1\}$ такое, что $p | a_i$.

Теперь рассмотрим произведение из $k$ множителей $N = a_1 \cdot a_2 \cdot \ldots \cdot a_k$, которое делится на $p$. Представим это произведение в виде $(a_1 \cdot a_2 \cdot \ldots \cdot a_{k-1}) \cdot a_k$. Обозначим $B = a_1 \cdot a_2 \cdot \ldots \cdot a_{k-1}$. Тогда имеем $p | (B \cdot a_k)$.

Согласно доказанной базе индукции (для двух множителей $B$ и $a_k$), из того, что $p | (B \cdot a_k)$, следует, что либо $p | B$, либо $p | a_k$.

• Если $p | a_k$, то мы нашли множитель, делящийся на $p$, и утверждение доказано.
• Если $p | B$, то это означает, что $p | (a_1 \cdot a_2 \cdot \ldots \cdot a_{k-1})$. По нашему индукционному предположению, в этом случае хотя бы один из множителей $a_1, a_2, \ldots, a_{k-1}$ должен делиться на $p$.

В обоих случаях мы приходим к выводу, что хотя бы один из множителей $a_1, a_2, \ldots, a_k$ делится на $p$. По принципу математической индукции, утверждение доказано для любого натурального количества множителей $k \ge 2$.

Ответ: Утверждение доказано.