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

1.29. В числе $233\Box4$ заполните пропуск такой цифрой, чтобы:

а) число делилось на 4;

б) число делилось на 12.

а) число делилось на 4;

Согласно признаку делимости на 4, число делится на 4 тогда и только тогда, когда число, образованное двумя его последними цифрами, делится на 4.

В нашем числе 233?4, которое можно записать как $233x4$, где $x$ — неизвестная цифра, две последние цифры образуют число $x4$.

Нам необходимо найти все цифры $x$ (от 0 до 9), при которых двузначное число $x4$ будет делиться на 4. Переберем все возможные варианты:
- если $x=0$, число 04 делится на 4 ($4 \div 4 = 1$);
- если $x=1$, число 14 не делится на 4;
- если $x=2$, число 24 делится на 4 ($24 \div 4 = 6$);
- если $x=3$, число 34 не делится на 4;
- если $x=4$, число 44 делится на 4 ($44 \div 4 = 11$);
- если $x=5$, число 54 не делится на 4;
- если $x=6$, число 64 делится на 4 ($64 \div 4 = 16$);
- если $x=7$, число 74 не делится на 4;
- если $x=8$, число 84 делится на 4 ($84 \div 4 = 21$);
- если $x=9$, число 94 не делится на 4.

Таким образом, подходящими цифрами являются 0, 2, 4, 6 и 8.

Ответ: 0, 2, 4, 6, 8.

б) число делилось на 12.

Число делится на 12, если оно одновременно делится и на 3, и на 4 (поскольку $12 = 3 \times 4$, а числа 3 и 4 взаимно простые).

Из пункта а) мы уже знаем, что для делимости на 4 на месте пропуска могут стоять цифры 0, 2, 4, 6 или 8.

Теперь проверим условие делимости на 3. Число делится на 3, если сумма его цифр делится на 3. Найдем сумму цифр числа $233x4$:
$S = 2 + 3 + 3 + x + 4 = 12 + x$.

Сумма $12 + x$ должна быть кратна 3. Поскольку 12 делится на 3, то и $x$ должен делиться на 3. Среди цифр от 0 до 9 на 3 делятся 0, 3, 6, 9.

Для того чтобы число $233x4$ делилось на 12, необходимо, чтобы выполнялись оба условия. Найдем цифры, которые удовлетворяют и первому, и второму условию:
- цифры для делимости на 4: {0, 2, 4, 6, 8};
- цифры для делимости на 3: {0, 3, 6, 9}.

Общими для обоих наборов являются цифры 0 и 6.

Проверим найденные решения:
- При $x=0$ получаем число 23304. Сумма цифр 12, делится на 3. Последние цифры 04, делятся на 4. Значит, 23304 делится на 12. ($23304 \div 12 = 1942$).
- При $x=6$ получаем число 23364. Сумма цифр 18, делится на 3. Последние цифры 64, делятся на 4. Значит, 23364 делится на 12. ($23364 \div 12 = 1947$).

Следовательно, пропуск можно заполнить цифрой 0 или 6.

Ответ: 0, 6.

1.30. В числе 735□4 заполните пропуск такой цифрой, чтобы:

а) число при делении на 3 давало в остатке 2;

б) число при делении на 4 давало в остатке 2.

а) Обозначим пропущенную цифру через $x$. Тогда мы имеем число $735x4$. Согласно признаку делимости, остаток от деления числа на 3 равен остатку от деления суммы его цифр на 3. Сумма цифр нашего числа равна $S = 7 + 3 + 5 + x + 4 = 19 + x$. По условию задачи, число должно давать остаток 2 при делении на 3. Следовательно, сумма его цифр $19 + x$ также должна давать остаток 2 при делении на 3. Это означает, что выражение $(19 + x) - 2$, то есть $17 + x$, должно быть кратно 3. Переберем все возможные значения $x$ от 0 до 9 и найдем те, при которых сумма $17 + x$ делится на 3. Подходящие значения:
• при $x=1$, $17+1=18$, что кратно 3 ($18 = 3 \cdot 6$);
• при $x=4$, $17+4=21$, что кратно 3 ($21 = 3 \cdot 7$);
• при $x=7$, $17+7=24$, что кратно 3 ($24 = 3 \cdot 8$).
Другие цифры не подходят. Таким образом, пропуск можно заполнить цифрами 1, 4 или 7.

