Решение диофантовых уравнений алгоритмом евклида онлайн (8 видео)

Содержание

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

Видео:Математика. Линейные диофантовы уравнения с двумя неизвестными. Центр онлайн-обучения «Фоксфорд»Скачать

Линейные диофантовы уравнения онлайн

Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида:

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

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

Для решения линейного диофантового уравнения с двумя неизвестными сначала необходимо найти частное решение и , а затем записать общее решение, используя формулы:

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

Поскольку делится нацело на , то данное уравнение имеет решения в целых числах.

Далее, найдём какое-нибудь конкретное (частное) решение и исходного уравнения. Для этого, сначала необходимо найти частное решение и вспомогательного уравнения с коэффициентом :

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

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

Преобразуем данную дробь в цепную дробь:

В полученной цепной дроби отбросим последнюю дробь :

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

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

Теперь, чтобы найти частное решение и исходного уравнения, умножим найденное частное решение и вспомогательного уравнения на :

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

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

Видео:Полезные мелочи | алгоритм Евклида | диофантовы уравнения | примеры | 1Скачать

Линейные диофантовы уравнения с двумя переменными

Калькулятор решает линейные диофантовы уравнения с двумя переменными.

Сначала калькулятор, теория под ним.

Линейные диофантовы уравнения с двумя переменными

Диофантово уравнение с двумя неизвестными имеет вид:

где a, b, c — заданные целые числа, x и y — неизвестные целые числа.

Для нахождения решений уравнения используется Расширенный алгоритм Евклида (исключая вырожденный случай, когда a = b = 0 и уравнение имеет либо бесконечно много решений, либо же не имеет решений вовсе).
Если числа a и b неотрицательны, тогда с помощью расширенного алгоритма Евклида мы можем найти их наибольший общий делитель g, а также такие коэффициенты и , что:
.

Утверждается, что если число c делится на g, то диофантово уравнение имеет решение; в противном случае диофантово уравнение решений не имеет. Это следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.

То есть если c делится на g, тогда выполняется соотношение:

т. е. одним из решений диофантова уравнения являются числа:

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

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

Итак, пусть g = НОД (a,b), выполняется условие:
.

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

Этот процесс можно повторять сколько угодно, т. е. все числа вида:

,
где k принадлежит множеству целых чисел, являются множеством всех решений диофантова уравнения.

Видео:Как решать Диофантовы уравнения ★ 9x+13y=-1 ★ Решите уравнение в целых числахСкачать

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


Коэффициенты первого диофантового уравнения

Коэффициенты второго диофантового уравнения

Система двух диофантовых уравнений

Матрица общего решения

Результат в виде строки

Проверка для первого уравнения

Проверка для второго уравнения

Рассматривается оригинальный алгоритм решения двух произвольных однородных линейных уравнений в целых числах. Автоматический расчет матрицы решений.

Пусть Нам надо решить систему из двух диофантовых уравнений

Несомненно можно решать эту систему так как делают все.

— Умножив первое уравнение на 31 и вычтя из второго мы получим классическое диофантовое уравнение с двумя переменными.

— Решив которое можно найти все целочисленные значения системы

Схема рабочая, несмотря на множество ручных вычислений

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

Он красив и понятен даже для школьников, знающих про вектора и матрицы.

Частично использован алгоритм, описанный вот в этой статье ( стр 36,37)

Он доработан, приведен к матричным операциям и обобщен на любые значения.

Алгоритм и его работу мы будем изучать на примере.

Решаем следующую систему диофантовых уравнений

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

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

Как видим ответ совпадает со свободным членом первого уравнения.

2. Теперь, раз мы нашли общее решение первого уравнения, давайте его подставим во второе.

То есть в уравнение (70a-31b+9c=9)подставим наши значения

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

То есть мы получили уравнение

Но, обратите внимание, что во втором уравнении свободный член равен не нулю, а девяти.

То есть мы переписываем

Переносим свободные члены в правую часть и получаем классическое диофантовое уравнение, которое можем решать легко.

Общее решение такое

3. А теперь делаем обратное преобразование.

вот в эту систему (begina=8m+14p+20\b=-19m-30p-44\c=-m+p+0end)

мы вместо неизвестных подставляем найденные m и p.

В матричном исчислении это решается так:

последний столбец. Это свободные члены и они нам пока мешаются.

Умножаем эту матрицу на матрицу созданную из этих уравнений

Последняя колонка это свободные члены, прибавим к ней ту колонку которую убирали в начале этого пункта

то есть к вектору <-22 36 -11> прибавляем

А следовательно общее решение системы двух диофантовых уравнений

Проверим, правильно ли посчитали

Для первого уравнения

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

Но радоваться рано, несмотря на то, что мы получили общее решение, мы получаем не все возможные значения.

Почему? Да потому что вектор имеет НОД =19

и фактически наше общее решение имеет вид

Так как числа в скобках должны быть целыми, то обозначим их t и наше, уже точно окончательное общее решение системы двух диофантовых уравнений имеет вид

Еще несколько примеров, и небольшие ремарки к алгоритму.

Теперь что калькулятор не может.

Очень сильно не любит уравнения с нулевыми коэффициентами. Особенно первое. Например, вот такую систему

калькулятор не решит.

Прибавим к первому уравнению, второе. Таким образом в первом уравнении исчезают все нулевые коэффициенты и калькулятор сможет решить эту систему. Ну как не решит? Решит, если прибегнем к уловке, и постараемся убрать все нулевые коэффициенты

Проверка показывает что общее решение корректно.