Введення в невизначені рівняння
Коли ми обдумуємо рішення тієї або іншої задачі, необхідно звертати увагу на те, які в ній використовуються величини. Цілі або дробові? Позитивні або негативні? Адже незначна деталь допомагає не тільки усунути помилку в рішенні тієї чи іншого завдання, але і знайти саме рішення. Розберемо це на прикладі.
Нехай в Міші (заздалегідь перепрошую, якщо відвідувач сайту Михайло) є п'ятирубльової і , Припустимо, восьмірублевие монети. Всього їх на суму тридцять дев'ять рублів. Скільки монет по п'ять рублів і скільки по вісім у Миші.
Здається, що тут не вистачає даних, якщо, наприклад, через x позначити к-ть 5-рублевих монет, а за y - 8-рублевих монет, то умова самої задачі дозволяє написати одне єдине рівняння:
Ці та інші рівняння та їх системи, в яких число невідомих перевищує число рівнянь, називають невизначеними.
З умови видно, що к-ть монет не може вимірюватися нецілих або негативними числами. Значить, якщо x - ціле невід'ємне число, то і:
повинно бути невід'ємним і цілим. А значить, потрібно, щоб вираз 39 - 5x без залишку ділилося на 8. За допомогою підбору можна переконається, що це можливо при x = 3. Звідси, y = 3.
Перебір варіантів не зручний, коли ми працюємо з великими числами. Набагато краще скористатися методом рассеванія або методом спуску, який придумали давньоіндійські математики. Про метод спуску буде сказано трохи нижче.
Метод спуску (матеріал взято з енциклопедії Аванта + "Математика")
Продовжимо розгляд невизначеного рівняння виду:
де a, b, c - відомі цілі коефіцієнти.
Розберемо це все на знайомому прикладі:
Виберемо невідоме, що має найменший коефіцієнт, і висловимо його через інше невідоме:
Тепер виділимо цілу частину:
Всі число буде цілим, якщо цілим виявиться значення (4 - 3у)/5. Це можливо лише тоді коли число (4 - 3у) без залишку ділиться на 5. Вводячи додаткову цілочисельну змінну z, останню умову запишемо у вигляді
Ми прийшли до рівняння такого ж типу, як і вихідне, але вже з меншими коефіцієнтами. Вирішувати його тепер потрібно відносно змінних y і z.
Продовжуємо діяти всі за тим же принципом:
Для того щоб у виявилось цілим, необхідно, щоб число 1 - 2z без залишку поділялося на 3: 1 - 2z = 3u (знову введена додаткова змінна u, приймаюча тільки цілі значення). Звідси за вже відпрацьованою схемою отримуємо:
Продовжимо ... Число z буде цілою, якщо число 1 - u без залишку ділиться на 2: 1 - u = 2v, де v - довільне ціле. Звідси u = 1 - 2v. Дробів більше немає, спуск закінчено.
Залишилося тепер благополучно В«піднятися вгоруВ». Висловимо через змінну v спочатку z, потім в і, нарешті, х:
Формули х = 3 + 8v, y = 3 - 5v представляють загальне рішення вихідного рівняння в цілих числах. А якщо нас цікавлять тільки невід'ємні цілі числа, то серед всіх цілих рішень потрібно вибрати такі, для яких
і, стало бути,
Спільно ці нерівності можуть виконуватися лише при v = 0. У цьому випадку x = 3, y = 3. Тобто в Міші було 3 5-рублеві монети і 3 8-рублеві монети.
Взагалі, цілі рішення у рівняння виду
можуть бути не завжди. Більш того, якщо на НСД (найбільший спільний дільник) a і b ділиться c, тоді і тільки тоді, рівняння вирішуваний в цілих числах.
