Делимость суммы и произведения

Отлично. Разберём тему «Делимость суммы и произведения» пошагово, с понятными примерами и объяснениями. Это базовый набор правил, который пригодится почти во всех задачах на делимость. 1) Что значит делимость - А скажем, что целое число a делится на b (обозначается a | b), если существует целое число k такое, что b = a · k. - Применимо к сумме и к произведению словом: если a делит b и a делит c, то a делит и b+c, и b−c. Также если a делит b, то a делит любую линейную комбинацию m·b + n·c. 2) Основные правила делимости (для понимания) - Правило 1 (сумма и разность): если a | b и a | c, то a | (b + c) и a | (b − c). Доказательство: запишем b = a·k и c = a·l, тогда b+c = a(k+l), b−c = a(k−l). - Правило 2 (произведение с суммой): если a | b и a | c, то a | (m·b + n·c) для любых целых m, n (потому что m·b + n·c = a(m·k + n·l)). - Правило 3 (когда можно «отнять» делимость): если a | b и gcd(a, b) = 1, и a | c, то a | c. Это особый факт, который часто применяется как «кляп» в доказательствах (через свойства наибольшего общего делителя). - Правило 4 (лекция о простых): если p — простое число и p | (ab), то p | a или p | b (известный лемма Эзло). Это важное основание для работы с простыми делителями. 3) Ключевые леммы, которые часто встречаются в задачах Лемма A. Пусть a | b и a | c. Тогда для любых целых m и n выполняется a | (m·b + n·c). Доказательство: b = a·k, c = a·l, значит m·b + n·c = a(m·k + n·l). Лемма B. Если gcd(a, b) = 1 и a | (b·c), то a | c. Доказательство: найдём u, v такие, что u·a + v·b = 1 (из существования линейной комбинации по свойству НОД). Умножим на c: u·a·c + v·b·c = c. Первая часть делится на a, вторая часть тоже, потому что a | b·c. Следовательно, a | c. Лемма C. Если p — простое, и p | (a + b) и p | (a − b), то p | 2a и p | 2b. Следствие: складывая и вычитая, получаем 2a и 2b делятся на p. Если p не равно 2 (то есть p — нечётное), то из этого следует p | a и p | b (потому что у odd p есть обратный элемент к 2). Это стандартный трюк для некоторых задач. 4) Примеры с пошаговыми объяснениями Пример 1. Пусть a | b и a | c. Покажем, что a | (b + c) и a | (b − c). - Пусть b = a·k, c = a·l. - Тогда b + c = a·k + a·l = a·(k + l) — значит a | (b + c). - Аналогично b − c = a·k − a·l = a·(k − l) — значит a | (b − c). Закончили этот пример. Пример 2. Пусть a | b и gcd(a, c) = 1. Тогда a | (b·c) ⇒ a | b. - По условию a | b, значит всё и так. Но если дано наоборот: a | (b·c) и gcd(a, c) = 1, тогда из Леммы B следует a | b. Пояснение: gcd(a, c) = 1 значит можно «развернуть» делимость через существование линейной комбинации 1 = x·a + y·c, перемножим на b и применим разложение на множители. В итоге a | b·c и gcd(a, c) = 1 приводят к a | b. Пример 3. Пусть p — простое число. Пусть p | (a + b) и p | (a − b). Что можно сказать? - По Лемме C, p | 2a и p | 2b. - Если p ≠ 2, то 2 имеет обратный элемент по модулю p, значит p | a и p | b. - Если p = 2, то условия дают 2 | (a + b) и 2 | (a − b), что эквивалентно 2 | a и 2 | b (поскольку a + b и a − b чётные тогда и только тогда, когда a и b имеют одинаковый чётный/нечётный статус). В любом случае выполняется вывод о слабой делимости. Пример 4. Применение правила к линейной комбинации. - Пусть a | b и a | c. Получаем, что a | (3b − 5c) по формуле m·b + n·c с m = 3 и n = −5. - Доказательство: b = a·k, c = a·l, тогда 3b − 5c = a(3k − 5l) — делится на a. 5) Как это использовать на практике (быстрые советы) - Ищите ситуацию: есть ли данное a | b и a | c? Тогда сразу можно заключать про любую линейную комбинацию m·b + n·c. - Проверяйте условие на взаимную простоту. Если gcd(a, b) = 1 и известно a | (b·c), можно заключить a | c. - Если нужно разложить на простые делители, применяйте Лемму про простые (p | ab ⇒ p | a или p | b) и потом раскладывайте по множителям. - Если задача про сумму и разность, попробуйте сложить и вычесть (b + c) и (b − c) или (a + b) и (a − b) — часто получаются удобные выводы. 6) Задачи для самостоятельной практики (сложность средней школы) Попробуйте решить после прочтения: - Задача 1. Пусть a | b и a | c. Докажите, что a | (2b + 3c). - Задача 2. Пусть p — простое число, и p | (a + b). Пусть также p | a. Докажите, что p | b. - Задача 3. Пусть n | (x + y) и n | (x − y). Что можно сказать о x и y, когда n — нечётное? Какие выводы о чётности можно сделать? - Задача 4. Пусть p — простое, и p | (a^2 − b^2). Что можно сказать про a и b, если p | (a − b) или p | (a + b)? Если хочешь, могу подобрать конкретную задачу по твоему уровню и подробно её разобрать по шагам. Просто пришли текст задачи или изображение — и укажи цель: хочешь понять теорию или решить конкретную задачу.