Обобщенный алгоритм евклида решение диофантовых уравнений

Элективный курс Сказки Шехерезады и уравнения Диофанта Балашов 2009 Содержание

Главная > Элективный курс

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Применение алгоритма Евклида для нахождения наибольшего общего делителя двух чисел (повторение).

Существует довольно простой прием, позволяющий находить наибольший делитель двух натуральных чисел. Этот прием называется алгоритмом Евклида. Вы с ним познакомились еще при изучении курса математики в 5 – 6 классах. Евклид, великий ученый, живший около 2000 лет назад, занимался не только геометрией, которая носит его имя. Ему принадлежит решение ряда важных задач арифметики и, в частности, тот способ нахождения наибольшего общего делителя, который мы сегодня будем использовать при изучении нового материала. А сейчас повторим суть алгоритма Евклида .

Чтобы найти наибольший общий делитель двух чисел:

1) надо большее из двух чисел разделить на меньшее;

2) потом меньшее из чисел на остаток при первом делении;

3) затем остаток при первом делении на остаток при втором делении и вести этот процесс до тех пор, пока не произойдет деление без остатка. Последний отличный от нуля остаток и есть искомый НОД двух данных чисел

Рассмотрим пример. Найти НОД (645; 381).

Разделим с остатком 645 на 381. Мы получим: 645=381·1+264.

Далее разделим с остатком 381 на 264, получим: 381=264·1+117.

Теперь разделим с остатком 264 на 117, получим: 264=117·2+30.

Продолжим процесс деления, разделим с остатком 117 на 30, получим: 117=30·3+27. Далее, 30=27·1+3. Следующий шаг – делим 27 на 3, получаем, что 27=3·9 +0, т. е. 27 делится на 3 без остатка. Значит, наибольший общий делитель чисел 27 и 3 равен 3, следовательно, и наибольший общий делитель чисел 645 и 381 равен 3, т. е. последнему отличному от нуля остатку.

Таким образом, НОД (645; 381) = 3.

Прием разыскания наибольшего общего делителя, примененный в этом примере, и представляет собой алгоритм Евклида.

2. Вывод формул для решения диофантовых уравнений с использованием алгоритма Евклида.

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

с использованием алгоритма Евклида, докажем утверждение о том, что наибольший общий делитель двух чисел есть последний отличный от нуля остаток в цепочке указанных в примере действий .

Чтобы доказать утверждение о наибольшем общем делителе, представим описанный процесс в виде следующей цепочки равенств: если a > b , то

·b = r 1 q 1 + r 2

r 1 = r 2 q 2 + r 3 (2)

r n – 1 = r n q n

Здесь r 1 , . . . , r n — положительные остатки, убывающие с возрастанием номера. Отсутствие остатка в последнем равенстве следует из того, что натуральные числа r n не могут убывать бесконечно, поэтому на некотором шаге остаток станет нулевым.

Обратимся к системе (2). Из первого равенства, выразив остаток r 1 через a и b , получим r 1 = a – b · q 0 . Подставляя его во второе равенство, найдём r 2 = b (1 + q 0 q 1 ) – a · q 1 . Продолжая этот процесс дальше, мы сможем выразить все остатки через a и b , в том числе и последний: r n = Aa + Bb . В результате нами доказано

что найдутся такие целые числа A и B , что d = Aa + Bb . Заметим, что коэффициенты A и B имеют разные знаки; если НОД ( a , b ) = 1 , то Aa + Bb = 1 . Как найти числа A и B , видно из алгоритма Евклида.

Перейдем теперь к решению линейного уравнения с двумя неизвестными:

Возможны два случая: либо число c делится на d = НОД( a , b ) , либо нет.

В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a 1 x + b 1 y = c 1 , коэффициенты которого

a 1 = a / d и b 1 = b / d взаимно просты.

Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делиться на d и поэтому не может равняться числу c , которое на d не делится.

Итак, мы можем ограничиться случаем, когда в уравнении (1) коэффициенты a и b взаимно просты. На основании предыдущего предложения найдутся такие целые числа х 0 и у 0 , что ax 0 + by 0 = 1 , откуда пара (сх 0 , су 0 ) удовлетворяет уравнению (1). Вместе с ней уравнению (1) удовлетворяет бесконечное множество пар ( x , у) целых чисел, которые можно найти по формулам

