Страница 383 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

49.18. Натуральные числа $a, b$ и $c$ таковы, что $(a+b+c) : 13$. Докажите, что число $a^{13} + b^{13} + c^{13}$ также кратно 13.

Для доказательства воспользуемся Малой теоремой Ферма. Она гласит, что если $p$ — простое число, то для любого целого числа $n$ выполняется сравнение $n^p \equiv n \pmod{p}$.

В нашей задаче число 13 является простым. Следовательно, мы можем применить Малую теорему Ферма для $p = 13$ и натуральных чисел $a$, $b$ и $c$.

Согласно теореме, для каждого из чисел $a$, $b$ и $c$ справедливы следующие сравнения по модулю 13:

$a^{13} \equiv a \pmod{13}$

$b^{13} \equiv b \pmod{13}$

$c^{13} \equiv c \pmod{13}$

Сложим эти три сравнения, что является корректной операцией в арифметике остатков:

$a^{13} + b^{13} + c^{13} \equiv a + b + c \pmod{13}$

По условию задачи, сумма $(a+b+c)$ делится на 13. На языке сравнений это записывается как:

$a + b + c \equiv 0 \pmod{13}$

Теперь, используя свойство транзитивности сравнений, мы можем объединить полученные результаты. Так как $a^{13} + b^{13} + c^{13}$ сравнимо с $a + b + c$ по модулю 13, а $a + b + c$, в свою очередь, сравнимо с 0 по тому же модулю, то и $a^{13} + b^{13} + c^{13}$ сравнимо с 0.

$a^{13} + b^{13} + c^{13} \equiv 0 \pmod{13}$

Это сравнение означает, что число $a^{13} + b^{13} + c^{13}$ делится на 13 без остатка, что и требовалось доказать.

Ответ: Утверждение доказано. На основе Малой теоремы Ферма, $n^{13} \equiv n \pmod{13}$ для любого целого $n$. Следовательно, $a^{13} + b^{13} + c^{13} \equiv a + b + c \pmod{13}$. Так как по условию $a + b + c$ кратно 13, то есть $a + b + c \equiv 0 \pmod{13}$, из этого следует, что $a^{13} + b^{13} + c^{13} \equiv 0 \pmod{13}$, то есть $a^{13} + b^{13} + c^{13}$ также кратно 13.

49.19. Докажите, что при любом натуральном $a$ значение выражения $a^{14} + 13a^2$ кратно 7.

Для доказательства того, что значение выражения $a^{14} + 13a^2$ кратно 7 при любом натуральном $a$, мы используем теорию сравнений и малую теорему Ферма.

Требуется доказать, что $a^{14} + 13a^2 \equiv 0 \pmod{7}$.

Сначала преобразуем выражение, используя свойства сравнений по модулю. Заметим, что коэффициент 13 при делении на 7 даёт в остатке 6. Это можно записать как $13 \equiv 6 \pmod{7}$. Также удобно представить это как $13 \equiv -1 \pmod{7}$, поскольку $13 = 2 \cdot 7 - 1$.

Подставим $13 \equiv -1 \pmod{7}$ в исходное выражение:

$a^{14} + 13a^2 \equiv a^{14} + (-1) \cdot a^2 \equiv a^{14} - a^2 \pmod{7}$.

Теперь задача сводится к доказательству того, что $a^{14} - a^2$ кратно 7.

Согласно малой теореме Ферма, для любого простого числа $p$ и любого целого числа $a$ выполняется сравнение $a^p \equiv a \pmod{p}$.

В нашем случае $p=7$, что является простым числом. Следовательно, для любого натурального $a$ справедливо:

$a^7 \equiv a \pmod{7}$.

Используем это свойство для преобразования $a^{14}$:

$a^{14} = (a^7)^2$.

Так как $a^7 \equiv a \pmod{7}$, то, возведя обе части сравнения в квадрат, получим:

