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

Главная » Статьи » Математика » Уравнения

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

α • x+b • y= c,

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

Ниже рассматриваются несколько классических задач на эти уравнения: нахождение любого

решения, получение всех решений, нахождение количества решений и сами решения в

определённом отрезке,

нахождение решения с наименьшей суммой неизвестных.

Вырожденный случай

Один вырожденный случай мы сразу исключим из рассмотрения: когда α = b = 0 .

В этом случае,

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

имеет решений

вовсе (в зависимости от того, c = 0 или нет).

Нахождение одного решения

Найти одно из решений диофантова уравнения с двумя неизвестными можно с помощью

Расширенного

алгоритма Евклида. Предположим сначала, что числа α и b неотрицательны.

Расширенный алгоритм Евклида по заданным неотрицательным числам α и b

находит их наибольший

общий делитель g, а также такие коэффициенты xg и yg , что:

α•xg+b•yg = g

Утверждается, что если c cделится на g = gcd(α,b) , то диофантово уравнение

α • x +b • y = c

имеет решение; в противном случае диофантово уравнение решений не имеет.

Доказательство следует из очевидного факта, что линейная комбинация двух чисел

по-прежнему должна делиться на их общий делитель.

Предположим, что c делится на g , тогда, очевидно, выполняется:

α•xg•(c/g)+b• yg•(c/g) = c,

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

Мы описали решение в случае, когда числа α и b неотрицательны.

Если же одно из них или они оба отрицательны, то можно поступить таким образом:

взять их по модулю и применить к ним алгоритм

Евклида, как было описано выше, а затем изменить знак найденных x0 и y0

в соответствии с

настоящим знаком чисел α и b соответственно.

Реализация (напомним, здесь мы считаем, что входные данные α = b = 0

недопустимы):

int gcd (int a, int b, int & x, int & y) {
 if (a == 0) {
 x = 0; y = 1;
 return b;
 }
 int x1, y1;
 int d = gcd (b%a, a, x1, y1);
 x = y1 - (b / a) * x1;
 y = x1;
 return d;
}
 
bool find_any_solution (int a, int b, int c, int & x0, int & y0, int & g)

{g = gcd (abs(a), abs(b), x0, y0);
 if (c % g != 0)
 return false;
 x0 *= c / g;
 y0 *= c / g;
 if (a < 0) x0 *= -1;
 if (b < 0) y0 *= -1;
 return true;
}

Получение всех решений

Покажем, как получить все остальные решения (α и х бесконечное множество)

диофантова

уравнения, зная одно из решений (x0,y0) .

Итак, пусть g = gcd(α,b) , а числа x0,y0 удовлетворяют условию:

α•x0+b•y0 = c

Тогда заметим, что, прибавив к x0 число b/g и одновременно отняв α/g от y0 ,

мы не нарушим равенства:

α•(x0+b/g)+b•(y0-α/g)=α•x0+b•y0+α•b/g-b•α/g=c

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

вида:

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

Более того, только числа такого вида и являются решениями, т.е. мы описали

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

если не наложено дополнительных условий).

Нахождение количества решений и сами решения в заданном отрезке

Пусть даны два отрезка[minx;maxx]и[miny;maxy] , и требуется найти количество

решений (x,y) диофантова уравнения, лежащих в данных отрезках соответственно.

Заметим, что если одно из чисел α,b равно нулю, то задача имеет не больше одного

решения, поэтому

эти случаи мы в данном разделе исключаем из рассмотрения.

Сначала найдём решение с минимальным подходящим x, т.еxminx.x≥ minx .

Для этого сначала найдём любое решение диофантова уравнения (см. пункт 1).

Затем получим из него решение с наименьшим .x≥ minx — для этого воспользуемся

процедурой, описанной в предыдущем пункте, и будем уменьшать/увеличивать x,

пока оно не окажется ≥ minx, и при этом минимальным. Это можно сделать за O(1),

посчитав, с каким коэффициентом нужно применить это преобразование, чтобы получить

минимальное число, большее либо равное minx. Обозначим найденный xчерез lx1 .

Аналогичным образом можно найти и решение с максимальным подходящим x = rx1,= ,

т.е. x ≤ maxx.

Далее перейдём к удовлетворению ограничений на y, т.е. к рассмотрению отрезка

[ miny;maxy;] .

Способом, описанным выше, найдём решение с минимальным y≥miny , а также

решение с максимальным y≤maxy. Обозначим x-коэффициенты этих решений

через lx2; и rx2 соответственно.

Пересечём отрезки [lx1;и rx1] ; обозначим получившийся отрезок через [lx;rx] .

Утверждается, что любое решение, у которого x-коэффициент лежит в [lx;rx] — любое

такое решение является подходящим. (Это верно в силу построения этого отрезка:

сначала мы отдельно удовлетворили ограничения на x и y, получив два отрезка,

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

Таким образом, количество решений будет равняться длине этого отрезка, делённой

на |b|(поскольку x-коэффициент может изменяться только на ±b ), и плюс один.

Приведём реализацию (она получилась достаточно сложной, поскольку требуется

аккуратно рассматривать случаи положительных и отрицательных коэффициентов

α и b):

void shift_solution (int & x, int & y, int a, int b, int cnt) {
 x += cnt * b;
 y -= cnt * a;
}
 
int find_all_solutions (int a, int b, int c, int minx, int maxx, int miny, int maxy)

{int x, y, g;
 if (! find_any_solution (a, b, c, x, y, g))
 return 0;
 a /= g; b /= g;
 
 int sign_a = a>0 ? +1 : -1;
 int sign_b = b>0 ? +1 : -1;
 
 shift_solution (x, y, a, b, (minx - x) / b);
 if (x < minx)
 shift_solution (x, y, a, b, sign_b);
 if (x > maxx)
 return 0;
 int lx1 = x;
 
 shift_solution (x, y, a, b, (maxx - x) / b);
 if (x > maxx)
 shift_solution (x, y, a, b, -sign_b);
 int rx1 = x;
 
 shift_solution (x, y, a, b, - (miny - y) / a);
 if (y < miny)
 shift_solution (x, y, a, b, -sign_a);
 if (y > maxy)
 return 0;
 int lx2 = x;
 
 shift_solution (x, y, a, b, - (maxy - y) / a);
 if (y > maxy)
 shift_solution (x, y, a, b, sign_a);
 int rx2 = x;
 
 if (lx2 > rx2)
 swap (lx2, rx2);
 int lx = max (lx1, lx2);
 int rx = min (rx1, rx2);
 
 return (rx - lx) / abs(b) + 1;
}