Ответ: 1, 4, 7.

б) Рассматриваем число $735x4$. Остаток от деления любого числа на 4 зависит только от числа, образованного его двумя последними цифрами. В данном случае это число $x4$, которое можно записать в виде $10x + 4$. По условию, это число должно давать остаток 2 при делении на 4. Запишем это математически: $(10x + 4) \pmod 4 = 2$. Поскольку слагаемое 4 делится на 4 без остатка, то остаток всей суммы зависит только от слагаемого $10x$. Таким образом, условие сводится к $10x \pmod 4 = 2$. Представим $10x$ в виде $8x + 2x$. Так как $8x$ всегда делится на 4 (поскольку 8 делится на 4), остаток выражения $8x + 2x$ при делении на 4 будет таким же, как и остаток от деления $2x$ на 4. Значит, нам нужно найти такие цифры $x$, для которых $2x$ дает остаток 2 при делении на 4. Переберем значения $x$ от 0 до 9:
• если $x$ - четное число (0, 2, 4, 6, 8), то $2x$ будет кратно 4, и остаток будет 0.
• если $x$ - нечетное число (1, 3, 5, 7, 9), то $2x$ не будет кратно 4, и остаток будет 2. Например, при $x=1$, $2 \cdot 1=2$, остаток 2; при $x=3$, $2 \cdot 3=6$, остаток 2; при $x=5$, $2 \cdot 5=10$, остаток 2, и так далее.
Следовательно, подходят все нечетные цифры.

Ответ: 1, 3, 5, 7, 9.

1.31. В числе 7345_ заполните пропуск такой цифрой, чтобы:

а) число при делении на 9 давало в остатке 2;

б) число при делении на 25 давало в остатке 7.

а) число при делении на 9 давало в остатке 2;

Обозначим искомую цифру, которой заканчивается число, через $x$. Тогда наше число можно записать как $\overline{7345x}$. По условию, это число при делении на 9 должно давать в остатке 2. В терминах сравнений по модулю это записывается так: $\overline{7345x} \equiv 2 \pmod{9}$.

Для решения этой задачи воспользуемся признаком делимости на 9. Согласно этому признаку, любое натуральное число имеет такой же остаток при делении на 9, как и сумма его цифр. Найдем сумму цифр числа $\overline{7345x}$: $S = 7 + 3 + 4 + 5 + x = 19 + x$.

Следовательно, наше условие можно переписать для суммы цифр: $19 + x \equiv 2 \pmod{9}$.

Теперь упростим это сравнение. Найдем остаток от деления числа 19 на 9: $19 = 2 \cdot 9 + 1$. Значит, $19 \equiv 1 \pmod{9}$. Подставим это значение в наше сравнение: $1 + x \equiv 2 \pmod{9}$.

Чтобы найти $x$, вычтем 1 из обеих частей сравнения: $x \equiv 2 - 1 \pmod{9}$ $x \equiv 1 \pmod{9}$.

Поскольку $x$ — это цифра, она может принимать значения от 0 до 9. Среди этих значений только одно удовлетворяет условию $x \equiv 1 \pmod{9}$, а именно $x = 1$. Для проверки подставим найденную цифру в исходное число: 73451. Сумма его цифр равна $7+3+4+5+1 = 20$. При делении 20 на 9 получаем частное 2 и остаток 2 ($20 = 2 \cdot 9 + 2$). Условие выполняется.

Ответ: 1.

б) число при делении на 25 давало в остатке 7.