$(a^7)^2 \equiv a^2 \pmod{7}$,

откуда следует, что $a^{14} \equiv a^2 \pmod{7}$.

Подставим этот результат в наше преобразованное выражение:

$a^{14} - a^2 \equiv a^2 - a^2 \equiv 0 \pmod{7}$.

Таким образом, мы показали, что $a^{14} + 13a^2$ сравнимо с нулём по модулю 7. Это означает, что выражение $a^{14} + 13a^2$ делится на 7 без остатка при любом натуральном $a$, что и требовалось доказать.

Ответ: Доказано, что при любом натуральном $a$ значение выражения $a^{14} + 13a^2$ кратно 7.

49.20. Докажите, что при любом натуральном $a$ значение выражения $a^{57} - 39a^3$ кратно 19.

Чтобы доказать, что значение выражения $a^{57} - 39a^3$ кратно 19 при любом натуральном $a$, необходимо показать, что остаток от деления этого выражения на 19 равен нулю. В терминах теории чисел это означает, что нам нужно доказать сравнение: $a^{57} - 39a^3 \equiv 0 \pmod{19}$.

Рассмотрим данное выражение по модулю 19. В первую очередь, упростим коэффициент 39, найдя его остаток от деления на 19: $39 = 2 \cdot 19 + 1$. Отсюда следует, что $39 \equiv 1 \pmod{19}$.

Теперь мы можем подставить это значение в исходное выражение: $a^{57} - 39a^3 \equiv a^{57} - 1 \cdot a^3 \pmod{19}$, $a^{57} - 39a^3 \equiv a^{57} - a^3 \pmod{19}$.

Теперь задача сводится к доказательству того, что $a^{57} - a^3$ делится на 19. Для этого воспользуемся Малой теоремой Ферма, которая гласит: если $p$ — простое число, то для любого целого числа $a$ выполняется сравнение $a^p \equiv a \pmod{p}$.

Поскольку 19 — простое число, то по Малой теореме Ферма для любого натурального $a$ справедливо: $a^{19} \equiv a \pmod{19}$.

Рассмотрим степень 57 в первом члене нашего выражения. Мы можем представить 57 как $3 \cdot 19$. Тогда: $a^{57} = a^{3 \cdot 19} = (a^{19})^3$.

Используя установленное ранее сравнение $a^{19} \equiv a \pmod{19}$, возведем обе его части в третью степень: $(a^{19})^3 \equiv a^3 \pmod{19}$. Следовательно, мы получаем, что $a^{57} \equiv a^3 \pmod{19}$.

Подставим полученный результат в наше выражение: $a^{57} - a^3 \equiv a^3 - a^3 \equiv 0 \pmod{19}$.

Таким образом, мы доказали, что $a^{57} - 39a^3 \equiv 0 \pmod{19}$ для любого натурального числа $a$, а это означает, что значение выражения $a^{57} - 39a^3$ всегда кратно 19.

Ответ: Что и требовалось доказать.

49.21. Используя малую теорему Ферма, найдите остаток от деления числа a на число b, если:

1) $a=5^{52}$, $b=53$;

2) $a=2^{47}$, $b=41$.

1) $a = 5^{52}, b = 53$

Требуется найти остаток от деления числа $a$ на число $b$, то есть найти значение выражения $5^{52} \pmod{53}$.

Малая теорема Ферма утверждает, что если $p$ — простое число, и целое число $a$ не делится на $p$, то справедливо сравнение: $a^{p-1} \equiv 1 \pmod{p}$.

В данном случае $p = 53$, что является простым числом. Основание степени $a = 5$ не делится на $53$. Следовательно, все условия для применения малой теоремы Ферма выполнены.

Подставим наши значения в формулу теоремы:

$5^{53-1} \equiv 1 \pmod{53}$

$5^{52} \equiv 1 \pmod{53}$

Это означает, что остаток от деления $5^{52}$ на $53$ равен 1.

Ответ: 1