x = cx 0 + bt, y = cy 0 – at. (3)

Здесь t – любое целое число. Нетрудно показать, что других целочисленных решений уравнение ах + by = c не имеет. Решение, записанное в виде (3), называется общим решением уравнения (1). Подставив вместо t конкретное целое число, получим его частное решение.

Примечание . Название «лекция» как будто говорит о том, что активная роль здесь принадлежит лишь самому учителю, учащимся предоставляется пассивная роль – внимательно слушать рассказ учителя и выполнять в тетради те записи, которые учитель выполняет на классной доске. Если бы это было именно так, то данная форма обучения оказалось бы мало эффективной. Современные требования обучения математике предполагают, что даже в том случае, когда учитель является главным действующим лицом,
необходима активная деятельность самих учащихся. Поэтому лекция учителя должна пробуждать у учащихся интерес и потребность к активной умственной деятельности.

По ходу лекции следует обратиться с вопросами к учащимся . Например: Какие уравнения называются диофантовыми? Какой вид имеет линейное диофантово уравнение? Какие условия накладываются на его коэффициенты? Какой способ решения уравнения мы использовали на предыдущем занятии?

Также на занятиях, где материал изучается крупным блоком, целесообразно создание таблицы в виде конспекта изложенного учителем нового материала. Этот конспект должен стать информационно-справочной таблицей и сыграть свою
роль на занятиях тематического или итогового повторения. Сформулируем некоторые требования к его оформлению. Материал в конспекте должен быть разделен на несколько самостоятельных, логически связанных между собой блоков. В него желательно внести вспомогательные вопросы, с помощью которых готовится введение нового, узловые вопросы темы и ее практическое применение.

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

Как разработать такой конспект? Учитель сначала разрабатывает конспект полностью на листе бумаге стандартного размера. На другом таком же листе он выписывает конспект-заготовку в строгом расположении текста на основном конспекте. Этот фрагментарный конспект необходимо размножить, чтобы к лекции такой конспект-заготовку имел каждый ученик. Точно такой конспект «с пропусками» учитель должен заранее написать на доске
перед началом лекции или подготовить его компьютерный вариант для использования в классе с интерактивной доской. Для проведения данной лекции был подготовлен такой
конспект-заготовка (Приложение 4).

3. Примеры решения диофантовых уравнений с использованием алгоритма Евклида.

Рассмотрим решение заданий №6 (а), №7 из Приложения 1.

Задание №6 . Решить уравнение на множестве целых чисел

НОД(7;11)=1, Найдем значение х 0 и у 0 для получения решений уравнения по формулам (3). Применим алгоритм Евклида к числам 11 и 7:

Таким образом, получаем: , следовательно х 0 = –3, у 0 =2

Запишем общее решение уравнения на множестве целых чисел согласно формулам (3):

Придавая конкретные целые значения t , можно получить частные решения уравнения. Например, при t =1, имеем x = –196, у=131.

Задача №7 . Для газификации жилого дома требуется проложить газопровод протяженностью 150 м. Имеются трубы 13 м и 9м длиной. Сколько требуется труб, чтобы не приходилось их разрезать при прокладке газопровода.

Пусть требуется x труб по 9 м, и у труб по 13м. Составим и решим уравнение: 9х+13у=150.

НОД(9;13)=1, уравнение разрешимо во множестве целых чисел.

Найдем значение х 0 и у 0 для получения решений уравнения по формулам (3). Применим алгоритм Евклида к числам 13 и 9:

Запишем общее решение уравнения согласно формулам (3).

Так как x и y неотрицательные целые числа, то чтобы найти значение t , решим систему неравенств:

Ответ. Для прокладывания газопровода потребуется 8 труб длиной по 9м и 6 труб длиной по 13м.

4 . В домашнее задание для учащихся необходимо включить подготовку по теоретическому материалу и практические задания.

Учащиеся должны ответить на следующие вопросы.