Снова обозначим искомую цифру через $x$, а число — как $\overline{7345x}$. По условию, это число при делении на 25 должно давать в остатке 7. Запишем это в виде сравнения по модулю: $\overline{7345x} \equiv 7 \pmod{25}$.

Воспользуемся свойством делимости на 25. Остаток от деления любого числа на 25 совпадает с остатком от деления на 25 числа, образованного двумя его последними цифрами. В нашем случае две последние цифры образуют число $\overline{5x}$.

Таким образом, исходное условие эквивалентно следующему: $\overline{5x} \equiv 7 \pmod{25}$.

Число $\overline{5x}$ можно представить в виде суммы $50 + x$. Подставим это выражение в наше сравнение: $50 + x \equiv 7 \pmod{25}$.

Упростим левую часть сравнения. Так как $50$ делится на 25 без остатка ($50 = 2 \cdot 25$), то $50 \equiv 0 \pmod{25}$. Следовательно, сравнение принимает вид: $0 + x \equiv 7 \pmod{25}$ $x \equiv 7 \pmod{25}$.

Поскольку $x$ — это цифра, то есть $0 \leq x \leq 9$, единственное значение, удовлетворяющее условию $x \equiv 7 \pmod{25}$, это $x = 7$. Для проверки подставим найденную цифру: число 73457. Две его последние цифры образуют число 57. При делении 57 на 25 получаем частное 2 и остаток 7 ($57 = 2 \cdot 25 + 7$). Условие выполняется.

Ответ: 7.

1.32. Рассмотрите два предложения:

a) сумма квадратов двух натуральных чисел делится на 3 тогда и только тогда, когда каждое из этих чисел делится на 3;

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

Докажите, что из этих утверждений верно только одно.

Для доказательства истинности или ложности данных утверждений мы будем использовать теорию сравнений по модулю. Каждое утверждение представляет собой эквивалентность ($P \iff Q$), поэтому для доказательства необходимо проверить две импликации: $P \Rightarrow Q$ и $Q \Rightarrow P$.

а) сумма квадратов двух натуральных чисел делится на 3 тогда и только тогда, когда каждое из этих чисел делится на 3

Пусть $a$ и $b$ — два натуральных числа. Утверждение можно записать в виде: $a^2 + b^2$ делится на 3 $\iff$ $a$ делится на 3 и $b$ делится на 3.

1. Докажем импликацию: если $a$ и $b$ делятся на 3, то $a^2 + b^2$ делится на 3.
Если $a$ делится на 3, то $a = 3k$ для некоторого натурального $k$. Аналогично, если $b$ делится на 3, то $b = 3m$ для некоторого натурального $m$. Тогда их сумма квадратов равна: $a^2 + b^2 = (3k)^2 + (3m)^2 = 9k^2 + 9m^2 = 3(3k^2 + 3m^2)$. Это выражение очевидно делится на 3. Эта часть утверждения верна.

2. Докажем импликацию: если $a^2 + b^2$ делится на 3, то $a$ и $b$ делятся на 3.
Рассмотрим, какие остатки могут давать квадраты натуральных чисел при делении на 3. Любое натуральное число $n$ при делении на 3 может давать остаток 0, 1 или 2. Запишем это в виде сравнений по модулю 3:

• Если $n \equiv 0 \pmod{3}$, то $n^2 \equiv 0^2 \equiv 0 \pmod{3}$.
• Если $n \equiv 1 \pmod{3}$, то $n^2 \equiv 1^2 \equiv 1 \pmod{3}$.
• Если $n \equiv 2 \pmod{3}$, то $n^2 \equiv 2^2 = 4 \equiv 1 \pmod{3}$.

Таким образом, квадрат любого натурального числа при делении на 3 может давать в остатке только 0 или 1. Теперь рассмотрим сумму $a^2 + b^2$ по модулю 3. По условию, $a^2 + b^2$ делится на 3, что означает $a^2 + b^2 \equiv 0 \pmod{3}$. Проверим возможные комбинации остатков для $a^2$ и $b^2$:

