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

Решением уравнения являются пары целых чисел которые при подстановке в исходное уравнение дают верное тождество.

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

Так, например, уравнение имеет решения, потому что кратно а уравнение решений иметь не будет, так как не кратно

Самый очевидный метод решения таких уравнений — метод перебора.

Например, для уравнения можно получить соотношение, выражая одну переменную через другую: Далее, подставляя можно получить Если рассматривать решение только в натуральных числах, то получишь пары: (9; 1), (7; 2), (5; 3), (3; 4), (1; 5). Такое решение называется частным решением.

Далее рассмотри алгоритм Евклида на примере уравнения

откуда следует, что уравнение имеет решение. Представь единицу через 3 и 10: Таким же образом представь число 4: Тогда коэффициенты и, оглядываясь на коэффициенты в разложении единицы, можно записать решение: Это общее решение, где — целое число.

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

Метод заключается в выражении одной переменной через вторую и последующем выделении целой части и получения общего решения через параметр. Рассмотри данный алгоритм на примере уже другого уравнения: Видно, что уравнение имеет решения, ведь 6 кратно 1. Поэтому нужно выразить переменную, например, и выделить целую часть: Полагая, что есть параметр получится, что Откуда