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