2) $a = 2^{47}, b = 41$

Требуется найти остаток от деления числа $a$ на число $b$, то есть найти значение выражения $2^{47} \pmod{41}$.

Воспользуемся малой теоремой Ферма. Здесь модуль $p = 41$ является простым числом, а основание степени $a = 2$ не делится на $41$. Условия теоремы соблюдены.

Согласно малой теореме Ферма:

$2^{41-1} \equiv 1 \pmod{41}$

$2^{40} \equiv 1 \pmod{41}$

Теперь представим $2^{47}$ через $2^{40}$:

$2^{47} = 2^{40+7} = 2^{40} \cdot 2^7$

Рассмотрим это выражение по модулю 41:

$2^{47} \equiv 2^{40} \cdot 2^7 \pmod{41}$

Так как $2^{40} \equiv 1 \pmod{41}$, мы можем заменить $2^{40}$ на 1 в сравнении:

$2^{47} \equiv 1 \cdot 2^7 \pmod{41}$

$2^{47} \equiv 2^7 \pmod{41}$

Теперь вычислим значение $2^7$ и найдем остаток от его деления на 41.

$2^7 = 128$

Разделим 128 на 41 с остатком:

$128 = 3 \cdot 41 + 5$

Остаток от деления равен 5, следовательно, $128 \equiv 5 \pmod{41}$.

Таким образом, $2^{47} \equiv 5 \pmod{41}$.

Ответ: 5

49.22. Докажите, что число $24^{24} - 1$ кратно 35.

Чтобы доказать, что число $24^{24} - 1$ кратно 35, достаточно доказать, что оно делится на 5 и на 7, так как $35 = 5 \cdot 7$ и числа 5 и 7 являются взаимно простыми.

Сначала докажем делимость на 5. Для этого рассмотрим выражение по модулю 5. Число 24 при делении на 5 дает в остатке 4, что можно записать как $24 \equiv 4 \pmod{5}$. Удобнее использовать сравнение $24 \equiv -1 \pmod{5}$. Тогда $24^{24} \equiv (-1)^{24} \pmod{5}$. Так как 24 – четное число, $(-1)^{24} = 1$. Следовательно, $24^{24} \equiv 1 \pmod{5}$, а это значит, что $24^{24} - 1 \equiv 1 - 1 \equiv 0 \pmod{5}$. Таким образом, число $24^{24} - 1$ делится на 5.

Теперь докажем делимость на 7. Рассмотрим выражение по модулю 7. Число 24 при делении на 7 дает в остатке 3, то есть $24 \equiv 3 \pmod{7}$. Тогда $24^{24} \equiv 3^{24} \pmod{7}$. Воспользуемся Малой теоремой Ферма, согласно которой $a^{p-1} \equiv 1 \pmod{p}$ для простого числа $p$ и целого числа $a$, не делящегося на $p$. Для $p=7$ и $a=3$ имеем: $3^{7-1} \equiv 3^6 \equiv 1 \pmod{7}$. Представим степень 24 как $24 = 6 \cdot 4$. Тогда $3^{24} = (3^6)^4 \equiv 1^4 \equiv 1 \pmod{7}$. Значит, $24^{24} \equiv 1 \pmod{7}$, и $24^{24} - 1 \equiv 1 - 1 \equiv 0 \pmod{7}$. Таким образом, число $24^{24} - 1$ делится на 7.

Поскольку число $24^{24} - 1$ делится и на 5, и на 7, а числа 5 и 7 взаимно простые, то оно делится и на их произведение, то есть на 35.

Ответ: Что и требовалось доказать.

49.23. Натуральное число $a$ не делится нацело на 29. Докажите, что одно из чисел, $a^{14} - 1$ или $a^{14} + 1$, делится нацело на 29.

Поскольку 29 — это простое число, а натуральное число $a$ по условию не делится на 29, мы можем воспользоваться малой теоремой Ферма.

