Ця стаття просунута на Menéame. Якщо вам сподобалось і ви хочете за нього проголосувати, введіть сюди та згадайте про це.
Мотивація
Припустимо, ми стикаємось із такою проблемою:
Чоловік заходить до магазину одягу і купує 12 костюмів, деякі чорні, а інші сірі, за 1200 євро. Якщо чорні костюми коштують на 30 євро більше, ніж сірі, і ви придбали якомога менше останніх, скільки костюмів придбали для кожного кольору?
Піднімемо:
Рівняння має вигляд:
Вираховуючи математику, ми маємо наступне:
Якщо ви думали, що у нас буде проста система рівнянь для розв’язання, ви помиляєтесь. Нам залишається єдине рівняння з двома невідомими. Чи нам не вистачає даних? Ні. Ми можемо це вирішити. Ласкаво просимо в чудовий світ Росії Діофантові рівняння.
Діофантові рівняння
A діофантове рівняння - це алгебраїчне рівняння, в якому з’являється кілька змінних, розв’язками яких є цілі числа. Тобто, рішення діофантового рівняння полягає у визначенні, які цілі числа йому задовольняють. Його ім’я взято від математика Діофант Олександрійський, який, окрім того, що одним із перших застосував символізм в алгебрі, серед іншого присвятив себе вивченню цих рівнянь
Діофантові рівняння вищезазначеного типу називаються діофантовими рівняннями лінійна. Цей конкретний випадок рівнянь - це той, який ми навчимося вирішувати в цій статті. Більш конкретно, ми збираємося показати (і продемонструвати) метод для обчислення цілочисельних розв’язків рівняння
Існування рішень
Перший результат, який ми побачимо та продемонструємо, пов’язаний із існуванням рішень цих рівнянь. Ходімо з ним:
Теорема:
Діофантичне лінійне рівняння форми має цілочисельний розв'язок тоді і лише тоді, коли найбільшим спільним дільником y є дільник .
Крім того, якщо ми це називаємо, ми маємо, що конкретний розв'язок згаданого рівняння можна отримати таким чином:
буття .
1. - Ми починаємо з натяку зліва направо:
має цілочисельне рішення, то існують такі, що
Як є загальним дільником y, то y, с .
Тоді ми маємо таке:
Тобто ми маємо вираз типу з усіма цілими числами. Отже, стільки, скільки вони повинні розділити a, таким чином закінчуючи цю частину доказу.
2. - Тепер ми рухаємось із натяком справа наліво, отримуємо як бонус додаток:
Тепер припустимо, що це дільник. Тоді воно існує таке, що. З іншого боку, за теоремою Безу існують такі, що. Ми множимо двох членів цієї рівності на:
Де ми беремо
З урахуванням того, до чого ми дійшли, і є рішеннями рівняння (1).
є рішенням рівняння (1), що ми і хотіли показати.
На сьогодні ми досягли знання того, як розпізнати, які лінійні діофантові рівняння мають рішення, і обчислити для них конкретне рішення. Але ми хочемо загального рішення, тобто всіх розв’язків лінійних рівнянь діофантину, які можна розв’язати. Ми перейдемо до цього в наступному пункті.
Загальне рішення лінійного діофантичного рівняння
Ми збираємося довести таку теорему:
Теорема:
Якщо це конкретне рішення рівняння
(1)
тоді всі цілочисельні розв'язки його мають вигляд:
(два)
з, буття .
Якщо це рішення рівняння (1), то це правда. Але тоді вирази (2) також є рішенням цього рівняння:
Тоді потрібно було б побачити, що всі розв'язки (1) так, як ми описали в (2). Ходімо:
Виходячи з попереднього конкретного рішення, припустимо, що ми маємо рішення лінійного діофантичного рівняння (1). Тоді ми маємо наступні два рівняння:
Віднімаємо два рівняння, отримуючи
Передаючи друге додавання іншого члена рівності, до якої ми приходимо
Тепер ділимо на:
Оскільки і є відносними простими цілими числами (оскільки, поділивши їх на їх найбільший спільний дільник, ми видалили фактори, спільні у них на початку), і розділимо a, це має бути правдою, що воно ділить .
Це призводить до того, що він повинен існувати таким чином, щоб:
Звідки ми отримуємо, що він повинен мати такий вигляд:
Підставляючи це значення в рівняння (3), ми після кількох простих обчислень отримуємо вираз, який шукаємо:
Практичний приклад
Повернемося до нашого друга в костюмах. Ми дотримуємось наступного лінійного діофантичного рівняння:
Давайте подивимось, чи зможемо ми знайти, скільки костюмів кожного кольору купив цей чоловік.
Оскільки він є дільником нашого рівняння, він має рішення. Для отримання і ми повинні використовувати алгоритм Евкліда для обчислення найбільшого спільного дільника разом із ідентичністю Безута, згаданою вище. У цьому випадку ви отримуєте
Тоді конкретне рішення таке:
З цього легко знайти всі рішення:
В принципі ці вирази дають нам усі шляхи вирішення проблеми, але ми ще не закінчили. Є більше речей, які слід враховувати. Аналізуючи отримані дані, ми знаємо, що кількість чорних костюмів, які ви придбали, є, отже, кількість придбаних сірих костюмів .
Беручи до уваги, що кількість костюмів кожного типу, придбаних нашим другом, має бути позитивною і менше 12, отримується наступне:
Тому єдиними можливими значеннями для є .
Але в заяві також зазначається, що він придбав мінімальну кількість сірих костюмів. Тестування з попередніми значеннями, для яких ця умова виконується. Отже, головний герой нашої проблеми придбав сірі та чорні костюми.
Демо-джерело:
- Алгебра та дискретна математика I, Кармен Морено Валенсія.