Диофантови уравнения от първа степен с две неизвестни

Както е известно, уравнението ax + by = c, където а, b и с са рационални коефициенти, це нарича линейно уравнение (уравнение от I степен) с две неизвестни. В множеството на рационалните числа то винаги има безброй решения (например при b ≠ 0 всяка наредена двойка $\left(x;y=\frac{c-ax}{b}\right)$ при x - рационално число е неговото решение). Когато е поставено изискването да се намерят само целочислените му решения, т.е. тези, чиито компоненти са цели числа, уравнението се нарича диофантово уравнение от I степен с две неизвестни.

Без да се нарушава общността на разглеждане на въпроса, условието за рационалност на коефициентите a, b, И с може да се замени с условието те да бъдат цели числа. Наистина, ако а, b и с са произволни рационални числа, то като умножим двете страни на разглежданото уравнение с общо кратно (например най-малкото) на знаменателите а, b и с, съгласно известна теорема, ще получим уравнение, еквивалентно на разглежданото, което ще бъде с коефициенти цели числа. Затова в нашето разглеждане на върпоса по-нататък ще считаме, че а, b и с са цели числа.

Теорема 1:
Необходимото и достатъчно условие диофантово уравнение ax + by = c да има поне едно решение е най-големият общ делител на a и b да дели с.
1. Необходимост: Нека наределената двойка (x₀, y₀) е решение на диофантовото уравнение ax + by = c. Това означава, че ax₀ + by₀ = c е вярно числово равенство. Да означим с d най-големия общ делител на a и b. Ще докажем че d дели c. Наистина, щом d е делител на a и b, то съществуват цели числа a и b такива, че a = da₁ и b = db₁. DДа заместим a и b с техните равни в числовото равенство ax₀ + by₀ = c. Ще получим da₁x₀ + db₁y₀ = c или d(a₁x₀ + b₁y₀) = c. Лявата страна на полученото равенство се дели на d, от което следва, че и дясната трябва да се дели на d, т.е. d дели c.
2. Достатъчност: Ще докажем, че е вярно и обратното твърдение, т.е. d дели c, то диофантовото уравнение ax + by = c има поне едно решение. За целта ще използваме наготово едно твърдение от теорията на числата, известно под името тъждество на Безу, което гласи:
Ако d дели най-големият общ делител на числата а и b, то съществуват цели числа u и v такива, че d = ua + vb.
Нека d дели c. Това означава, че съществува цяло число c₁ такова, че c = dc₁. Да умножим двете страни на тъждеството на Безу с c₁. Ще получим c₁ua + cvb = c₁d, което е вярно числово равенство. Като вземем пред вид, че c₁d = c и че c₁u и c₁v са цели числа и положим c₁u = x₀ и c₁v = y₀, ще получим числовото равенство ax₀ + by₀ = c, което означава, че (x₀;y₀) е решение на диофантовото уравнение ax + by = c.

Следствие:
Всяко диофантово уравнение от вида ax + by = c, където а и b са взяимно прости числа, има поне едно решение.
Наистина ако най-големия общ делите на a и b е d = 1, то d дели c.

Доказаната теорема ни дава достатъчното условие едно диофантово уравнение да има поне едно решение. То се представя с изискването най-големият общ делител на коефициентите пред променливите да дели свободния член. Тогава всяко диофантово уравнение, което има поне едно решение, можем да заменим с еквивалентното му уравнение от вида ax + by = c, където a и b са взаимно прости числа. Наистина за това е достатъчно да разделим двете страни на въпросното уравнение с най-големия общ делител на коефициентите пред променливите.
Доказаната теорема ни дава отговор на въпроса за броя на решенията на едно дифантово уравнение от I степен с две неизвестни. Този отговор се дава от следната теорема:

Теорема 2:
Ако диофантовот уравнение ax + by = c, където a и b са взаимно прости числа, има решение (x₀; y₀), то ax + by = c, има безброй решения, които се дават чрез формулите:
            x = x₀ + bt,
            y = y₀ - at,             (1)