Малая теорема Ферма гласит, что если $p$ — простое число, то для любого целого числа $a$, не делящегося на $p$, выполняется сравнение: $a^{p-1} \equiv 1 \pmod{p}$.

В нашем случае $p = 29$. Применим теорему:

$a^{29-1} \equiv 1 \pmod{29}$

$a^{28} \equiv 1 \pmod{29}$

Представим степень 28 как $2 \cdot 14$:

$(a^{14})^2 \equiv 1 \pmod{29}$

Перенесем единицу в левую часть сравнения:

$(a^{14})^2 - 1 \equiv 0 \pmod{29}$

Теперь разложим левую часть по формуле разности квадратов $x^2 - y^2 = (x-y)(x+y)$:

$(a^{14} - 1)(a^{14} + 1) \equiv 0 \pmod{29}$

Это означает, что произведение $(a^{14} - 1)(a^{14} + 1)$ делится нацело на 29. Поскольку 29 — простое число, то если произведение двух чисел делится на 29, то хотя бы одно из этих чисел должно делиться на 29.

Следовательно, либо $(a^{14} - 1)$ делится на 29, либо $(a^{14} + 1)$ делится на 29, что и требовалось доказать.

Ответ: Утверждение доказано с помощью малой теоремы Ферма.

49.24. Найдите все простые $p$ такие, что число $p^2 + 11$ имеет 6 различных натуральных делителей.

Пусть $N = p^2 + 11$. По условию, $p$ — простое число, а число $N$ имеет 6 различных натуральных делителей.

Количество натуральных делителей числа $\tau(N)$, разложение которого на простые множители имеет вид $q_1^{a_1} q_2^{a_2} \cdots q_k^{a_k}$, вычисляется по формуле $\tau(N) = (a_1+1)(a_2+1)\cdots(a_k+1)$.

Поскольку $\tau(N) = 6$, а число 6 можно представить в виде произведения натуральных чисел (больших 1) двумя способами: $6$ и $2 \cdot 3$. Это означает, что разложение числа $N$ на простые множители может иметь один из двух видов:
1) $N = q^5$ для некоторого простого числа $q$.
2) $N = q_1^2 \cdot q_2$ для некоторых различных простых чисел $q_1$ и $q_2$.

Рассмотрим каждый случай отдельно.

Случай 1: $p^2 + 11 = q^5$
Если $p=2$, то $p^2 + 11 = 2^2 + 11 = 15$. Число 15 не является пятой степенью какого-либо простого числа.
Если $p$ — нечетное простое число, то $p^2$ — нечетное число. Тогда $p^2 + 11$ — четное число. Следовательно, единственный простой множитель $q$ должен быть равен 2.
Получаем уравнение: $p^2 + 11 = 2^5 = 32$.
Отсюда $p^2 = 32 - 11 = 21$. Число 21 не является квадратом целого числа, значит, $p$ не является целым, а следовательно, и не простым.
Таким образом, в этом случае решений нет.

Случай 2: $p^2 + 11 = q_1^2 \cdot q_2$
Проверим несколько первых простых значений $p$.
• При $p=2$: $p^2 + 11 = 2^2 + 11 = 15 = 3^1 \cdot 5^1$. Число делителей $\tau(15) = (1+1)(1+1) = 4$, что не равно 6.
• При $p=3$: $p^2 + 11 = 3^2 + 11 = 20 = 2^2 \cdot 5^1$. Число делителей $\tau(20) = (2+1)(1+1) = 6$. Это соответствует условию задачи. Значит, $p=3$ является решением.

Теперь рассмотрим случай, когда $p$ — простое число, большее 3 ($p > 3$).
Если $p > 3$, то $p$ не делится на 3. Следовательно, остаток от деления $p$ на 3 равен 1 или 2. В любом из этих случаев $p^2$ дает остаток 1 при делении на 3 (т.е. $p^2 \equiv 1 \pmod 3$).
Тогда $p^2 + 11 \equiv 1 + 11 \pmod 3 \equiv 12 \pmod 3 \equiv 0 \pmod 3$.
Это означает, что число $p^2 + 11$ делится на 3. Следовательно, один из его простых множителей ($q_1$ или $q_2$) должен быть равен 3.