• Если $a^2 \equiv 0 \pmod{3}$ и $b^2 \equiv 0 \pmod{3}$, то $a^2+b^2 \equiv 0+0=0 \pmod{3}$.
• Если $a^2 \equiv 0 \pmod{3}$ и $b^2 \equiv 1 \pmod{3}$ (или наоборот), то $a^2+b^2 \equiv 0+1=1 \pmod{3}$.
• Если $a^2 \equiv 1 \pmod{3}$ и $b^2 \equiv 1 \pmod{3}$, то $a^2+b^2 \equiv 1+1=2 \pmod{3}$.

Сумма квадратов делится на 3 ($a^2+b^2 \equiv 0 \pmod{3}$) только в первом случае, когда $a^2 \equiv 0 \pmod{3}$ и $b^2 \equiv 0 \pmod{3}$. Если квадрат числа делится на простое число 3, то и само число должно делиться на 3. Следовательно, из $a^2 \equiv 0 \pmod{3}$ следует $a \equiv 0 \pmod{3}$, и из $b^2 \equiv 0 \pmod{3}$ следует $b \equiv 0 \pmod{3}$. Значит, если $a^2 + b^2$ делится на 3, то и $a$, и $b$ делятся на 3. Эта часть утверждения также верна.

Поскольку обе импликации верны, утверждение а) является истинным.

Ответ: утверждение а) верно.

б) сумма квадратов двух натуральных чисел делится на 5 тогда и только тогда, когда каждое из этих чисел делится на 5

Утверждение: $a^2 + b^2$ делится на 5 $\iff$ $a$ делится на 5 и $b$ делится на 5.

1. Проверим импликацию: если $a$ и $b$ делятся на 5, то $a^2 + b^2$ делится на 5.
Если $a = 5k$ и $b = 5m$, то $a^2 + b^2 = (5k)^2 + (5m)^2 = 25k^2 + 25m^2 = 5(5k^2 + 5m^2)$. Сумма делится на 5. Эта часть утверждения верна.

2. Проверим импликацию: если $a^2 + b^2$ делится на 5, то $a$ и $b$ делятся на 5.
Рассмотрим остатки квадратов натуральных чисел при делении на 5.

• Если $n \equiv 0 \pmod{5}$, то $n^2 \equiv 0^2 \equiv 0 \pmod{5}$.
• Если $n \equiv 1 \pmod{5}$, то $n^2 \equiv 1^2 \equiv 1 \pmod{5}$.
• Если $n \equiv 2 \pmod{5}$, то $n^2 \equiv 2^2 = 4 \pmod{5}$.
• Если $n \equiv 3 \pmod{5}$, то $n^2 \equiv 3^2 = 9 \equiv 4 \pmod{5}$.
• Если $n \equiv 4 \pmod{5}$, то $n^2 \equiv 4^2 = 16 \equiv 1 \pmod{5}$.

Таким образом, квадрат любого натурального числа при делении на 5 может давать в остатке только 0, 1 или 4. Рассмотрим сумму $a^2 + b^2$ по модулю 5 при условии $a^2 + b^2 \equiv 0 \pmod{5}$. Проверим, какие комбинации остатков $a^2$ и $b^2$ дают в сумме 0 по модулю 5:

• $a^2 \equiv 0, b^2 \equiv 0 \implies a^2+b^2 \equiv 0 \pmod{5}$.
• $a^2 \equiv 1, b^2 \equiv 4 \implies a^2+b^2 \equiv 1+4 = 5 \equiv 0 \pmod{5}$.

Кроме случая, когда оба числа делятся на 5, существует еще один: когда $a^2$ дает остаток 1, а $b^2$ — остаток 4 (или наоборот). Это означает, что $a$ не делится на 5 (остатки $a$ могут быть 1 или 4), и $b$ не делится на 5 (остатки $b$ могут быть 2 или 3). Приведем контрпример. Пусть $a=1$ и $b=2$. Ни $a=1$, ни $b=2$ не делятся на 5. Однако их сумма квадратов $a^2 + b^2 = 1^2 + 2^2 = 1 + 4 = 5$. Число 5 делится на 5. Таким образом, мы нашли числа $a$ и $b$, которые не делятся на 5, но сумма их квадратов делится на 5. Следовательно, импликация "если $a^2 + b^2$ делится на 5, то $a$ и $b$ делятся на 5" является ложной.

