Як вирішити лінійне диофантово рівняння
Диофантово рівняння - це рівняння алгебри з накладаються додатковою умовою, що складається в тому, що всі його рішення повинні представляти із себе цілі числа. У загальному випадку діофантови рівняння дуже складно вирішити, і для їх вирішення існує безліч методів. Велика теорема Ферма є знаменитим прикладом диофантова рівняння, що залишається невирішеним ось уже понад 350 років.
Проте, лінійні діофантови рівняння, що мають вигляд ax + by = c можуть бути вирішені відносно легко за допомогою алгоритму, описаного в даній статті. Користуючись наведеними методом, ми можемо знайти, що (4,7) є цілочисельним позитивним рішенням рівняння 31x + 8y = 180. Операцію поділу в модульної арифметики також можна представити у вигляді диофантова рівняння. Наприклад, 12/7 (модуль 18) вимагає рішення рівняння 7x = 12 (модуль 18), що можна переписати як 7x = 12 + 18y або 7x - 18y = 12. Хоча деякі діофантови рівняння занадто складні, прочитайте цю статтю, щоб дізнатися, як вирішувати найпростіші з них.
кроки Правити
Запишіть рівняння в наступному вигляді: ax + by = c.
Застосуйте до коефіцієнтів a і b алгоритм Евкліда. Це робиться з двома цілями. По-перше, ми повинні визначити, чи є у коефіцієнтів a і b спільний дільник. Наприклад, якщо перед нами рівняння 4x + 10y = 3, ми відразу ж помічаємо, що його ліва частина завжди парна, а права - непарна, тобто рішення у вигляді цілих чисел для даного рівняння не існує. Схожим чином, вирішуючи рівняння 4x + 10y = 2, ми можемо спростити його до 2x + 5y = 1. І по-друге, якщо ці заходи є рішень ми можемо сконструювати одне з них з послідовності подільників, отриманої за допомогою алгоритму Евкліда.
Якщо a. b і c мають спільний дільник, спростите рівняння, поділивши його ліву і праву частини на це число. Якщо a і b мають спільний дільник, на який не ділиться без залишку c. тоді зупиніться. У цьому випадку рівняння не має цілих рішень.
Накресліть таблицю з трьох рядків, як показано на малюнку.
Заповніть верхню сходинку таблиці делителями, знайденими за алгоритмом Евкліда. На малюнку показано, як це буде виглядати для рівняння 87x - 64y = 3.
Заповніть дві нижніх рядки зліва направо наступним способом: для кожного осередку знайдіть твір верхньої осередки цього ж стовпчика і сусідній осередку, розташованої зліва від даної. Впишіть в клітинку суму цього твору і значень двох осередків, розташованих зліва.
Подивіться на останні дві колонки заповненої до кінця таблиці. Остання колонка повинна містити значення коефіцієнтів a і b (якими вони були на кроці 3). Якщо це не так, перевірте свої обчислення. Передостання колонка також буде містити два значення. У нашому прикладі з a = 87 і b = 64 вона містить числа 34 і 25.
Зауважимо, що 87 * 25 - 64 * 34 = -1. Детермінант матриці 2x2 в правому нижньому кутку таблиці завжди буде дорівнює 1 або -1. Якщо він негативний, помножте обидві частини рівності на -1, і у вас вийде -87 * 25 + 64 * 34 = 1. Це буде стартовою точкою, з якої ми побудуємо рішення.
Поверніться до початкового рівняння. Перепишіть рівність з попереднього кроку як 87 * (- 25) + 64 * (34) = 1 або 87 * (- 25) - 64 * (- 34) = 1, щоб його вид був ближче до первісного рівняння. Наприклад, в нашому випадку краще другий варіант, оскільки він підходить до члена -64y початкового рівняння при y = -34.
Лише тепер прийшла пора поглянути на постійний коефіцієнт c в правій частині рівняння. Оскільки раніше нами було знайдено рішення рівняння ax + by = 1, помноживши обидві частини цього рівняння на c. отримаємо a (cx) + b (cy) = c. Таким чином, якщо (-25, -34) є рішенням рівняння 87x - 64y = 1, то (-75, -102) буде рішенням рівняння 87x -64y = 3.
Якщо диофантово рівняння має хоча б одне рішення, це означає, що воно має нескінченне число рішень. Це є наслідком того, що ax + by = a (x + b) + b (y -a) = a (x + 2b) + b (y-2a), і в загальному випадку ax + by = a (x + kb) + b (y -ka) для будь-якого цілого k. Таким чином, оскільки (-75, -102) є рішенням рівняння 87x -64y = 3, існують і інші рішення, такі як (-11, -15), (53,72), (117,159) і т.д. Загальне рішення можна записати у вигляді (53 + 64k. 72 + 87k), де k є будь-яким цілим числом.