/H3>
Розглянемо тепер лінійне рівняння з двома невідомими
,.
Покажемо кілька алгоритмів для знаходження рішення.
Спосіб 1.
Нехай
Розглянемо два випадки:
а). не ділиться на. У цьому випадку рішень немає по теоремі 2.
б). ділиться на, поділимо на.
;
.
Таким чином отримали нове ЛДУ, з тим же безліччю рішень, але вже зі взаємно-простими коефіцієнтами. Тому далі ми будемо розглядати саме такі рівняння. p> Розглянемо,.
, перейдемо до порівняння,
.
Т.к. , То порівняння має єдине рішення.
; підставимо в рівняння.
;
;
, причому.
Позначимо.
Тоді загальне рішення можна знайти за формулами:, де.
Приклад. ,.
Знайдемо рішення порівняння;
;
, тобто p>.
;
В
Отримали спільне рішення:, де.
Спосіб 2.
Розглянемо ще один спосіб знаходження рішення ЛДУ з двома невідомими, а для цього розглянемо рівняння виду. Рівняння такого виду називаються лінійними однорідними діофантових рівняннями (ЛОДР). Висловлюючи невідому, через невідому приходимо до. Так як x повинен бути цілим числом, то, де - довільне ціле число. Значить. Рішеннями ЛОДР є n-ки виду, де. Безліч всіх таких n-ок називається загальним рішенням ЛОДР, будь-яка ж конкретна пара з цієї множини називається приватним рішенням. p> Розглянемо тепер рівняння,. Нехай n-но його приватне рішення, а безліч n-ок спільне рішення відповідного ЛОДР. Доведемо пропозиція.
Загальне рішення ЛДУВ , Задається рівняннями, де. p> Доказ. Те, що праві частини зазначених у формулюванні теореми рівностей дійсно є рішеннями, перевіряється їх безпосередньої підстановкою у вихідне рівняння. Покажемо, що будь-яке рішення рівняння має саме такий вигляд, який вказаний в формулюванні пропозиції. Нехай - якесь рішення рівняння. Тоді, але ж і. Віднімемо з першого рівності другу і отримаємо:
- однорідне рівняння. Пишемо відразу спільне рішення:, звідки отримуємо:
. Доказ завершено. p> Постає питання про знаходженні приватного рішення ЛДУ. <В
По теоремі про лінійному розкладанні НСД, це означає, що знайдуться такі і з безлічі цілих чисел, що, причому ці і ми легко вміємо знаходити за допомогою алгоритму Евкліда. Помножимо тепер рівність на і отримаємо:, тобто ,. p> Таким чином, для знаходження спільного рішення знаходимо спільне рішення ЛОДР, приватне рішення ЛДУ і їх складовими.
Зауваження: особливо цей спосіб зручний, коли або. Якщо, наприклад,,, тоді n-ка, очевидно, буде приватним рішенням ЛДУ. Можна відразу виписувати спільне рішення. br/>
Приклад. ,. p> Знайдемо приватне рішення. Використовуємо алгоритм Евкліда. p>;
В
Отримуємо лінійне розкладання НСД:
, т.е.
,
Отримали спільне рішення:, де. p> Як бачимо, отримали рішення, що не співпадає з рішенням, знайденим першим способ...