Подслучай 2.1: $q_1 = 3$
Уравнение принимает вид $p^2 + 11 = 3^2 \cdot q_2 = 9q_2$, где $q_2$ — простое число, не равное 3.
Выразим $p^2$: $p^2 = 9q_2 - 11$.
Так как $p > 3$, $p$ — нечетное простое число. Квадрат любого нечетного числа при делении на 8 дает в остатке 1, то есть $p^2 \equiv 1 \pmod 8$.
Рассмотрим уравнение по модулю 8:
$p^2 \equiv 9q_2 - 11 \pmod 8$
$1 \equiv (1)q_2 - 3 \pmod 8$
$q_2 \equiv 4 \pmod 8$.
Это означает, что $q_2$ должно быть кратно 4, что невозможно для простого числа. Следовательно, в этом подслучае решений нет.

Подслучай 2.2: $q_2 = 3$
Уравнение принимает вид $p^2 + 11 = q_1^2 \cdot 3 = 3q_1^2$, где $q_1$ — простое число, не равное 3.
Выразим $p^2$: $p^2 = 3q_1^2 - 11$.
Так как $p > 3$, $p$ — нечетное простое число, и $p^2 \equiv 1 \pmod 4$.
Рассмотрим два варианта для $q_1$:
• Если $q_1 = 2$, то $p^2 = 3(2^2) - 11 = 12 - 11 = 1$. Отсюда $p=1$, что не является простым числом.
• Если $q_1$ — нечетное простое число (т.е. $q_1 \ge 5$), то $q_1^2 \equiv 1 \pmod 4$.
Рассмотрим уравнение по модулю 4:
$p^2 \equiv 3q_1^2 - 11 \pmod 4$
$1 \equiv 3(1) - 3 \pmod 4$
$1 \equiv 0 \pmod 4$.
Получено противоречие. Следовательно, в этом подслучае также нет решений.

Мы рассмотрели все возможные случаи и обнаружили, что единственным простым числом $p$, удовлетворяющим условию задачи, является $p=3$.

Ответ: $p=3$.

49.25. Докажите, что значение выражения $42^{47} + 47^{42}$ является составным числом.

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

Рассмотрим выражение $N = 42^{47} + 47^{42}$ по модулю 43.

1. Анализ первого слагаемого $42^{47}$.
Число 42 можно представить как $43 - 1$. Следовательно, справедливо сравнение:$42 \equiv -1 \pmod{43}$Возведем обе части сравнения в степень 47:$42^{47} \equiv (-1)^{47} \pmod{43}$Так как 47 — нечетное число, то $(-1)^{47} = -1$. Таким образом, получаем:$42^{47} \equiv -1 \pmod{43}$

2. Анализ второго слагаемого $47^{42}$.
Число 47 можно представить как $43 + 4$. Следовательно, справедливо сравнение:$47 \equiv 4 \pmod{43}$Возведем обе части сравнения в степень 42:$47^{42} \equiv 4^{42} \pmod{43}$

Для дальнейшего упрощения воспользуемся малой теоремой Ферма, которая утверждает, что если $p$ — простое число, то для любого целого числа $a$, не делящегося на $p$, выполняется сравнение $a^{p-1} \equiv 1 \pmod{p}$. В нашем случае $p = 43$ является простым числом, а $a = 4$ не делится на 43. Применяя теорему, получаем:$4^{43-1} \equiv 1 \pmod{43}$$4^{42} \equiv 1 \pmod{43}$Следовательно, и $47^{42} \equiv 1 \pmod{43}$.

