|
Семинар 9 Задание решение заданий на делимость и целые числа|
ИТОГОВОЕ ПОВТОРЕНИЕ СЕМИНАР 9
Задание С6. Решение заданий на делимость и целые числа.
Необходимые сведения:
1) Определение и свойства делимости целых чисел.
Целое число делится на целое число , если существует такое целое число , что .
Если делится на , то делится на ( здесь и далее все числа целые, если это специально не оговаривается).
Если и делятся на , то и делятся на .
Если делится на , делится на , то делится на .
Если делится на и делится на , то делится на .
2) Теорема о делении с остатком.
Для любого целого числа и натурального числа существует единственная пара чисел и таких, что , где - целое, - целое неотрицательное, причем может принимать лишь различных значений: .
Заметим, что если остаток равен 0, то число делится на .
3) Простые и составные числа.
1. Натуральное число называется простым, если оно не имеет натуральных делителей, кроме себя и единицы.
2. Число, не являющееся простым, называется составным.
3. Число 1 не является ни простым, ни составным.
4. Единственное простое четное число – это 2.
4) Взаимно простые числа.
1. Два числа называются взаимно простыми, если они не имеют общих натуральных делителей, кроме единицы.
2. Если число делится на каждое из двух взаимно простых чисел и , то оно делится на их произведение .
3. Если произведение делится на число , причем и взаимно простые, то делится на .
5) Основная теорема арифметики.
Каждое натуральное число имеет единственное ( с точностью до порядка множителей) разложение на простые множители , где - различные простые числа, - натуральные числа.
Наибольший общий делитель, наименьшее общее кратное.
Общим делителем чисел и называется число, на которое делятся оба числа и . Наибольший общий делитель чисел и обозначается НОД.
Для нахождения НОД можно использовать алгоритм Евклида, выполняя последовательно деление с остатком:
Процесс заканчивается после того, как первый раз получен нулевой остаток. Тогда последний ненулевой остаток НОД.
Другой способ нахождения НОДсостоит в разложении чисел и на простые множители, отыскании общих множителей, входящих в оба разложения, и вычислении произведения общих простых множителей в наименьших степенях, с которыми эти множители входят в разложение и .
Общим кратным чисел и называется число, которое делится на и на . Наименьшее общее кратное обозначается НОК.
Для нахождения НОК можно разложить числа и на простые множители, отыскать простые множители, входящие хотя бы в одно разложение, и вычислить произведение этих множителей в наибольших степенях, с которыми эти множители входят в разложение и .
Заметим, что НОД НОК.
Факториал.
Факториалом натурального числа называется число . Факториал числа 0 по определению равен 1. ().
Число определяет количество различных перестановок элементов по порядку.
Желательно знать базовые неравенства (хотя бы неравенство Коши – см.1.):
Неравенство Коши: среднее арифметическое неотрицательных чисел не меньше их среднего геометрического, причем равенство достигается только в случае, когда все данные числа равны. Для неравенство наиболее часто используется и выглядит так:
Пусть . Тогда ; равенство достигается при .
Дополнение:
Неравенства о средних (для ) :
Для положительных и верно следующее: .
Неравенство Коши-Буняковского:
( интерпретируется так: модуль скалярного произведения двух n-мерных векторов
не больше произведения их модулей).
Для справки:
называется средним арифметическим;
называется средним геометрическим;
называется средним гармоническим.
называется средним квадратичным.
Необходимые навыки:
Деление чисел с остатком.
Запись общего вида числа, дающего указанный остаток при делении на указанное число.
Группировка и разложение на множители выражеий.
Решение в целых числах простейших уравнений вида «произведение двух целочисленных выражений равно числу» рассмотрением всех разложений на множители данного числа с учетом знаков множителей. Элементарные навыки простейшего разумного перебора.
Расшифровка десятичной записи числа, то есть запись в виде числового выражения числа, составленного из указанных цифр в указанном порядке.
Действия с помощь метода «от противного».
Умение оценивать значение величин, сравнивать величины с помощью цепочки неравенств.
Способность найти пример указанной комбинации или контрпример неверному общему утверждению.
В нужный момент упорядочить данные величины иногда очень помогает!
Полезно помнить:
На какие цифры могут оканчиваться квадраты натуральных чисел.
Если каждое из двух чисел делится на некоторое число, то любая их линейная комбинация тоже делится на это число.
Произведение двух подряд идущих целых чисел всегда четно (одно из них четное); из трех подряд идущих чисел ровно одно делится на три; ……; из последовательных целых чисел ровно одно делится на .
Произведение последовательных целых чисел всегда делится на .
При любом натуральном числа вида и не являются квадратами натуральных чисел. (Докажите в качестве простого упражнения.)
В логических целочисленных задачах и задачах на делимость часто нужно угадать ответ, а затем доказать, что он верный, приведя пример, подтверждающий достижимость своего ответа, и обязательно доказав, что других(лучших?) ответов быть не может (например, если спрашивают наименьшее количество или значение чего-либо, то нужно привести комбинацию, дающую именно ваш ответ, и доказать, что остальные будут больше, или что величина, меньшая даже на 1, не подойдет).
Советы:
1) Никогда не опускайте руки при виде незнакомой задачи. Она вполне может оказаться решаемой, особенно при спокойном размышлении!
2) Помните, что никаких сложных теорем для решения С6 знать не нужно. Нужен материал 5-8 класса. Конечно, очень бы пригодился опыт решения олимпиадных задач…. Но даже при его отсутствии здравая логика может помочь!
3) Помните, что угаданный ответ – это еще не решение! Но…. Во-первых, ответ может навести на решение. Во-вторых, если угадать (и ПРОВЕРИТЬ) ВСЕ ответы, то можно получить хотя бы балл за С6.
4) Часто решение сводится к анализу ситуации и РАЗУМНОМУ перебору вариантов. Не пренебрегайте такими способами!
5) ОЧЕНЬ внимательно читайте условие задачи. И еще раз перед окончательной записью решения и ответа.
6) Если не знаете, как решать, вываливайте на лист все, связанное с условием, что приходит в голову! Не бойтесь самых странных путей решения. Не вышло – пробуйте другой! Вызывайте любые ассоциации (математические и логические)! И пользуйтесь ими! Конечно, стандартные приемы желательно знать, и уметь ими пользоваться, как тропинкой, чтобы выйти из леса. А уж на тропинку выйти пусть вам поможет логика и интуиция!
Успехов!
Характеристика блоков заданий:
Блок 1 – Подготовка к выполнению задач уровня С3. Некоторые приемы в заданиях весьма умеренного уровня сложности.
Блок 2 – Работа на занятии. Задания С6. Разные. Заданий достаточно много, преподаватель имеет возможность выбрать, какие примеры надо в первую очередь разобрать на семинарах. Желательно хотя бы ознакомиться с темами и приемами.
Блок 3 – Домашнее задание.
Внимание! Задания не всегда расположены в порядке возрастания сложности!
Примеры для разбора на занятии:
Задание
|
Комментарии
|
Ответ
|
Блок 1. (обязательный минимум-подготовка к задачам ЕГЭ)
|
Сколькими нулями оканчивается число 400! ?
|
Перебираем двойки и пятерки в разложении на множители. Понятно, что двоек гораздо больше. Значит, для каждой двойки найдется пятерка! Считаем пятерки. Внимательно! Ведь есть числа. Которые делятся не только на 5, а на 25 и даже 125. Их количество ( с учетом делимости на степень пятерки) и дает ответ.
|
99
|
При каких натуральных значениях дробь есть целое число?
|
Делим с остатком числитель на знаменатель, то есть выделяем целую часть дроби. Дробь равна целому числу плюс «число, деленное на ». Остается выяснить, на какие целые числа делится число, то есть какие значения может принимать , при каких это происходит, и какие их них натуральные.
|
1
|
Решите в целых числах уравнение
|
Единица из правой части раскладывается в произведение двух целых множителей не таким уж большим количеством способов…. Всего-то двумя! (1,1 и -1,-1). Получаем две системы (для каждого из случаев – по одной). Находим ответ.
|
|
Решите в целых числах уравнение .
|
Задача полностью сводится к предыдущей, только надо это увидеть. Добавим в каждую часть уравнения по 2, и левая часть разложится на множители! Правда, решать придется уже не две системы, а 4: множители 2,1; 1,2; -2,-1; -1,-2.
|
|
Решите в целых числах уравнение .
|
Однородное выражение в левой части раскладывается на множители стандартным образом (например, как квадратный трехчлен относительно ). Перебираем разложения тройки.
|
|
Докажите, что уравнение не имеет решений в целых числах.
|
Квадрат целого числа не может давать при делении на 3 остаток 2. (Докажите, перебрав все три возможных остатка при делении на 3 числа, возводимого в квадрат.)
|
|
Найдите общий вид таких чисел, которые при делении на 5 дают остаток 2, а при делении на 3 – остаток 1.
|
Записываем уравнение в целых числах: ,далее возможны варианты.
1) просто перебираем остатки при делении А на 15 - НОК(3;5).
2) приводим подобные; перебираем все остатки при делении на 3 (можно при делении на 5, но это дольше). Ищем, в каком случае возможно равенство, подставляем в выражение для А соответствующий вид : или . Получаем ответ.
3) представляем свободный член – число 1- в виде суммы некоторого количества троек и пятерок, например, . Далее переносим все «тройки» в одну часть уравнения, все «пятерки» - в другую, и делаем вывод о делимости обеих частей, например, на 3. Получаем общий вид числа . Так, пожалуй, быстрее всего.
|
|
Докажите, что при любом целом число делится на 120.
|
Раскладываем на множители. Произведение пяти последовательных целых чисел должно делиться на 5!=120.
|
|
Решите в натуральных числах уравнение .
|
Если , то левая часть уравнения оканчивается на 3 ( так как факториалы чисел , больших 4, содержат множители 5 и 2, то есть оканчиваются 0). Квадрат же не может заканчиваться тройкой. Перебираем .
|
|
Решите в простых числах уравнение .
|
Либо левую часть представляем как разность квадратов и перебираем разложения 9 на множители, либо переносим 9 влево, а - вправо; тогда и (одной четности) – четные числа, отличающиеся на 6, то есть одно из них делится не только на 2, но и на 4. Следовательно, - четное простое число, то есть 2.
|
|
Блок 2. (задания уровня ЕГЭ)
|
Найдите все простые числа , для каждого из которых существует такое целое число , что дробь сократима на .
|
Кроме числителя и знаменателя, можно найти еще числа, делящиеся на . Поиском занимаемся, либо подгадывая такие комбинации исходных чисел, чтобы степени уменьшались (а в конце получаем число, которое точно делится на ), либо с использованием деления с остатком ( сродни алгоритму Евклида).
|
2,3
|
Найдите все такие простые числа p, для каждого из которых существует такое целое число k, что число p является общим делителем чисел и .
|
Задача аналогична предыдущей.
|
3, 5, 7.
|
Наибольшее целое число, не превосходящее , равно . Найдите все такие действительные значения .
|
Записываем условие-ограничение, получаем неравенство на . Решаем. Далее замечаем, что ; выражаем через , подставляем в полученное решение неравенства. Выбираем наибольшее целое . Находим , пишем в ответ.
|
|
Найдите все натуральные числа , для которых верно равенство .
|
Возможны различные рассуждения при решении этой задачи, и мы ни в коем случае не претендуем на уникальность или оптимальность решения. Предложим один из вариантов. Используем ограничения, которые очень легко получить, зная, что переменные – натуральные числа, то есть не меньше 1. Далее получаем конечный (да и небольшой) набор возможных значений одной из переменных, и задача сводится к трем стандартным уравнениям в целых числах. Иногда в подобных задачах для получения ограничений приходится использовать базовые неравенства.
|
|
Найдите все целые значения и , для которых выполняется равенство .
|
Если раскрыть скобки и использовать разложение на множители, то получим стандартное уравнение, решаемое конечным перебором.
|
|
Решите в натуральных числах уравнение , где .
|
Домножением на знаменатели сводим задачу к предыдущей.
Есть другой способ решения, использующий то, что из двух положительных слагаемых в левой части должно быть одно, которое не менее половины правой части. Но со знаменателем 25 такое решение менее удобно.
|
|
Решите в натуральных числах уравнение .
|
Задача решается методом «бесконечного спуска». Рассматривается четность-нечетность входящих в условие переменных и делается обобщающий вывод. Фактически, задача неявно предполагает действия методом математической индукции.
|
Решений нет
|
Решите в натуральных числах уравнение .
|
Несложные рассуждения с делимостью, правда, на факториал, и аккуратность в конце приводят к ответу, довольно очевидному при взгляде на уравнение. Надо заметить, что здесь приходится упорядочить переменные, отдельно рассмотрев случай равенства.
|
|
Найдите все тройки натуральных чисел , удовлетворяющие уравнению .
|
Опять упорядочим переменные, проведем небольшую оценку и сведем все к конечному перебору.
|
|
Решите в натуральных числах уравнение .
|
В условии бросаются в глаза семерки в правой части. Точнее, на 7 она делится, а на 49 уже нет… Так что в связи с делимостью на 7 придется рассмотреть значения меньше 7 (перебрать легко, тем более если еще что-нибудь отсеять….) и не меньше 7 (здесь поработать с делимостью).
|
|
Найдите все пары натуральных чисел и , являющиеся решениями уравнения .
|
Пара нетривиальных задач с коротким решением для наблюдательных людей. Надо хорошо знать свойства, связанные с четностью и со степенями 3….. Если вы угадаете, делимость на что надо рассматривать. То есть шанс решить задачу!
|
|
Найдите все пары натуральных чисел и , являющиеся решениями уравнения .
|
|
Винтики можно разложить в пакетики, а пакетики упаковать в коробки, по 3 пакетика в одну коробку. Можно эти же винтики разложить в пакетики так, что в каждом пакетике будет на 3 винтика больше, чем раньше, но тогда в каждой коробке будет лежать по 2 пакетика, а коробок потребуется на 2 больше. Какое наибольшее количество винтиков может быть при таких условиях?
|
Классическая текстовая задача на составление и решение уравнения в целых числах со смысловыми ограничениями. Внимательно читаем условие и вопрос задачи!
|
840
|
Перед каждым из чисел 2;3;…;6 и 10;11;…;20 произвольным образом ставят знак плюс или минус, после чего к каждому из образовавшихся чисел первого набора прибавляют каждое из образовавшихся чисел второго набора, а затем все 55 полученных результатов складывают. Какую наименьшую по модулю и какую наибольшую сумму можно получить в итоге?
|
На один из вопросов задачи ответить легко, если знать, как суммируется прогрессия, или потратить просто побольше времени на складывание чисел. (да, во второй задаче надо сначала заметить произведение двух скобок).
Со вторым вопросом значительно сложнее. Надо сделать целых две вещи: первое – доказать, что 0 получиться не может(четность). Второе – привести пример, когда получается 1 (это тоже нетривиально, нужна фантазия).
|
1 и 1045
|
Каждое из чисел 2;3;…;7 умножают на каждое из чисел 13; 14;…;21 и перед каждым из полученных произведений ставят знак плюс или минус, после чего все 54 полученных результата складывают. Какую наименьшую по модулю и какую наибольшую сумму можно получить в итоге?
|
1 и 4131
|
Какое наибольшее число членов может иметь геометрическая прогрессия, все члены которой – различные натуральные числа, большие 210 и меньшие 350?
|
Логическая задача, включающая необходимость придумать пример, подтверждающий догадку об ответе, и обосновать, что ответ верный – то есть в нашем случае аккуратно доказать с помощью неравенств, что пяти членов уже быть не может.
|
4
|
Последние члены двух конечных арифметических прогрессий и совпадают, а сумма всех совпадающих (взятых по одному разу) членов этих погрессий равна 815. Найдите число членов в каждой прогрессии.
|
Классическая задачка на совмещение двух прогрессий и постановку ограничений. Уравнение в целых числах. См.подготовительные задания.
|
49 и 29
|
Найдите все пары натуральных чисел и , удовлетворяющие равенству ( в левой части равенства стоит число, получаемое приписыванием десятичной записи числа перед десятичной записью числа )
|
. Оценка длины десятичной записи числа. Хитрое сведение к конечному перебору с помощью оценок. Выполните затем аналогичную задачу самостоятельно.
|
|
Число равно произведению 10 различных натуральных чисел, больших 1. Какое наименьшее число различных натуральных делителей (включая единицу и само число) может иметь число ?
|
Разумный перебор делителей, подсчет их количества, включающий расположение по возрастанию (упорядочение опять сильно помогает решению) не исчерпывают решение. Опять-таки надо привести пример того. Что оптимальное значение достижимо.
|
56
|
Сумма шестнадцати чисел равна . Оказалось, что сумма каждых пятнадцати из этих шестнадцати чисел положительна. Какое наименьшее целое значение может иметь наименьшее из данных чисел?
|
НЕОБХОДИМО упорядочение чисел. Далее легкая, но красивая оценка нужного числа и, конечно, как же без примера реализации… Проделайте в домашней задаче все то же самое самостоятельно.
|
-6
|
Блок 3. (домашнее задание)
|
Решите в целых числах уравнение
|
|
Решите в целых числах уравнение .
|
|
Решите в целых числах уравнение .
|
|
Докажите, что уравнение не имеет решений в целых числах.
|
|
Найдите общий вид таких чисел, которые при делении на 3 дают остаток 1, а при делении на 4 – остаток 3.
|
|
При каких натуральных число делится на 120?
|
При всех
|
Решите в натуральных числах уравнение .
|
|
. Найдите все простые числа , для каждого из которых существует такое целое число , что дробь можно сократить на .
|
2, 5
|
Решите в натуральных числах уравнение .
|
|
Решите в натуральных числах уравнение .
|
|
Перед каждым из чисел 5;6;…;10 и 12;13;…;16 произвольным образом ставят знак плюс или минус, после чего к каждому из образовавшихся чисел первого набора прибавляют каждое из образовавшихся чисел второго набора, а затем все 30 полученных результатов складывают. Какую наименьшую по модулю и какую наибольшую сумму можно получить в итоге?
|
1 и 645
|
Найдите все пары натуральных чисел и , удовлетворяющие равенству ( в левой части равенства стоит число, получаемое приписыванием десятичной записи числа перед десятичной записью числа )
|
|
Болтики можно разложить в пакетики, а пакетики упаковать в коробки, по 2 пакетика в одну коробку. Можно эти же болтики разложить в пакетики так, что в каждом пакетике будет на 5 болтиков меньше, чем раньше, но тогда в каждой коробке будет лежать по 3 пакетика, а коробок потребуется на 2 меньше. Какое наименьшее количество болтиков может быть при таких условиях?
|
594
|
Сумма восьми чисел равна . Оказалось, что сумма каждых семи из этих восьми чисел положительна. Какое наименьшее целое значение может иметь наименьшее из данных чисел?
|
-7
| |
|
|
Скачать 169.68 Kb.