Поскольку одна из импликаций ложна, всё утверждение "тогда и только тогда" является ложным.

Ответ: утверждение б) неверно.

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

1.33. Найдите все простые числа, меньшие:

а) 50;

б) 100.

Простое число — это натуральное число больше 1, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Для нахождения всех простых чисел до заданного предела можно последовательно исключать составные числа, используя метод, известный как "Решето Эратосфена".

а) Чтобы найти все простые числа, меньшие 50, необходимо рассмотреть все натуральные числа от 2 до 49. Для проверки чисел на простоту достаточно проверить их делимость на простые числа, квадрат которых не превышает 50. Поскольку $7^2=49$ и следующее простое число $11$ в квадрате дает $121 > 50$, то проверку на делимость нужно проводить только для простых чисел 2, 3, 5 и 7.
1. Начинаем с 2, это первое простое число. Все остальные четные числа являются составными.
2. Следующее простое число — 3. Все числа, кратные 3 (кроме самого числа 3), являются составными.
3. Следующее простое — 5. Исключаем все числа, кратные 5.
4. Следующее простое — 7. Исключаем все числа, кратные 7.
Все числа, которые не были исключены в процессе, являются простыми.
В результате получаем следующий список простых чисел, меньших 50.
Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

б) Чтобы найти все простые числа, меньшие 100, мы продолжаем тот же процесс для чисел до 99. Предел для проверки делимости — это простые числа, чей квадрат не больше 100. Так как $\sqrt{100}=10$, то нам нужно проверять делимость на простые числа 2, 3, 5 и 7, как и в предыдущем пункте.
Мы уже нашли все простые числа до 50. Теперь проверим числа от 50 до 99:
- Исключаем все четные числа.
- Исключаем числа, кратные 3 (например, 51, 57, 63, 69, 75, 81, 87, 93, 99).
- Исключаем числа, кратные 5 (например, 55, 65, 85, 95).
- Исключаем числа, кратные 7 (например, 77, 91).
Оставшиеся в диапазоне от 50 до 99 числа 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 являются простыми. Объединив их с ранее найденным списком, мы получим все простые числа меньше 100.
Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

1.34. Найдите все составные числа, меньшие:

а) 50;

б) 100.

а) 50;

Составное число — это натуральное число больше единицы, которое имеет делители, отличные от 1 и самого себя. То есть, это число, которое не является простым. Например, число 6 является составным, так как оно делится на 2 и на 3 ($6 = 2 \cdot 3$). Число 1 не является ни простым, ни составным.

Чтобы найти все составные числа, меньшие 50, мы должны рассмотреть все натуральные числа в диапазоне от 2 до 49 и исключить из них все простые числа.

Простыми числами в этом диапазоне являются: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Все остальные числа в этом диапазоне, начиная с наименьшего составного числа 4, будут искомыми составными числами.

Ответ: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49.

б) 100.

Аналогично, чтобы найти все составные числа, меньшие 100, необходимо из всех натуральных чисел от 2 до 99 исключить простые.

Простыми числами в этом диапазоне являются: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Все остальные числа в диапазоне от 4 до 99 будут составными.

Ответ: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99.

1.35. Выпишите все пары взаимно простых составных чисел из отрезка натурального ряда 1, 2, 3, ..., 20.

Для решения этой задачи необходимо сначала определить все составные числа в заданном диапазоне, а затем найти среди них пары, которые являются взаимно простыми.

1. Находим составные числа в отрезке [1, 20]