В чем суть алгоритма Евклида?

Когда уравнение (1) разрешимо во множестве целых чисел?

По каким формулам находится общее решение диофантова уравнения первой степени с двумя переменными с использованием алгоритма Евклида? Укажите, что обозначают буквы, входящие в эти формулы.

При выполнении домашнего задания используется опорный конспект лекции, в котором выделены основные вопросы, рассмотренные на занятии, и заполнены соответственно имеющиеся пропуски (Приложение 4).

В качестве практических заданий можно предложить для решения задания №6 (б), №8 из Приложения 1. Также можно предложить составить сюжетную задачу, решение которой сводится к уравнению из №6 (б) на множестве целых неотрицательных или натуральных чисел. Найти ее решения.

Решение диофантовых уравнений с использованием алгоритма Евклида

Актуализация знаний ( проверка знания теории и выполнения практических заданий).

Решение задач с использованием алгоритма Евклида.

Постановка домашнего задания.

Оборудование: заполненные конспекты – заготовки предыдущей лекции, карточки с заданиями для фронтальной и групповой работы.

Актуализация знаний. Проведение первого этапа занятия – практикума учитель может спланировать по своему усмотрению. Необходимо организовать проверку выполнения домашнего задания, включающего как теоретические вопросы, так и практические задания.

Решение задач с использованием алгоритма Евклида .

Задания для решения выбираются по принципу: от простого к сложному. Для овладения методом решения диофантовых уравнений с использованием алгоритма Евклида можно предложить вначале решить уравнения, не связанные, с какой либо реальной ситуацией. Например, № 6 (в, г). Затем можно предложить решение текстовых задач на составление линейных диофантовых уравнений. Например, № 9, 10. Все задания указаны из Приложения 1. Задания можно выполнить в группах, а затем проверить полученные ответы. Ниже приведем решение задачи №9.

Неотъемлемой частью занятия – практикума является решение и нестандартных задач, заданий повышенной трудности. В процессе их выполнения можно использовать прием разбиения на подзадачи. К таким заданиям можно отнести и задачу № 11, которую мы далее рассмотрим.

Заметим, что в ходе решения задач, учащиеся могут опираться на заполненный опорный конспект предыдущей лекции, в котором выделен способ решения диофантовых уравнений с использованием алгоритма Евклида.

Задача №9. Транспортные организации имеют в наличие машины вместимостью 3, 5 т и 4, 5 т. Следует перевезти груз весом 53 т. Сколько машин нужно взять для одного рейса?

Пусть x машин по 3,5 т.; у машин по 4, 5 т. Составим и решим уравнение: 3,5х+4,5у=53. Перейдем к уравнению с целыми коэффициентами, например, умножим обе части уравнения на 2. Получим: 7х+9у=106.

НОД(7, 9)=1, уравнение имеет целые решения.

Так как t – принимает целые значения, то системе неравенств удовлетворяют значения t =-47 и t =-46. Получим решение диофантова уравнения в натуральных числах:

Таким образом, для одного рейса можно взять:

А) 1 машину вместимостью 3,5 т и 11 машин вместимостью 4,5 т;

В) 10 машин вместимостью 3,5 т и 4 машины вместимостью 4,5 т.

Полезно обратить внимание на то, какой из возможных вариантов будет наиболее эффективным для работы предприятия с экономической точки зрения (экономия бензина, экономия средств на оплату труда водителям и т.д.) .

Задача №11 . Школа получила 1 млн. руб. на приобретение 100 единиц учебного оборудования (на всю сумму без сдачи). Администрации школы предложили, оборудование стоимостью 3000, 8000 и 12000 руб. за единицу. Сколькими способами школа может закупить это оборудование. Укажите один из способов.

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

1 ) составление системы уравнений .

Пусть приобретено x единиц оборудования по 12000 руб., y единиц оборудования по 8000 руб., z единиц оборудования по
3000 руб.

Всего приобретено 100 единиц оборудования, т.е. x + y + z = 100 , причем на приобретение 100 единиц оборудования затрачено 1 млн. руб., т.е.

12000 x + 8000 y + 3000 z = 1 000 000,

