KNOWED.RU

Пусть a,b,c - произвольные целые числа, причем a,b отличны от нуля. Рассмотрим уравнение:
ax+by=c
Поставим задачу нахождения всех целочисленных решений этого уравнения. В этом случае оно называется Диофантовым.
Пусть d=(a,b). Ясно, что если уравнение имеет решения, то d делит c.
Пусть a=a1d, b=b1d, c=c1d. Понятно, что уравнения a1x+b1y=c1 и ax+b=c равносильны.
Значит без ограничения общности можно считать, что в уравнении ax+by+c коэффициенты a и b взаимно просты.

Опишем множество решений Диофантова уравнения:

ТЕОРЕМА: Пусть (xo,yo) - некоторое решение Диофантова уравнения ax+by=c , причем коэффициенты a и b взаимно просты.
Если (x,y) - произвольное решение этого уравнения, то x=xo+bt, y=yo-at для некоторого целого t.

ДОКАЗАТЕЛЬСТВО:
Подставляя выражение xo+bt и yo-at вместо x и y в уравнение получим:
a(xo+bt)+b(yo-at)=axo+abt+byo-bat=axo+byo=c
Таким образом, числа xo+bt, yo-at образуют решение уравнения при любом целом t.
Пусть x,y - произвольные решения диофантова уравнения ax+by=c. Кроме того, axo+bxo=c.
Тогда ax+by=axo+byo, тоесть ax-axo+bx-bxo=0 => a(x-xo)+b(y-yo)=0.
Поскольку a и b взаимно просты, то видно, что b делит x-xo т.е x-xo=bt. теперь имеем:
abt+b(y-yo)=c, откуда y-yo=-at. Тем самым проверено, что любое решение диофантова уравнения имеет вид предложенный в теореме.

Решим в качестве примера диофантово уравнение:
13x+41y=8
Выражая x через y получим:
x=(8-41y)/13=-3y+(8-2y)/13
Поскольку x и -3y - целые числа, то 13 должно делить 8-2y.
Значит, 8-2y=13z для некоторого целого z, тогда
y=(8-13z)/2=4-7z+z/2
Теперь получили, что 2 должно делить z, т.е
z=2t. Теперь
y=y=4-7(2t)+t=4-13t.
Из равенства x=(8-41y)/13=-3y+(8-2y)/13 окончательно получаем:
x=-3(4-13t)+2t=-12+41t.
Опубликовано на сайте: http://www.knowed.ru
Прямая ссылка: http://www.knowed.ru/index.php?name=pages&op=view&id=98
1111