і y0, що ax0 + by0 = 1, звідки пара (сx0, cy0) задовольняє рівнянню (2) Разом з нею рівнянням (2) задовольняє нескінченну безліч пар (x, y) цілих чисел, які можна знайти за формулами
x = cx0 + bt, y = cy0-at. (3)
Тут t-будь-яке ціле число. Неважко показати, що інших цілочисельних рішень немає рівняння ax + by = c не має. Рішення, записане у вигляді (3), називається загальним рішенням уравнеія (2). Підставивши замість t конкретне ціле число, отримаємо його приватне рішення. Знайдемо, наприклад, цілочисельні рішення вже зустрічався нам рівняння 2x +5 y = 17. Застосувавши до числам 2 і 5 алгоритм Евкліда, отримаємо 2 * 3-5 = 1. Значить пара cx0 = +3 * 17, cy0 = -1 * 17 задовольняє рівнянню 2x +5 y = 17. Тому спільне рішення вихідного рівняння таке x = 51 +5 t, y =-17-2t, де t приймає будь цілі значення. Очевидно, невід'ємні рішення відповідають тим t, для яких виконуються нерівності
{51 +5 t ≥ 0
{-17-2t ≥ 0
Звідси знайдемо - 51 ≤ t ≤ - 17 . Цим неравенствам задовольняють числа -10, -9. 52
Відповідні приватні рішення запишуться у вигляді пар (1,3), (6,1).
Застосуємо цей же метод до вирішення однієї з стародавніх китайських завдань про птахів.
Задача: Скільки можна купити на 100 монет півнів, курей і курчат, якщо все треба купити 100 птахів, причому півень коштує 5 монет, курка - 4, а 4 курчати - 1 монету?
Для вирішення цього завдання позначимо дані число півнів через х, курей - через y, а курчат через 4z (з умови видно, що число курчат повинно ділиться на 4). Складемо систему рівнянь:
{x + y +4 z = 100
{5x +4 y + z = 100,
яку треба вирішити в цілих невід'ємних числах. Помноживши перше рівняння системи на 4, а друге - на (- 1) і склавши результати, прийдемо до рівняння - х +15 z = 300 з цілочисельними рішеннями х = - 300 + 15t, z = t. Підставляючи ці значення в перший рівняння, отримаємо y = 400 - 19t. Значить, цілочисельні рішення системи мають вид х = -300 +15 t, y = 400-19t, z = t. З умови задачі випливає, що
{- 300 + 15t ≥ 0,
{400-19t ≥ 0,
{t ≥ 0
звідки 20 ≤ t ≤ 21 1/19, тобто t = 20 або t = 21. Отже, на 100 монет можна купити 20 курей і 80 курчат, або 15 півнів, 1 курку і 84 курчати
Другий метод вирішення діофантових рівнянь першого ступеня за своєю суттю не надто відрізняється від розглянутого в попередньому пункті, але він пов'язаний з ще одим цікавим математичним поняттям. Йдеться про безперервних або ланцюгових дробах. Щоб визначити їх знову звернемося до алгоритму Евкліда. З першої рівності системи (1) випливає, що дріб а/b можна записати у вигляді суми цілої частини і правильного дробу: a/b = q0 + r1/b. Але r1/b = 1/b, і на підставі другого рівності тієї ж системи імем b/r1 = q1 + r2/r1. Значить, a/b = q0 +1/q1 + r2/r1. Далі отримаємо a/b = q0 +1/q1 +1/q2 + r3/r2. Продовжимо цей процес до тих пір, поки не прийдемо до знаменника qn. В результаті ми представимо звичайну дріб a/b в наступному вигляді: a/b = q0 +1/q1 +1/q2 +1/... 1/qn. Ейлер назвав дробу такого виду безперервними. Приблизно в той же час в Німеччині з'явився інший термін-ланцюгова дріб. Так за цими дробами і збереглися обидві назви. Як приклад представимо дріб 40/3t у вигляді ланцюгової: 40/3t = 1 +9/3t = 1/3t/9 = 1 +1/3 +4/9 = 1 +1/3 +1/9/4 = 1 +1/3 +1/2 + 1/4.
Ланцюгові дроби володіють наступним важливим властивістю: якщо дійсне число а записати у вигляді безперервної дробу, то підходяща дріб Pk/Qk дає наілучщее наближення числа a серед всіх дробів, знаменники яких не перевищують Qk. Саме в процесі пошуку найкращого приблежения значень квадратних коренів італійський математик Пієтро Антоніо Катальді (1552-1626) прийшов у 1623году до ланцюговим дробям, з чого і почалося їх вивчення. На закінчення повернемося до ланцюговим дробям і відзначимо їх перевага і недолік порівняно, наприклад, з десятковими. Зручність полягає в тому, що їхні властивості не пов'язані ні з якою системою обчислення. З цієї причини ланцюгові дроби ефективно використовуються в теоретичних дослідженнях. Але широкого практичного застосування вони не отримали, оскільки для них немає зручних правил виконання арифметичних дій, які є для десяткових дробів.
Розглянемо Діофантови рівняння і вирішимо їх.
1 Вирішити в цілих числах рівняння 3x +5 y = 7.
Рішення.
Маємо
x = 7-5y/3 = 6-3y-2y +1/3 = 2-y +1-2 y/3,
1-2y = 3k,
y = 1-3k/2 = 1-2k-k/2 =-k +1- k/2,
1-k = 2t, k = 1-2t,
y = 1-3 (1-2t)/2 = -1 +3 t,
x = 7-5 (-1 +3 t)/3 = 4-5t
(t-будь-яке число).
2 Вирішити в цілих числах рівняння 6x ВІ +5 y ВІ = 74.
6x ВІ -24 = 50-5y ВІ, або 6 (x ВІ -4) = 5 (10-y ВІ), звідки x ВІ -4 = 5u, тобто 4 +5 u ≥ 0, звідки u ≥ -4/5. p> Анал...