12x + 8y + 3z = 1000 .

Таким образом, получаем систему двух уравнений с тремя неизвестными:

Вопрос учителя: всегда ли задача будет иметь решение? Иначе: какими
должны быть x , y , z ?

( ответ: x >0, y >0, z >0 )

2) обсуждение решения системы.

Во-первых, исключим z , путем вычитания из второго уравнения первого, умноженного на 3. Следовательно, получаем диофантово уравнение 1-ой степени с двумя неизвестными 9 x + 5 y = 700.

Во-вторых, его можно решить способом с использованием алгоритма Евклида.

3) оформление решения задачи.

Так как уже получили уравнение, которое решается известным способом, то оформление решения можно предложить выполнить учащимся дома. В результате решения получается, что приобрести оборудование библиотека может шестью способами. Укажем одно из частных решений задачи: x=65 , y=23, z=12 , т.е. школа на 1 млн. руб. может
приобрести 65 единиц оборудования по 12 тыс. руб., 23 единицы оборудования по 8 тыс. руб., 12 единиц оборудования по 3 тыс. руб.

3. Постановка домашнего задания.

В качестве домашнего задания можно преложить учащимся решить задачи № 2; №3; №5 из Приложения 1 с использованием алгоритма Евклида.

Решение диофантовых уравнений с использованием

План занятия совпадает с планом школьной лекции на указанную тему.

Понятие цепной дроби. Представление рациональных чисел в виде цепной дроби

Формулы для решения диофантовых уравнений с использованием цепной дроби

Примеры решения диофантовых уравнений с использованием цепной дроби.

Оборудование: конспект – заготовка лекции на доске и индивидуальные заготовки для каждого ученика.

Занятие № 5 по своей структуре аналогично занятию №3. В качестве примеров решения диофантовых уравнений с использованием цепной дроби, можно рассмотреть задания из Приложения 1. Заметим, что можно взять уже ранее решенные задачи и выполнить их решение новым способом.

Понятие цепной дроби. Представление рациональных чисел в виде цепной дроби

Обратимся вновь к алгоритму Евклида. Из первого равенства системы (2) вытекает, что дробь a / b можно записать в виде суммы целой части и правильной дроби: . Из второго равенства той же системы имеем. Значит,

Продолжим этот процесс до тех пор, пока не придём к знаменателю q п

В результате мы представим обыкновенную дробь a / b в следующем виде: . Эйлер назвал дробь, стоящую в правой части равенства непрерывной . Приблизительно в тоже время в Германии появился другой термин – цепная дробь . Так за этими дробями и сохранились оба названия. Ввиду громоздкости развёрнутой записи цепной дроби применяют компактную запись

a / b = [ q 0 ; q 1 , q 2 , …, q п ] .

Представить рациональное число в виде цепной дроби.

Очевидно, что любое рациональное число, и только оно записывается в виде конечной цепной дроби. Иррациональным числам соответствуют бесконечные цепные дроби.

Если при построении цепной дроби остановиться на знаменателе q k , то получиться дробь [ q 0 ; q 1 , q 2 , …, q к ] , которую называют к-й подходящей дробью для искомой и обозначают Найдем вид некоторых подходящих дробей:

Для рационального числа a / b последовательность подходящих дробей конечна, и ее последний элемент Нетрудно заметить, что имеют место следующие рекуррентные соотношения:

(4)

Формулы для решения диофантовых уравнений с использованием цепной дроби

Вернемся к уравнению: ax + by = c (1). Напомним, что в нем a и b взаимно просты. Решение этого уравнения «способом цепной дроби» завершается применением готовых формул (доказательство которых можно найти в специальных пособиях), представляющих общее решение данного уравнения

(5)

Диофантовы уравнения

Что такое «решение задач подбором», и можно ли их решать иначе?

По отзывам сибмам, настоящим камнем преткновения в школьном курсе математики не только для учеников, но и для родителей становятся диофантовы уравнения. Что это такое и как их правильно решать? Разобраться нам помогли учитель математики образовательного центра «Горностай» Аэлита Бекешева и кандидат физико-математических наук Юрий Шанько.

