Cпосіб знаходження «часткового» розв’язку лінійног діофантового рівняння

Cпосіб знаходження «часткового»  розв’язку  лінійног діофантового рівняння

Для розв’язування лінійного діофантового рівняння з двома невідомими

ах + bу = с

треба помножити все рівняння на спільний знаменник,  а  потім:

1) перевірити умову розв’язності даного рівняння в цілих числах. Для цього  спочатку ділять обидві частини рівняння на число m = НСД(а, b,с) , а потім перевіряють умову:

НСД(a/m;  b/m ) = НСД(p;s) = 1, де  a/m = p; b/m = s;

якщо ця умова не виконується, тоді роблять висновок дане рівняння не має розв’язку в цілих числах.

2) якщо рівняння має розв’язок в цілих числах, тоді треба відшукати хоча б одну пару (х_о, у_о) цілих чисел, яка є розв’язком даного рівняння

ах + bу = с;

(це можна зробити:  методом підбору,  методом Евкліда, графічним способом та іншими способами.)

3) записати всю множину розв’язків лінійного діофантового рівняння з двома невідомими, як множину цілочисельних пар у вигляді

(х_о - ak,  у_о+ bk),  де k – довільне ціле число.

Cпосіб розкладу  одиниці  на суму цілочисельних добутків.

При такому способі  розв’язання лінійного діофантового рівняння  ах + bу = с  треба:

1) перевірити  умову  розв’язності  даного  рівняння;

2)  якщо розв’язки існують, тоді  знайти за допомогою алгоритму Евкліда цілочисельний розв’язок  (n; m) для    рівняння:

ах + bу = 1;

3) рівність  ах + bу = 1 помножити на  ціле число  с і отримати:   а(nc) + b(mc) = c,

записати цілочисельну пару   х_о = nc,    у_о  = mc,  що є  розв’язком ах + bу = с.

4) записати всю множину розв’язків лінійного діофантового рівняння з двома невідомими,  як множину цілочисельних пар у вигляді

х = nc - ak,

у  = mc + bk;

або

(х_о - ak,  у_о+ bk),

де k – довільне ціле число.

Приклад 4:

Розв’язати рівняння в цілих числах

3x + 5y = 7

Розв’язання:

1) Перевіримо умову розв’язності: коефіцієнти рівняння

а =3, b =5, с =7,

НСД(3, 5) = 1,

отже  маємо ціле число, якщо 7: НСД(3, 5), тому дане рівняння має множину розв’язків в цілих числах.

2) Знайдемо спочатку який-небудь розв’язок. Тут використаємо  таку ідею, до речі, часто допомагає і при розв’язанні інших завдань.

Спочатку знайдемо одну пару цілих чисел (m; n), яка є  рівняння розв’язком іншого, легшого рівняння:

3x + 5y = 1,

тоді матимемо правильну  рівність:

3m + 5n = 1,

 а для того, щоб знайти один розв’язок (х_о, у_о)  для рівняння

3x + 5y = 7,

треба буде помножити  правильну рівність 

3m + 5n = 1 на 7.

Продемонструємо цю ідею на практиці.  Оскільки легко встановити, що

3m + 5n = 3∙2 + 5∙(-1) = 1, то  3x + 5y = 3∙(2∙7) + 5∙(-7∙1) = 1∙7

і, отже,

x₀ = 14,

y₀ = 7 –

це розв’язок даного рівняння (одне з багатьох, не більш!).

3) Отже, маємо дві рівності:

3x + 5y = 7, 

3x₀ + 5y₀ = 7,

Віднімемо одне рівняння з іншого, позначимо

x- x₀ і у -y₀

через p і g, і отримаємо

3a + 5b = 0.

Звідси ми бачимо, що b ділиться на 3, а  а – на 5. Покладемо p = 5k,  тоді  g = 3k – тут очевидно,  що  k - може бути будь-яким цілим числом. Отже, ми отримуємо набір розв’язків:

х - x₀ = 5k; 

у - y₀ = -3k,

звідси маємо, 

x = 14 + 5k;

y = -7 - 3k,

де  k - може бути будь-яким цілим числом. Інших розв’язків, звичайно, немає.

Відповідь: (14 +5k;  -7 -3k), де k – довільне ціле число.