Составное число — это натуральное число, большее 1, которое имеет делители, отличные от 1 и самого себя. Сначала выпишем все числа от 1 до 20 и определим, какие из них являются составными.

• Простые числа в этом диапазоне: 2, 3, 5, 7, 11, 13, 17, 19.
• Число 1 не является ни простым, ни составным.
• Составные числа — это все остальные натуральные числа из отрезка, которые больше 1 и не являются простыми.

Таким образом, список составных чисел из отрезка [1, 20] следующий: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20.

2. Ищем взаимно простые пары

Два числа называются взаимно простыми, если их наибольший общий делитель (НОД) равен 1. Это значит, что у них нет общих простых делителей. Для удобства проверки разложим каждое составное число на простые множители:

• $4 = 2^2$
• $6 = 2 \cdot 3$
• $8 = 2^3$
• $9 = 3^2$
• $10 = 2 \cdot 5$
• $12 = 2^2 \cdot 3$
• $14 = 2 \cdot 7$
• $15 = 3 \cdot 5$
• $16 = 2^4$
• $18 = 2 \cdot 3^2$
• $20 = 2^2 \cdot 5$

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

• Для числа 4 (простой множитель 2): ищем числа, в разложении которых нет множителя 2. Это 9 ($3^2$) и 15 ($3 \cdot 5$).
  Получаем пары: (4, 9), (4, 15).
• Для числа 6 (простые множители 2, 3): все остальные составные числа в списке имеют в разложении либо 2, либо 3, поэтому пар с числом 6 нет.
• Для числа 8 (простой множитель 2): как и для числа 4, ищем числа без множителя 2. Это 9 и 15.
  Получаем пары: (8, 9), (8, 15).
• Для числа 9 (простой множитель 3): ищем числа без множителя 3. Из оставшегося списка это 10 ($2 \cdot 5$), 14 ($2 \cdot 7$), 16 ($2^4$), 20 ($2^2 \cdot 5$).
  Получаем пары: (9, 10), (9, 14), (9, 16), (9, 20).
• Для числа 10 (простые множители 2, 5): все оставшиеся непроверенные числа (12, 14, 15, 16, 18, 20) имеют общий множитель 2 или 5. Новых пар нет.
• Для числа 12 (простые множители 2, 3): все оставшиеся непроверенные числа (14, 15, 16, 18, 20) имеют общий множитель 2 или 3. Новых пар нет.
• Для числа 14 (простые множители 2, 7): ищем среди оставшихся (15, 16, 18, 20) числа без множителей 2 и 7. Подходит только 15 ($3 \cdot 5$).
  Получаем пару: (14, 15).
• Для числа 15 (простые множители 3, 5): ищем среди оставшихся (16, 18, 20) числа без множителей 3 и 5. Подходит только 16 ($2^4$).
  Получаем пару: (15, 16).

Остальные числа (16, 18, 20) не образуют новых взаимно простых пар.

Ответ: (4, 9), (4, 15), (8, 9), (8, 15), (9, 10), (9, 14), (9, 16), (9, 20), (14, 15), (15, 16).

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$. Наше исходное предположение о том, что множество простых чисел конечно, было неверным.

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

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$.

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

1.38. Докажите, что среди данных последовательных натуральных чисел нет ни одного простого числа:

а) $23! + 2$, $23! + 3$; $23! + 4$, ..., $23! + 23$;

б) $101! + 2$, $101! + 3$; $101! + 4$, ..., $101! + 101$.

в) Сколько составных чисел в каждой серии а) и б)?

г) Выпишите 1 000 000 последовательных натуральных чисел, среди которых нет ни одного простого.

а)

Рассмотрим последовательность чисел: $23! + 2, 23! + 3, 23! + 4, \dots, 23! + 23$. Необходимо доказать, что каждое число в этой последовательности является составным, то есть имеет делитель, отличный от 1 и самого себя.

Возьмем любой член этой последовательности, который можно представить в общем виде как $23! + k$, где $k$ – целое число и $2 \le k \le 23$.