Кто такой Диофант?

Еще древние египтяне для удобства рассуждений придумали специальное слово, обозначавшее неизвестное число, но в то время не было еще знаков действий и знака равенства, поэтому и записывать уравнения они не умели.

Первым, кто придумал, как можно записать уравнение, был замечательный ученый Диофант Александрийский. Александрия была большим культурным, торговым и научным центром древнего мира. Этот город существует и сейчас, он находится на Средиземноморском побережье Египта.

Жил Диофант, по-видимому, в III веке н.э. и был последним великим математиком античности. До нас дошли два его сочинения — «Арифметика» (из тринадцати книг сохранилось шесть) и «О многоугольных числах» (в отрывках). Творчество Диофанта оказало большое влияние на развитие алгебры, математического анализа и теории чисел.

А ведь вы знаете кое-что о диофантовых уравнениях…

Диофантовы уравнения знают все! Это задачки для учеников младших классов, которые решаются подбором.

” Например, «сколькими различными способами можно расплатиться за мороженое ценой 96 копеек, если у вас есть только копейки и пятикопеечные монеты?»

Если дать диофантовому уравнению общее определение, то можно сказать, что это алгебраическое уравнение с дополнительным условием: все его решения должны быть целыми числами (а в общем случае и рациональными).

” Зачастую мамы (особенно те, кто окончил школу еще при развитом социализме) полагают, что основная цель таких задач – научить детей расплачиваться мелочью за мороженое. И вот, когда они искренне убеждены, что раскладывание мелочи кучками осталось далеко в прошлом, их любимый семиклассник (или восьмиклассник) подходит с неожиданным вопросом: «Мама, как это решать?», и предъявляет уравнение с двумя переменными. Раньше таких задачек в школьном курсе не было (все мы помним, что уравнений должно быть столько же, сколько и переменных), так что мама не-математик нередко впадает в ступор. А ведь это та же самая задача про мелочь и мороженое, только записанная в общем виде!

Кстати, а зачем к ней вдруг возвращаются в седьмом классе? Все просто: цель изучения диофантовых уравнения – дать основы теории целых чисел, которая дальше развивается как в математике, так и в информатике и программировании. Диофантовы уравнения часто встречаются среди задач части «С» единого госэкзамена. Трудность, прежде всего в том, что существует множество методов решения, из которых выпускник должен выбрать один верный. Тем не менее, линейные диофантовы уравнения ax + by = c могут быть решены относительно легко с помощью специальных алгоритмов.

Алгоритмы для решения диофантовых уравнений

— Изучение диофантовых уравнения начинается в углубленном курсе алгебры с 7 класса. В учебнике Ю.Н. Макарычева, Н.Г. Миндюка приводятся некоторые задачи и уравнения, которые решают с использованием алгоритма Евклида и метода перебора по остаткам, — рассказывает Аэлита Бекешева. — Позже, в 8 – 9 классе, когда уже рассматриваем уравнения в целых числах более высоких порядков, показываем ученикам метод разложения на множители, и дальнейший анализ решения этого уравнения, оценочный метод. Знакомим с методом выделения полного квадрата. При изучении свойств простых чисел знакомим с малой теоремой Ферма, одной из основополагающих теорем в теории решений уравнений в целых числах. На более высоком уровне это знакомство продолжается в 10 – 11 классах. В это же время мы подводим ребят к изучению и применению теории «сравнений по модулю», отрабатываем алгоритмы, с которыми знакомились в 7 – 9 классах. Очень хорошо это материал прописан в учебнике А.Г. Мордковича «Алгебра и начала анализа, 10 класс» и Г.В. Дорофеева «Математика» за 10 класс.

Алгоритм Евклида

Сам метод Евклида относится к другой математической задаче – нахождению наибольшего общего делителя: вместо исходной пары чисел записывают новую пару – меньшее число и разность между меньшим и большим числом исходной пары. Это действие продолжают до тех пор, пока числа в паре не уравняются – это и будет наибольший общий делитель . Разновидность алгоритма используется и при решении диофантовых уравнений — сейчас мы вместе с Юрием Шанько покажем на примере, как решать задачи «про монетки».

