Занятие 3
Решение диофантовых уравнений
с использованием алгоритма Евклида
План занятия совпадает с планом школьной лекции на указанную тему.
План лекции
Применение алгоритма Евклида для нахождения наибольшего
общего делителя двух чисел (повторение).
Вывод формул для решения диофантовых уравнений с использованием алгоритма Евклида.
Примеры решения диофантовых уравнений с использованием алгоритма Евклида.
Оборудование: конспект-заготовка лекции на доске и индивидуальные заготовки для каждого ученика (Приложение 4).
Ход занятия
Применение алгоритма Евклида для нахождения наибольшего общего делителя двух чисел (повторение)
Существует довольно простой прием, позволяющий находить наибольший делитель двух натуральных чисел. Этот прием называется алгоритмом Евклида. Вы с ним познакомились еще при изучении курса математики в 5—6 классах. Евклид, великий ученый, живший около 2 000 лет назад, занимался не только геометрией, которая носит его имя. Ему принадлежит решение ряда важных задач арифметики и, в частности, тот способ нахождения наибольшего общего делителя, который мы сегодня будем использовать при изучении нового материала. А сейчас повторим суть алгоритма Евклида.
Чтобы найти наибольший общий делитель двух чисел:
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. Вывод формул для решения диофантовых уравнений с использованием алгоритма Евклида
Прежде чем рассмотреть решение линейного уравнения с двумя неизвестными:
ax + by = c (1)
с использованием алгоритма Евклида, докажем утверждение о том, что наибольший общий делитель двух чисел есть последний отличный от нуля остаток в цепочке указанных в примере действий.
Чтобы доказать утверждение о наибольшем общем делителе, представим описанный процесс в виде следующей цепочки равенств: если a > b, то
а = bq0 + r1
b = r1q1 + r2
r1 = r2q2 + r3 (2)
r2. . . . . . . . . . .
. . . . . . . . . . . .
rn – 1 = rn qn
Здесь r1, ... , rn — положительные остатки, убывающие с возрастанием номера. Отсутствие остатка в последнем равенстве следует из того, что натуральные числа rn не могут убывать бесконечно, поэтому на некотором шаге остаток станет нулевым.
Обратимся к системе (2). Из первого равенства, выразив остаток r1 через a и b, получим r1 = a – b·q0. Подставляя его во второе равенство, найдем
r2 = b(1 + q0q1) – a·q1. Продолжая этот процесс дальше, мы сможем выразить все остатки через a и b, в том числе и последний: rn = Aa + Bb. В результате нами доказано, что найдутся такие целые числа A и B, что d = Aa + Bb. Заметим, что коэффициенты A и B имеют разные знаки; если НОД (a; b) = 1, то Aa + Bb = 1. Как найти числа A и B, видно из алгоритма Евклида.
Перейдем теперь к решению линейного уравнения с двумя неизвестными:
ax + by = c. (1)
Возможны два случая: либо число c делится на d = НОД (a; b), либо нет.
В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a1x + b1y = c1, коэффициенты которого
a1 = a/d и b1 = b/d взаимно просты.
Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делится на d и поэтому не может равняться числу c, которое на d не делится.
Итак, мы можем ограничиться случаем, когда в уравнении (1) коэффициенты a и b взаимно просты. На основании предыдущего предложения найдутся такие целые числа х0 и у0, что ax0 + by0 = 1, откуда пара (сх0; су0) удовлетворяет уравнению (1). Вместе с ней уравнению (1) удовлетворяет бесконечное множество пар (x, у) целых чисел, которые можно найти по формулам
x = cx0 + bt, y = cy0 – at. (3)
Здесь t — любое целое число. Нетрудно показать, что других целочисленных решений уравнение ах + by = c не имеет. Решение, записанное
в виде (3), называется общим решением уравнения (1). Подставив вместо t конкретное целое число, получим его частное решение.
Замечание. Название урока — «лекция» — как будто говорит о том, что активная роль здесь принадлежит лишь самому учителю, учащимся предоставляется пассивная роль — внимательно слушать его рассказ, записывать в тетради то, что он пишет на классной доске. Если бы это было именно так, то процесс обучения оказался бы малоэффективным. Современные требования обучения математике предполагают, что даже в том случае, когда учитель является главным действующим лицом, необходима активная деятельность учащихся. Поэтому лекция учителя должна пробуждать у них интерес и потребность к активной умственной деятельности.
По ходу лекции следует обратиться с вопросами к учащимся. Например: Какие уравнения называются диофантовыми? Какой вид имеет линейное диофантово уравнение? Какие условия накладываются на его коэффициенты? Какой способ решения уравнения был использован на предыдущем занятии?
Также на занятиях, где материал изучается крупным блоком, целесообразно создание таблицы в виде конспекта изложенного учителем нового материала. Этот конспект должен стать информационно-справочной таблицей и сыграть свою роль на занятиях тематического или итогового повторения. Сформулируем некоторые требования к его оформлению. Материал в конспекте должен быть разделен на несколько самостоятельных, логически связанных между собой блоков. В него желательно внести вспомогательные вопросы, с помощью которых готовится введение нового, узловые вопросы темы и ее практическое применение.
Таким образом, с одной стороны, в конце урока желательно иметь конспект,
в котором видно главное. А с другой стороны, запись этого конспекта не должна занимать много времени. Для выполнения этих требований можно использовать заготовку для конспекта, т. е. таблицу с пропусками. В нее можно внести рисунок без подписей, частично выполненные условия теоремы, некоторые пункты алгоритмических предписаний и т. п.
Как разработать такой конспект? Учитель сначала разрабатывает конспект полностью на листе бумаге стандартного размера. На другом таком же листе он выписывает конспект-заготовку в строгом расположении текста на основном конспекте. Этот фрагментарный конспект необходимо размножить, чтобы к лекции такой конспект-заготовку имел каждый ученик. Точно такой конспект «с пропусками» учитель должен заранее написать на доске перед началом лекции или подготовить его компьютерный вариант для использования в классе с интерактивной доской. Для проведения данной лекции был подготовлен такой конспект-заготовка (Приложение 4).
3. Примеры решения диофантовых уравнений с использованием алгоритма Евклида
Рассмотрим решение заданий № 6(а), 7 из Приложения 1.
Задание № 6. Решить уравнение на множестве целых чисел
а) 7х + 11у = 69.
НОД (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(б) на множестве целых неотрицательных или натуральных чисел. Найти ее решения.
|