По определению факториала, $23! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 22 \cdot 23$. Из этого следует, что $23!$ делится на любое целое число от 2 до 23 без остатка. В частности, $23!$ делится на $k$.

Рассмотрим сумму $23! + k$. Первое слагаемое, $23!$, делится на $k$, поскольку $k$ является одним из множителей в произведении $23!$. Второе слагаемое, $k$, очевидно делится на $k$. Если каждое из двух слагаемых делится на некоторое число, то и их сумма делится на это число. Следовательно, число $23! + k$ делится на $k$.

Поскольку $k \ge 2$, то делитель $k$ больше 1. Также, $23! + k > k$, так как $23!$ – положительное число. Таким образом, для каждого числа вида $23! + k$ мы нашли делитель $k$, который больше 1 и меньше самого числа. Это означает, что каждое число в данной последовательности является составным. Следовательно, среди них нет ни одного простого числа.

Ответ: Доказано, что все числа в последовательности являются составными.

б)

Рассмотрим последовательность чисел: $101! + 2, 101! + 3, 101! + 4, \dots, 101! + 101$. Доказательство аналогично пункту а).

Возьмем любой член этой последовательности, который можно представить в общем виде как $101! + k$, где $k$ – целое число и $2 \le k \le 101$.

По определению, $101! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot 100 \cdot 101$. Это означает, что $101!$ делится на любое целое число $k$ в диапазоне от 2 до 101.

Рассмотрим сумму $101! + k$. Первое слагаемое, $101!$, делится на $k$, а второе слагаемое, $k$, также делится на $k$. Следовательно, вся сумма $101! + k$ делится на $k$.

Так как $k \ge 2$, делитель $k$ отличен от 1. Так как $101! > 0$, то $101! + k > k$. Значит, каждое число в этой последовательности имеет делитель $k$, отличный от 1 и самого себя, и, следовательно, является составным.

Ответ: Доказано, что все числа в последовательности являются составными.

в)

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

В серии а) представлена последовательность $23! + 2, 23! + 3, \dots, 23! + 23$. Количество членов в этой последовательности равно $(23 - 2) + 1 = 21 + 1 = 22$. Таким образом, в серии а) 22 составных числа.

В серии б) представлена последовательность $101! + 2, 101! + 3, \dots, 101! + 101$. Количество членов равно $(101 - 2) + 1 = 99 + 1 = 100$. Таким образом, в серии б) 100 составных чисел.

Ответ: в серии а) 22 составных числа, в серии б) 100 составных чисел.

г)

Нам нужно выписать $1\;000\;000$ последовательных натуральных чисел, среди которых нет ни одного простого. Для этого воспользуемся общим методом, показанным в предыдущих пунктах.

Чтобы получить $N$ последовательных составных чисел, можно взять последовательность вида $(N+1)! + 2, (N+1)! + 3, \dots, (N+1)! + (N+1)$. В данном случае $N = 1\;000\;000$.

Пусть $M = 1\;000\;000 + 1 = 1\;000\;001$. Рассмотрим последовательность: $M! + 2, M! + 3, M! + 4, \dots, M! + M$.

Эта последовательность состоит из $M-1 = (1\;000\;001 - 1) = 1\;000\;000$ последовательных натуральных чисел.

Докажем, что все они составные. Любой член последовательности имеет вид $M! + k$, где $2 \le k \le M$. Так как $k \le M$, то $M!$ делится на $k$. Значит, и сумма $M! + k$ также делится на $k$. Поскольку $M!+k > k$ и $k > 1$, каждое число $M!+k$ является составным.

Таким образом, искомая последовательность: $(1\;000\;001)! + 2, (1\;000\;001)! + 3, \dots, (1\;000\;001)! + 1\;000\;001$.

Ответ: Последовательность из $1\;000\;000$ последовательных составных натуральных чисел: $(1\;000\;001)! + 2, (1\;000\;001)! + 3, \dots, (1\;000\;001)! + 1\;000\;001$.