— Рассматриваем линейное диофантово уравнение ax + by = c, где a, b, c, x и y — целые числа. Как видите, одно уравнение содержит две переменных. Но, как вы помните, нам нужны только целые корни, что упрощает дело — пары чисел, при которых уравнение верно, можно найти.

Впрочем, диофантовы уравнения не всегда имеют решения. Пример: 4x + 14y = 5. Решений нет, т.к. в левой части уравнения при любых целых x и y будет получаться четное число, а 5 — число нечетное. Этот пример можно обобщить. Если в уравнении ax + by = c коэффициенты a и b делятся на какое-то целое d, а число c на это d не делится, то уравнение не имеет решений. С другой стороны, если все коэффициенты (a, b и c) делятся на d, то на это d можно поделить все уравнение.

Например, в уравнении 4x + 14y = 8 все коэффициенты делятся на 2. Делим уравнение на это число и получаем: 2𝑥 + 7𝑦 = 4. Этот прием (деления уравнения на какое-то число) позволяет иногда упростить вычисления.

Зайдем теперь с другой стороны. Предположим, что один из коэффициентов в левой части уравнения (a или b) равен 1. Тогда наше уравнение уже фактически решено. Действительно, пусть, например, a = 1, тогда мы можем в качестве y взять любое целое число, при этом x = c − by. Если научиться сводить исходное уравнение к уравнению, в котором один из коэффициентов равен 1, то мы научимся решать любое линейное диофантово уравнение!

Я покажу это на примере уравнения 2x + 7y = 4.

Его можно переписать в следующем виде: 2(x + 3y) + y = 4.

Введем новую неизвестную z = x + 3y, тогда уравнение запишется так: 2z + y = 4.

Мы получили уравнение с коэффициентом один! Тогда z — любое число, y = 4 − 2z.

Осталось найти x: x = z − 3y = z − 3(4 − 2z) = 7z − 12.

” В этом примере важно понять, как мы перешли от уравнения с коэффициентами 2 и 7 к уравнению с коэффициентами 2 и 1. В данном случае (и всегда!) новый коэффициент (в данном случае — единица) это остаток от деления исходных коэффициентов друг на друга (7 на 2).

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

Давайте попрообуем решить более сложное уравнение, предлагает Аэлита Бекешева.

Рассмотрим уравнение 13x — 36y = 2.

Шаг №1

36/13=2 (10 в остатке). Таким образом, исходное уравнение можно переписать следующим образом: 13x-13 * 2y-10y=2. Преобразуем его: 13(x-2y)-10y=2. Введем новую переменную z=x-2y. Теперь мы получили уравнение: 13z-10y=2.

Шаг №2

13/10=1 (3 в остатке). Исходное уравнение 13z-10y=2 можно переписать следующим образом: 10z-10y+3z=2. Преобразуем его: 10(z-y)+3z=2. Введем новую переменную m=z-y. Теперь мы получили уравнение: 10m+3z=2.

Шаг №3

10/3=3 (1 в остатке). Исходное уравнение 10m+3z=2 можно переписать следующим образом: 3 * 3m+3z+1m=2. Преобразуем его: 3(3m+z)+1m=2. Введем новую переменную n=3m+z. Теперь мы получили уравнение: 3n+1m=2.

Ура! Мы получили уравнение с коэффициентом единица!

m=2-3n, причем n может быть любым числом. Однако нам нужно найти x и y. Проведем замену переменных в обратном порядке. Помните, мы должны выразить x и y через n, которое может быть любым числом.

y=z-m; z=n-3m, m=2-3n ⇒ z=n-3 * (2-3n), y=n-3*(2-3n)-(2-3n)=13n-8; y=13n-8

x=2y+z ⇒ x=2(13n-8)+(n-3*(2-3n))=36n-22; x=36n-22

Пусть n=5. Тогда y=57, x=158. 13_*(158)-36 _* (57)=2

Да, разобраться не очень просто, зато теперь вы всегда сможете решить в общем виде задачи, которые решаются подбором!

Решаем задачи на подбор чисел