3. Сложение результатов.
Теперь сложим остатки от деления обоих слагаемых на 43:$42^{47} + 47^{42} \equiv (-1) + 1 \pmod{43}$$42^{47} + 47^{42} \equiv 0 \pmod{43}$Это означает, что значение выражения $42^{47} + 47^{42}$ делится на 43 без остатка.

Поскольку $42^{47}$ и $47^{42}$ — положительные числа, их сумма $42^{47} + 47^{42}$ очевидно больше, чем 43. Так как мы нашли делитель (число 43), который не равен 1 и не равен самому числу, то по определению число $42^{47} + 47^{42}$ является составным.

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

49.26. Докажите, что $p^q + q^p \equiv (p + q) \pmod{pq}$, где $p$ и $q$ — различные простые числа.

Чтобы доказать сравнение $p^q + q^p \equiv p + q \pmod{pq}$, где $p$ и $q$ — различные простые числа, нам нужно показать, что разность $(p^q + q^p) - (p + q)$ делится на $pq$. Поскольку $p$ и $q$ — различные простые числа, они взаимно просты. Следовательно, для того чтобы число делилось на $pq$, достаточно и необходимо, чтобы оно делилось на $p$ и на $q$ по отдельности.

1. Докажем, что $p^q + q^p \equiv p + q \pmod{p}$.
Рассмотрим левую и правую части сравнения по модулю $p$.
Левая часть: $p^q + q^p$. Так как $p^q$ содержит множитель $p$, то $p^q \equiv 0 \pmod{p}$. Выражение упрощается до $0 + q^p \equiv q^p \pmod{p}$.
Согласно Малой теореме Ферма, поскольку $p$ — простое число, для любого целого числа $q$ выполняется $q^p \equiv q \pmod{p}$.
Таким образом, левая часть сравнима с $q$: $p^q + q^p \equiv q \pmod{p}$.
Правая часть: $p + q$. По модулю $p$ имеем $p + q \equiv 0 + q \equiv q \pmod{p}$.
Поскольку и левая, и правая части сравнения сравнимы с $q$ по модулю $p$, то сравнение $p^q + q^p \equiv p + q \pmod{p}$ является верным.

2. Докажем, что $p^q + q^p \equiv p + q \pmod{q}$.
Рассмотрим левую и правую части сравнения по модулю $q$.
Левая часть: $p^q + q^p$. Так как $q^p$ содержит множитель $q$, то $q^p \equiv 0 \pmod{q}$. Выражение упрощается до $p^q + 0 \equiv p^q \pmod{q}$.
Согласно Малой теореме Ферма, поскольку $q$ — простое число, для любого целого числа $p$ выполняется $p^q \equiv p \pmod{q}$.
Таким образом, левая часть сравнима с $p$: $p^q + q^p \equiv p \pmod{q}$.
Правая часть: $p + q$. По модулю $q$ имеем $p + q \equiv p + 0 \equiv p \pmod{q}$.
Поскольку и левая, и правая части сравнения сравнимы с $p$ по модулю $q$, то сравнение $p^q + q^p \equiv p + q \pmod{q}$ также является верным.

Заключение.
Мы показали, что разность $(p^q + q^p) - (p + q)$ делится как на $p$, так и на $q$. Поскольку $p$ и $q$ — различные простые числа, они взаимно просты (т.е. $НОД(p, q) = 1$). Если целое число делится на два взаимно простых числа, оно делится и на их произведение. Следовательно, $(p^q + q^p) - (p + q)$ делится на $pq$.
Это по определению означает, что $p^q + q^p \equiv p + q \pmod{pq}$.
Что и требовалось доказать.

Ответ: Доказательство основано на Малой теореме Ферма. Сравнение доказывается сначала по модулю $p$, а затем по модулю $q$. Так как $p$ и $q$ — различные (а значит, взаимно простые) простые числа, из справедливости сравнения по каждому из этих модулей следует его справедливость по модулю их произведения $pq$.