където t е цяло число.
Доказателство: Най-напред ще докажем, че всяка двойка (x₁;y₁), където x₁ = x₀ + bt и y₁ = y₀ - at, е решение на уравнението ax + by = c, т.е. ax₁ + by₁ = c е вярно числово равенство. За целта заместваме x₁ и y₁ с техните равни в уравнението и получаваме:
ax₁ + by₁ = a(x₀ + bt) + b(y₀ - at) = ax₀ + abt + by₀ - abt = ax₀ + by₀. По условие (x₀;y₀) е решение на уравнението, т.е. ax₀ + by₀ = c. Тогава ax₁ + by₁ = c e вярно числово равенство, т.е. (x₁;y₁) е също решение на уравнението.
Ще трябва да докажем още, че всички решения на уравнението се дават от формулите (1), т.е., ако (x';y') е решение на уравнението, то x' и y' могат да се представят чрез формулите от вида (1).
Наистина ако (x';y') e решение на уравнението, то ax' + by' = c e вярно числово равенство. По условие (x₀;y₀) е също решение, т.е. ax₀ + by₀ = c е също вярно числово равенство. След почленно изваждане на двете числови равенства получаваме а(x' - x₀) = -b(y' - y₀), т.е. $x'-x_0=\frac{-b(y'-y_0)}{a}=\frac{b(y_0-y')}{a}$. Тъй като x'-x₀ e цяло, то $\frac{b(y_0-y')}{a}$ e също цяло. От друга страна b и а са взаимно прости. Следователно а дели y₀-y', т.е. y₀ - y' = at' или y' = y₀ - at', където t' e цяло. Като заместим y₀-y' с равното му в равенството $x'-x_0=\frac{b(y_0-y')}{a}$, получаваме $x'-x_0=\frac{bat'}{a}$ или x' = x₀ + bt'.

Доказаната теорема ни дава начин за намиране на всичкитре решения на разглежданото диофантово уравнение при условие, че знаем едно конкретно негово решение. Остава открит само въпросът как да намерим едно начално решение. В много случаи (когато числата a и b не са големи) то просто се налучква. Например, за уравнението 3x - 2y = 4 лесно се открива, че наредената двойка (2;1) е неговото решение. Тогава всичките му решения се дават чрез формулите x = 2 - 2t и y = 1 - 3t, където t e цяло число.

За случаите когато сме затруднени да "открием" начално решение, съществуват различни методи за неговото намиране. Ще посочим един от тях, известен под името метод на Ойлер.

Пример: Да се реши в цели числа уравнението 17x + 22y = 15.
Посоченото уравнение има целочислени решения, защото 17 и 22 са взаимно прости числа.
Изразяваме неизвестното, чийто коефициент има по-малка абсолютна стойност чрез другото. В случая |17| < |22| и $x=\frac{15-2y}{17}$. В полученият израз за x тделяме цялата му част, т.е.
$x=\frac{15-22y}{17}=-y+\frac{15-5y}{17}$.
За да бъде х цяло число, е достатъчно $\frac{15-5y}{17}$ да бъде цяло число, т.е. 17 да дели 15-5ъ. Това означава, че трябва да съществува цяло число t такова, че 15 - 5у = 17t. Получаваме ново линейно диофантово уравнение с неизвестни y и t. С него постъпваме по същия начин.
      $\frac{15-17t}{17}=3-3t-\frac{2t}{5}$
За да бъде у цяло число е достатъчно при t цяло число 2t/5 да бъде цяло, т.е. 2t да се дели на 5. Тогава трябва да съществува цяло число t, такова, че 2t = 5t₁. С полученото диофантово уравнение постъпваме пак по същия начин, т.е. $t=\frac{5t_1}{2}=2t_1+\frac{t_1}{2}.$ За да бъде t цяло число е достатъчно t₂/2 да бъде цяло, т.е. t₁=2t₂, където t₂ e цяло. Намерената стойнопст за t₁ използаме, за да определим последователно t, y, и x чрез t₂. Получаваме $t=2(2t_2)+\frac{2t_2}{2}=5t_2;y=3-3(5t_2)-\frac{2.5t_2}{5}=3-17t_2;x=-(3-17t_2)+\frac{15-5(3-17t_2)}{17}=-3+22t_2.$ Тогава всички целочислени решения се дават чрез формулите x = -3 + 22t₂ и y = 3 - 17t₂ при t₂ цяло.
Като вземем пред вид, че съгласно Теорема 2, за да запишем формулите, даващи всичките решения на разглежданото уравнение, е достатъчно да знаем само едно негово решение, става чсно, че описаният алгоритъм може да се съкрати. Така например още в израза $x=-y+\frac{15-5y}{17}$ се "вижда", че х е цяло число за всяко цяло у, при което 15-5у се дели на 17. Например, ако 15 - 5у = 0, т.е. у = 3, то х = -3. Тогава съгласно Теорема 2 всичките решения на разгледаното уравнение се дават чрез формулите x = -3 + 22t; y = 3 - 17t при t цяло число.
Накрая трябва да отбележим, че при решаване на задачи, водещи до съставяне и решаване на линейни диофантови уравнения с две неизвестни, трябва да имаме в предвид характера на въведените неизвестни, който определя множеството на допустимите им стойности. В такива случаи решението на задачата обикновено се дава от едно крайно модмножество на множеството на решенията на диофантово уравнение.

Задачи

1. Проверете кои от следните доифантови уравнения имат решение и ги решете:
a) 3x + 5y = 19;
b) 6x + 10y = 38;
c) 34x + 17y = 15;
d) 37x + 91 y = 8;
e) 14x + 19y = 17;
f) 13x + 7y = 0;
g) 37x - 25y = 53;
h) 12x + 31y - 127 = 0.

2. За покупка на сувенир български турист е трябвало да заплати 21 рубли. В себе су той имал банкноти по 5 рубли, а касиерката разполагала с банкноти по 3 рубли. Как трябва да стане разплащането при наличните банкноти?

3. Сумата 87лв. е изплатена с банкноти от 5лв. и 2лв. Колко са банкнотите от единия и другия вид?

4. дин ученик казал на приятеля си: "Умножи 12 по рождения си ден, 31 по рождения си месец и ако съобщиш сбора на получените числа, аз ще позная рождения ти ден и месец." След пресмятане приятелят му казал, че сборът е 374. Как ученикът е намерил рождената дата на приятеля си и коя е тя?

5. Могат ли да се отмерят 32 грама от някакъв продукт на везни при наличието на 5 теглилки по 3г и 6 теглилки по 5г?

6. 110кг ябълки трябвало да се разпределят в щайги, които събират по 8кг и 10кг ябълки. По колко щайги от единия и другия вид са необходими?

7. По колко курса трябва да направят две леки коли, от които едната е четириместна, а другата - петместна, за да превозят от едно място на друго 37 пътника?

8. Ученик трябвало да реши 73 задачи за 19 дни. През първите 11 дни той решавал по х задачи, а през останалите - по у задачи. По колко задачи дневно е решавал ученикът?