Примеры задач для учеников младших классов, которые решаются подбором: посоревнуйтесь с ребенком, кто решит их быстрее: вы, используя алгорит Евклида, или школьник — подбором?

Задача про лапы

Условия

В клетке сидят куры и кролики. Всего у них 20 лап. Сколько там может быть кур, а сколько — кроликов?

Решение

Пусть у нас будет x кур и y кроликов. Составим уравнение: 2х+4y=20. Сократим обе части уравнения на два: x+2y=10. Следовательно, x=10-2y, где x и y — это целые положительные числа.

Ответ

Число кроликов и куриц: (1; 8), (2; 6), (3; 4), (4; 2), (5; 0)

Согласитесь, получилось быстрее, чем перебирать «пусть в клетке сидит один кролик. »

Задача про монетки

Условия

У одной продавщицы были только пяти- и двухрублевые монетки. Сколькими способами она может набрать 57 рублей сдачи?

Решение

Пусть у нас будет x двухрублевых и y пятирублевых монеток. Составим уравнение: 2х+5y=57. Преобразуем уравнение: 2(x+2y)+y=57. Пусть z=x+2y. Тогда 2z+y=57. Следовательно, y=57-2z, x=z-2y=z-2(57-2z) ⇒ x=5z-114. Обратите внимание, переменная z не может быть меньше 23 (иначе x, число двухрублевых монеток, будет отрицательным) и больше 28 (иначе y, число пятирублевых монеток, будет отрицательным). Все значения от 23 до 28 нам подходят.

Линейное диофантово уравнение и 4 способа его решения

Разделы: Математика

Првило 1. Если с не делится на d, то уравнение ах + ву = с не имеет решений в целых числах. Н.О.Д.(а,в) = d.

Правило 2. Чтобы найти решение уравнения ах + ву = с при взаимно-простых а и в, нужно сначала найти решение (Х_о ; у_о) уравнения ах + ву = 1; числа СХ_о , Су_о составляют решение уравнения ах + ву = с.

Решить в целых числах (х,у) уравнение

Первый способ. Нахождение частного решения методом подбора и запись общего решения.

Знаем, что если Н.О.Д.(а;в) =1, т.е. а и в взаимно-простые числа, то уравнение (1)

имеет решение в целых числах х и у. Н.О.Д.(5;8) =1. Методом подбора находим частное решение: Х_о = 7; у_о =2.

Итак, пара чисел (7;2) — частное решение уравнения (1).

Значит, выполняется равенство: 5 x 7 – 8 x 2 = 19 … (2)

Вопрос: Как имея одно решение записать все остальные решения?

Вычтем из уравнения (1) равенство (2) и получим: 5(х -7) – 8(у — 2) =0.

Отсюда х – 7 = . Из полученного равенства видно, что число (х – 7) будет целым тогда и только тогда, когда (у – 2) делится на 5, т.е. у – 2 = 5n, где n какое-нибудь целое число. Итак, у = 2 + 5n, х = 7 + 8n, где n Z.

Тем самым все целые решения исходного уравнения можно записать в таком виде:

n Z.

Второй способ. Решение уравнения относительно одного неизвестного.

Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент. 5х — 8у = 19 х = .

Остатки при делении на 5: 0,1,2,3,4. Подставим вместо у эти числа.

Если у = 0, то х = =.

Если у =1, то х = =.

Если у = 2, то х = = = 7 Z.

Если у =3, то х = =.

Если у = 4 то х = =.

Итак, частным решением является пара (7;2).

Тогда общее решение: n Z.

Третий способ. Универсальный способ поиска частного решения.

Для решения применим алгоритм Евклида. Мы знаем, что для любых двух натуральных чисел а, в, таких, что Н.О.Д.(а,в) = 1 существуют целые числа х,у такие, что ах + ву = 1.

1. Сначала решим уравнение 5m – 8n = 1 используя алгоритм Евклида.

2. Затем найдем частное решение уравнения (1)по правилу 2.

3. Запишем общее решение данного уравнения (1).

1. Найдем представление: 1 = 5m – 8n. Для этого используем алгоритм Евклида.

8 = 5 1 + 3.