Решить уравнение с помощью алгоритма евклида

Элективный курс Сказки Шехерезады и уравнения Диофанта Балашов 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)

Линейное диофантово уравнение и 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.

5 = 3

3 = 2 .

Из этого равенства выразим 1. 1 = 3 — 2 = 3 – (5 — 3 ) =

= 3 — 5 = 3 = (8 — 5 — 5 82 -5

= 5(-2). Итак, m = -3, n = -2.

2. Частное решение уравнения (1): Х_о = 19m; у_о =19n.

Отсюда получим: Х_о =19; у_о =19 .

Пара (-57; -38)- частное решение (1).

3. Общее решение уравнения (1): n Z.

Четвертый способ. Геометрический.

1. Решим уравнение 5х – 8у = 1 геометрически.

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

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

Отложим на окружности последовательно друг за другом равные дуги, составляющие

-ю часть полной окружности. За 8 шагов получим все вершины правильного вписанного в окружность 8-угольника. При этом сделаем 5 полных оборотов.

На 5 – ом шаге получили вершину, соседнюю с начальной, при этом сделали 3 полных оборота и еще прошли — ю часть окружности, так что х = у + .

Итак, Х_о = 5, у_о =3 является частным решением уравнения 5х – 8у = 1.

2. Частное решение уравнения (1): Х_о = 19 у_о =19

3. Общее решение уравнения (1): n Z.

Диофантовы уравнения — методы, алгоритмы и примеры решения

Основные понятия

Решением линейных уравнений начали заниматься ещё в Древнем Вавилоне и Греции. Особого успеха в их вычислении смог добиться древнегреческий философ и математик правителя Греции — Диофант Александрийский. В третьем веке до нашей эры он издал свой труд под названием «Арифметика», в котором описал возможные решения различных математических задач. Большая часть их была посвящена уравнениям, которые и были позже названы в его честь.

Диофантовыми уравнениями принято называть линейные выражения вида: a1x1 + a2x2 + … + anxn = c. В этих равенствах икс обозначает искомое неизвестное, а коэффициенты a и c являются целыми числами. Греческий учёный предложил несколько способов решения таких уравнений:

• полный перебор;
• разложение на множители;
• выражение одной переменной через другую с выделением целой части при решении системы;
• поиск частного решения;
• алгоритм Евклида;
• геометрический метод.

Методы решения диофантовых уравнений позволяют найти целые или рациональные решения для алгебраических равенств или их систем. Но при этом число переменных в выражении не должно превышать двух. Как правило, такие уравнения имеют несколько решений, поэтому их другое популярное название — неопределённые.

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

Чтобы понимать возможности применения уравнений в тех или иных исследовательских вычислениях, необходимо предварительно ответить на два вопроса: могут ли быть у задания целочисленные решения и ограничено ли число действительных ответов. Поэтому использование способов подходит только для простейших уравнений первой и второй степени. Для выражений высших порядков, например, 4x 3 + 6Y 3 — 2z 4 = 23, определить, является ли решением целое число, довольно проблематично.

Методы решения

Для начала следует рассмотреть однородное линейное уравнение вида: ax + by = 0. Это простой многочлен первой степени. Для него характерно то, что если для коэффициентов можно подобрать один делитель, то обе части возможно сократить на его величину не нарушив принципы записи. Наиболее простым способом определить этот делитель является метод разработанный великим математиком своего времени Евклидом.

Решение диофантовых уравнений по алгоритму Евклида заключается в нахождении общего делителя натуральных чисел с использованием деления с остатком. Для этого нужно взять большее число и просто разделить его на наименьшее. Затем полученный остаток нужно снова разделить на меньшее из чисел. Это действие необходимо повторять до тех пор, пока результатом операции не станет единица, то есть выполнится деление без остатка. Последнее полученное число и будет являться наибольшим общим делителем (НОД).

Существует три теоремы, которые используются при решении уравнений первой степени:

1. В случае, когда НОД равняется единице, выражение будет обязательно иметь хотя бы одну пару целого решения.
2. Если коэффициенты выражения больше единицы, и при этом свободный член нельзя нацело разделить на них, то корни равенства не имеют целого значения.
3. Когда коэффициенты равняются единице, все решения, состоящие из целых чисел, находятся с помощью формул: x = x0c + bt и y = y0c — at, где: х0, y0 — целые ответы, t — множество чисел.

Например, пусть есть равенство вида 54x + 37y = 1. Используя то, что a = 54, а b =37, можно записать: 54 — 37 *1 = 17. Теперь можно выполнить следующие вычисления:

• 37 — 17 * 2 = 3;
• 71 — 3 * 5 = 2;
• 3 — 2 * 1 = 1.

Далее нужно выразить значения коэффициентов через остаток:

• 3 — (17 — 3 * 5) = 1;
• 1 = 17 — 3 * 4;
• 1 = 17 — (37- 17 * 2) * 4;
• 1 = 17 — 37 * 4+17 * 8;
• 1 = 17 * 9 — 37 * 4;
• 1 = (54 — 37 * 1) * 9 — 37 * 4;
• 1 = 54 * 9 — 37 * 9 — 37 * 4;
• 1 = 54 * 9 — 37 * 13;
• 1 = 54х + 37у.

Исходя из приведённого следует, что x0 равняется девяти, а игрек нулевой — минус тринадцать. Таким образом, рассматриваемое уравнение будет иметь вид:

Этим же способом можно и определить, что целых решений в выражении быть не может, как, например, для равенства 17x + 36y = 7. В этом случае НОД не делится на два, поэтому и целых решений нет.

Способ подбора и разложения

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

Пусть имеется зоопарк, в котором находятся птицы и млекопитающие. Всего у животных двадцать лап. Определить, какое количество может быть птиц, а какое — млекопитающих. Для нахождения ответа методом перебора следует принять число одних животных, равное x (пусть это будут четырёхпалые), а других — y (птицы). Таким образом, получится уравнение: 2x + 4 y = 20. Для простоты выражение можно упростить, сократив на два: x + 2y = 10.

Полученное выражение нужно преобразовать, разделив неизвестные знаком равно: x = 10 — 2y. Зная, что ответом могут быть только целые числа, вместо y нужно пробовать подставлять возможные варианты: 1 — 8; 2 — 6; 3 — 4; 4 — 2; 5 — 0. Это и есть все возможные ответы на поставленную задачу.

Разложение выражения на множители можно выполнять различными способами. Вот основные из них:

• вынесение общего множителя: если каждый член многочлена можно разделить на одно и то же число, то его можно вынести за скобку;
• использование формулы сокращённого умножения: оно выполняется по формуле: an — bn = (a-b) * (an-1 + an-2 * b +… a2bn-3 + abn-2 + bn-1);
• применение свойства полного квадрата: это самый эффективный способ, заключающийся в вынесении полного квадрата за скобку с последующим использованием формул разности квадратов;
• группировкой — в его основе лежит вынесение общего множителя таким образом, чтобы появилась возможность перегруппировки выражения, после которой получится значение, присутствующее во всех членах равенства.

Например, пусть имеется нелинейное уравнение вида: 8×4 + 32×2 = 8. Все его члены можно перенести в одну сторону, а равенство приравнять к нулю, при этом сократив каждый член на восемь: x4 + 4×2 — 1 = 0. Для преобразования такого выражения удобнее всего применить метод квадратов. Таким образом, уравнение можно расписать следующим образом: x4 + 2 * 2 * x2 + 4 — 4 — 1 = (x2 + 2)2 — 5 = (x2 + 2 — √5) * (x2 + 2 +√5).

Геометрический подход

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

Из этого утверждения можно сделать следующие выводы:

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

Применять этот метод можно для уравнений, порядок которых не превышает единицы. В равенствах высшего порядка построить график обычно сложно. Например, дана система:

Из первого и второго равенства можно выразить одно неизвестное через другое, используя несколько произвольных чисел. Затем, подставляя их вместо неизвестного, можно построить график. Как только две прямые будут построены, можно будет определить, что точка их пересечения имеет координаты -2; 5. Эти значения и будут искомыми корнями.

Занимательная задача

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

Вот одна из них, появившаяся из реальной истории. Однажды математик пришёл в магазин приобрести свитер. Его цена составляла 19 рублей. У учёного же были с собой только купюры номиналом три рубля, а у кассира — пятирублёвки. Задача состоит в том, чтобы выяснить, сможет ли состояться сделка. Иными словами, необходимо найти, сколько нужно математику дать купюр, и какое их количество он получит от кассира.

Рассуждать нужно следующим образом. В задачи есть два неизвестных: количество трёхрублёвых и пятирублёвых купюр. Поэтому можно составить уравнение: 3x — 5y = 19. По сути, уравнение с двумя неизвестными может иметь бесчисленное число решений, но не всегда из них может найтись хотя бы одно целое положительное.

Итак, зная, что неизвестные должны быть целыми положительными числами, нужно выразить неизвестное с меньшим коэффициентом через остальные члены. Получится равенство: 3 x = 19 + 5 y. Левую и правую часть можно разделить на три, а после выполнить простейшие преобразования: x = (19 + 5y) / 3 = 6 + y + (1 + 2y) / 3. Учитывая, что неизвестные и свободный член это целые числа, выражение (1 + 2y) / 3 можно заменить буквой r, также являющимся каким-то целым числом.

Тогда уравнение можно переписать как x = 6 + y + t. Отсюда t = (1 + 2y) / 3 или y = t + (t — 1) / 2. Снова можно сделать вывод, что (t — 1) / 2 — какое-то целое число. Если заменить его на t1, выражение примет вид: y = t + t1.

Подставив t = 2t1 + l в равенство можно получить, что x = 8 + 5t1, а y = 1 + 3t1. Таким образом, решением уравнения будут полученные равенства. Исходя из того, что результат должен быть положительным, равенства можно переписать в неравенства вида:8 + 5t1> 0, 1 + 3t1 > 0. Отсюда определить диапазон, ограничивающий t1. Беря во внимание только плюсовую часть диапазона, можно сделать заключение, что возможные варианты решения лежать в пределе от нуля до плюс бесконечности.

Подставляя по очереди числа, можно определить значения x и y. Искомый ряд будет выглядеть следующим образом: 1 = 8, 13, 18, 23, …, n; <у = 1 + 3t>1 = 1, 4, 7, 10,…, m. То есть математик, дав восемь купюр, получит одну на сдачу, а если он отдаст 13 купюр, то продавец должен будет ему выдать четыре пятирублёвки. Этот ряд можно продолжать до бесконечности.

Использование онлайн-калькулятора

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

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

Из нескольких десятков таких сайтов на русском языке можно отметить следующие:

Все приведённые сайты имеют интуитивно понятный интерфейс и бесплатны. После того как пользователь введёт в предложенную форму нужные уравнения и запустит расчётчик, онлайн-сервисы не только выдадут ответ, но и выведут на экран пошаговое решение с объяснениями. Таким образом, эти сервисы помогают не только быстро и верно найти решение, но и дают возможность пользователю понять принципы вычисления, проверить самостоятельно выполненный расчёт.