Уравнения с двумя неизвестными

 Рассмотрим линейное диофантово уравнение с двумя неизвестными
ax+by=c,a,b,cZ
Рассмотрим несколько алгоритмов нахождения его решений. Алгоритм №1. Пусть (a,b)=d1. Рассмотрим два случая:

  • c не делится на d. В этом случае решений нет по теорема о решении ЛДУ.
  • c делится на d, поделим обе части уравнения на d: adx+by=cd; (ad,bd)=1. В результате получаем новое линейное диофантово уранение с тем же множеством решений, но уже со взаимно простыми коэффициентами. Рассмотрим ax+by=c,(a,b)=1. Или же axc=by. Перейдем к сравнению axc(modb). Т.к. (a,b)=1, то сравнение имеет единственное решение x=x0(modb),x=x0+bt,tZ. Подставим его в уравнение:
    a(x0+bt)+by=c,
    by=ca(x0+bt),
    y=cax0bat,причемcax0b inZ.
    Обозначим y0=cax0b, тогда общее решение можно найти по формулам:
    {x=x0+bt,y=y0at,
    где tZ.
Пример. Решить уранение 3x+5y=2. Найдем решение сравнения 3x2(mod5):
3x12(mod5),
x4(mod5),т.е.x0=5.
x=4+5t,tZ.
y=23(4+5t)5=21215t5=23t.
Получили общее решение:
{x=4+5t,y=23t,
где tZ. Алгоритм № 2. Рассмотрим уравнение вида ax+by=0. Уравнения такого вида называются линейными однородными диофантовыми уравнениями. Выражая неизвестную x, через неизвестную y приходим к x=bay. Так как x должен быть целым числом, то y=at , где t – произвольное целое число. Значит x=bt. Решениями ax+by=0 являются пары чисел вида (bt,at), где tZ. Множество всех таких пар называется общим решением линейного однородного диофантового уравнения, любая же конкретная пара из этого множества называется частным решением. Рассмотрим теперь уравнение ax+by=c,(a,b)=1. Пусть пара чисел (x0,y0) его частное решение, а множество пар вида (bt,at) общее решение соответствующего линейного однородного диофантового уравнения. Общее решение линейного диофантового уравнения ax+by=c,(a,b)=1, задается уравнениями
{x=x0+bt,y=y0at,
где tZ. Встает вопрос о нахождении частного решения линейного диофантового уравнения. Так как (a,b)=1, то по теореме о линейном разложении НОД, это означает, что найдутся такие u и v из множества целых чисел, что au+bv=1, причем u и v легко найти с помощью алгоритма Евклида. Умножим теперь равенство au+bv=1 на c и получим:
a(uc)+b(vc)=c,т.е.x=uc,y=vc.
Таким образом, для нахождения общего решения находим общее решение линейного однородного диофантового уравнения, частное решение линейного диофантового уравнения и их складываем. Замечание: особенно этот способ удобен, когда ac или bc. Если, например, ac, c=aq, тогда пара чисел (q,0), очевидно, будет частным решением линейного диофантового уравнения. Можно сразу выписывать общее решение. Пример. Решить уранение 3x+5y=2. Найдем частное решение, используя алгоритм Евклида:
5=13+2,
3=12+1,
2=21.
Получаем линейное разложение НОД: 1=1312=131(1513)=2315, т.е u=2,v=1.
x0=uc=22=4,
x0=vc=12=2.
Получили общее решение:
{x=4+5t,y=23t,
где tZ. Алгоритм № 3. Разложим отношение коэффициентов при неизвестных в цепную дробь:
ab=q1+1q2+1q3++1qn
Возьмем предпоследнюю подходящую дробь Pn1Qn1. Пара чисел (x0,y0), где x0=(1)ncQn1,y0=(1)ncPn1 является частным решением уравнения axby+c=0,(a,b)=1. Действительно, так как a=Pn,b=Qn, то
ax0+by0=Pn(1)ncQn1Qn(1)ncPn1=(1)nc(PnQn1QnPn1)=(1)nc(1)n=c
Все решения данного уравнения имеют вид:
{x=(1)ncQn1+bt,y=(1)ncpn1at,
где tZ. Пример. Решить уранение 3x+5y=2. Разложим в цепную дробь число 35:
35=011+23=011+11+12.
Получим следующие подходящие дроби:
P1Q1=0,P2Q2=1,P3Q3=12,P4Q4=35.
Предпоследняя подходящая дробь будет Pn1Qn1=P3Q3=12. Решением уравнения 3x+5y=2 будет:
{x=(1)422+5t=4+5t,y=(1)42(1)3t=23t,
где tZ.