Зміст

• кроки
• Частина 1 з 4: Як записати рівняння
• Частина 2 з 4: Як записати алгоритм Евкліда
• Частина 3 з 4: Як знайти рішення за допомогою алгоритму Евкліда
• Частина 4 з 4: Як знайти безліч інших рішень

Щоб вирішити лінійне диофантово рівняння, потрібно знайти значення змінних «x» і «y», які є цілими числами. Целочисленное рішення складніше звичайного і вимагає певного набору дій. Спочатку необхідно обчислити найбільший спільний дільник (НСД) коефіцієнтів, а потім знайти рішення. Якщо ви знайшли одне цілочисельне рішення лінійного рівняння, можна застосувати простий шаблон, щоб знайти безліч інших рішень.

кроки

Частина 1 з 4: Як записати рівняння

1. 1 Запишіть рівняння в стандартній формі. Лінійне рівняння - це рівняння, в якому показники ступеня змінних не перевищують 1. Щоб вирішити таке лінійне рівняння, спочатку запишіть його в стандартній формі. Стандартна форма лінійного рівняння виглядає так: ${ Displaystyle Ax + By = C}$, де ${ Displaystyle A, B}$ і ${ Displaystyle C}$ - цілі числа.
   • Якщо рівняння дано в іншій формі, приведіть його до стандартної форми за допомогою основних алгебраїчних дій. Наприклад, дано рівняння ${ Displaystyle 23x + 4y-7x = -3y + 15}$. Наведіть подібні члени і запишіть рівняння так: ${ Displaystyle 16x + 7y = 15}$.
2. 2 Спростіть рівняння (якщо можна). Коли ви запишете рівняння в стандартній формі, подивіться на коефіцієнти ${ Displaystyle A, B}$ і ${ Displaystyle C}$. Якщо у цих коефіцієнтів є НОД, розділіть на нього все три коефіцієнта. Рішення такого спрощеного рівняння також буде рішенням вихідного рівняння.
   • Наприклад, якщо всі три коефіцієнта парні, розділіть їх як мінімум на 2. Наприклад:
     • ${ Displaystyle 42x + 36y = 48}$ (Всі члени діляться на 2)
     • ${ Displaystyle 21x + 18y = 24}$ (Тепер всі члени діляться на 3)
     • ${ Displaystyle 7x + 6y = 8}$ (Це рівняння більше не можна спростити)
3. 3 Перевірте, чи можна вирішити рівняння. У деяких випадках можна відразу заявити, що рівняння не має рішень. Якщо коефіцієнт «С» не ділиться на НСД коефіцієнтів «А» і «В», у рівняння немає рішень.
   • Наприклад, якщо обидва коефіцієнта ${ Displaystyle A}$ і ${ Displaystyle B}$ парні, то і коефіцієнт ${ Displaystyle C}$ повинен бути парним. Але якщо ${ Displaystyle C}$ непарний, то рішення немає.
     • У рівняння ${ Displaystyle 2x + 4y = 21}$ немає цілочисельних рішень.
     • У рівняння ${ Displaystyle 5x + 10y = 17}$ немає цілочисельних рішень, так як ліва частина рівняння ділиться на 5, а права - немає.

Частина 2 з 4: Як записати алгоритм Евкліда

1. 1 Усвідомте алгоритм Евкліда. Це ряд повторних поділів, в якому попередній залишок використовується як наступний дільник. Останній дільник, який ділить числа без остачі, є найбільшим спільним дільником (НСД) двох чисел.
   • Наприклад, знайдемо НОД чисел 272 і 36 за допомогою алгоритму Евкліда:
     • ${ Displaystyle 272 = 7 * 36 + 20}$ - розділіть більше число (272) на меншу (36) і зверніть увагу на залишок (20);
     • ${ Displaystyle 36 = 1 * 20 + 16}$ - розділіть попередній дільник (36) на попередній залишок (20). Зверніть увагу на новий залишок (16);
     • ${ Displaystyle 20 = 1 * 16 + 4}$ - розділіть попередній дільник (20) на попередній залишок (16). Зверніть увагу на новий залишок (4);
     • ${ Displaystyle 16 = 4 * 4 + 0}$ - розділіть попередній дільник (16) на попередній залишок (4). Так як залишок дорівнює 0, можна сказати, що 4 є НОДом вихідних двох чисел 272 і 36.
2. 2 Застосуйте алгоритм Евкліда до коефіцієнтів «A» і «B». Коли ви запишете лінійне рівняння в стандартній формі, визначте коефіцієнти «A» і «B», а потім застосуйте до них алгоритм Евкліда, щоб знайти НСД. Наприклад, дано лінійне рівняння ${ Displaystyle 87x-64y = 3}$.
   • Ось алгоритм Евкліда для коефіцієнтів А = 87 і В = 64:
     • ${ Displaystyle 87 = 1 * 64 + 23}$
     • ${ Displaystyle 64 = 2 * 23 + 18}$
     • ${ Displaystyle 23 = 1 * 18 + 5}$
     • ${ Displaystyle 18 = 3 * 5 + 3}$
     • ${ Displaystyle 5 = 1 * 3 + 2}$
     • ${ Displaystyle 3 = 1 * 2 + 1}$
     • ${ Displaystyle 2 = 2 * 1 + 0}$
3. 3 Знайдіть найбільший спільний дільник (НСД). Оскільки останнім делителем було число 1, НСД 87 і 64 дорівнює 1. Таким чином, 87 і 64 є простими числами по відношенню один до одного.
4. 4 Проаналізуйте отриманий результат. Коли ви знайдете НСД коефіцієнтів ${ Displaystyle A}$ і ${ Displaystyle B}$, Порівняйте його з коефіцієнтом ${ Displaystyle C}$ вихідного рівняння. якщо ${ Displaystyle C}$ ділиться на НСД ${ Displaystyle A}$ і ${ Displaystyle B}$, Рівняння має целочисленное рішення; в іншому випадку у рівняння немає рішень.
   • Наприклад, рівняння ${ Displaystyle 87x-64y = 3}$ можна вирішити, тому що 3 ділиться на 1 (НОД = 1).
   • Наприклад, припустимо, що НОД = 5. 3 не ділиться на 5 без остачі, тому таке рівняння не має цілочисельних рішень.
   • Як показано нижче, якщо рівняння має одне цілочисельне рішення, воно також має безліч інших цілочисельних рішень.

Частина 3 з 4: Як знайти рішення за допомогою алгоритму Евкліда

1. 1 Пронумеруйте кроки обчислення НОД. Щоб знайти рішення лінійного рівняння, потрібно використовувати алгоритм Евкліда в якості основи процесу підстановки і спрощення.
   • Почніть з нумерації кроків обчислення НСД. Процес обчислення виглядає так:
     • ${ Displaystyle { text {Крок 1}}: 87 = (1 * 64) +23}$
     • ${ Displaystyle { text {Крок 2}}: 64 = (2 * 23) +18}$
     • ${ Displaystyle { text {Крок 3}}: 23 = (1 * 18) +5}$
     • ${ Displaystyle { text {Крок 4}}: 18 = (3 * 5) +3}$
     • ${ Displaystyle { text {Крок 5}}: 5 = (1 * 3) +2}$
     • ${ Displaystyle { text {Крок 6}}: 3 = (1 * 2) +1}$
     • ${ Displaystyle { text {Крок 7}}: 2 = (2 * 1) +0}$
2. 2 Зверніть увагу на останній крок, де є залишок. Перепишіть рівняння цього кроку так, щоб ізолювати залишок.
   • У нашому прикладі останній крок із залишком - це крок 6. Залишок дорівнює 1. Перепишіть рівняння кроку 6 наступним чином:
     • ${ Displaystyle 1 = 3 (1 * 2)}$
3. 3 Ізолюйте залишок попереднього кроку. Цей процес являє собою покрокове «переміщення вгору». Кожен раз ви будете ізолювати залишок в рівнянні попереднього кроку.
   • Ізолюйте залишок рівняння кроку 5:
     • ${ Displaystyle 2 = 5 (1 * 3)}$ або ${ Displaystyle 2 = 5-3}$
4. 4 Зробіть заміну і спростите. Зверніть увагу, що рівняння кроку 6 містить число 2, а в рівнянні кроку 5 число 2 ізольовано. Тому замість «2» в рівнянні кроку 6 підставте вираз кроку 5:
   • ${ Displaystyle 1 = 3-2}$ (Рівняння кроку 6)
   • ${ Displaystyle 1 = 3 (5-3)}$ (Замість 2 підставили вираз)
   • ${ Displaystyle 1 = 3-5 + 3}$ (Розкрили дужки)
   • ${ Displaystyle 1 = 2 (3) -5}$ (Спростили)
5. 5 Повторіть процес підстановки і спрощення. Повторіть описаний процес, переміщаючись по алгоритму Евкліда в зворотному порядку. Кожен раз ви будете переписувати рівняння попереднього кроку і підставляти його останнім отримане рівняння.
   • Останнім розглянутим кроком був крок 5. Тому перейдіть до кроку 4 і ізолюйте залишок в рівнянні цього кроку:
     • ${ Displaystyle 3 = 18- (3 * 5)}$
   • Підставте цей вираз замість «3» в останнє рівняння:
     • ${ Displaystyle 1 = 2 (18-3 * 5) -5}$
     • ${ Displaystyle 1 = 2 (18) -6 (5) -5}$
     • ${ Displaystyle 1 = 2 (18) -7 (5)}$
6. 6 Продовжіть процес підстановки і спрощення. Цей процес буде повторюватися до тих пір, поки ви не досягнете початкового кроку алгоритму Евкліда. Мета процесу - записати рівняння з коефіцієнтами 87 і 64 вихідного рівняння, яке потрібно вирішити. У нашому прикладі:
   • ${ Displaystyle 1 = 2 (18) -7 (5)}$
   • ${ Displaystyle 1 = 2 (18) -7 (23-18)}$ (Підставили вираз з кроку 3)
     • ${ Displaystyle 1 = 2 (18) -7 (23) +7 (18)}$
     • ${ Displaystyle 1 = 9 (18) -7 (23)}$
   • ${ Displaystyle 1 = 9 (64-2 * 23) -7 (23)}$ (Підставили вираз з кроку 2)
     • ${ Displaystyle 1 = 9 (64) -18 (23) -7 (23)}$
     • ${ Displaystyle 1 = 9 (64) -25 (23)}$
   • ${ Displaystyle 1 = 9 (64) -25 (87-64)}$ (Підставили вираз з кроку 1)
     • ${ Displaystyle 1 = 9 (64) -25 (87) +25 (64)}$
     • ${ Displaystyle 1 = 34 (64) -25 (87)}$
7. 7 Перепишіть отримане рівняння відповідно до вихідних коефіцієнтами. Коли ви повернетеся до першого кроку алгоритму Евкліда, ви побачите, що отримане рівняння містить два коефіцієнта вихідного рівняння. Перепишіть рівняння так, щоб порядок його членів відповідав коефіцієнтам вихідного рівняння.
   • У нашому прикладі вихідне рівняння ${ Displaystyle 87x-64y = 3}$. Тому перепишіть отримане рівняння так, щоб коефіцієнти привести у відповідність.Зверніть особливу увагу на коефіцієнт «64». У вихідному рівнянні цей коефіцієнт негативний, а в алгоритмі Евкліда - позитивний. Тому множник 34 потрібно зробити негативним. Остаточне рівняння запишеться так:
     • ${ Displaystyle 87 (-25) -64 (-34) = 1}$
8. 8 Застосуйте відповідний множник, щоб знайти рішення. Зверніть увагу, що в нашому прикладі НОД = 1, тому остаточне рівняння дорівнює 1. Але вихідне рівняння (87x-64y) дорівнює 3. Тому всі члени остаточного рівняння потрібно помножити на 3, щоб отримати рішення:
   • ${ Displaystyle 87 (-25 * 3) -64 (-34 * 3) = 1 * 3}$
   • ${ Displaystyle 87 (-75) -64 (-102) = 3}$
9. 9 Запишіть целочисленное рішення рівняння. Числа, які множаться на коефіцієнти вихідного рівняння, є рішеннями цього рівняння.
   • У нашому прикладі запишіть рішення у вигляді пари координат: ${ Displaystyle (x, y) = (- 75, -102)}$.

Частина 4 з 4: Як знайти безліч інших рішень

1. 1 Усвідомте, що існує безліч рішень. Якщо лінійне рівняння має одне цілочисельне рішення, то воно повинно мати нескінченно безліч цілочисельних рішень. Ось короткий доказ (в алгебраїчній формі):
   • ${ Displaystyle Ax + By = C}$
   • ${ Displaystyle A (x + B) + B (y-A) = C}$ (Якщо додати «B» до «x» і відняти «A» з «y», значення вихідного рівняння не зміниться)
2. 2 Запишіть вихідні значення «x» і «y». Шаблон для обчислення наступних (нескінченних) рішень починається з єдиного рішення, яке ви вже знайшли.
   • У нашому прикладі рішення являє собою пару координат ${ Displaystyle (x, y) = (- 75, -102)}$.
3. 3 Додайте коефіцієнт «B» до значення «x». Зробіть це, щоб знайти нове значення «x».
   • У нашому прикладі x = -75, а В = -64:
     • ${ Displaystyle x = -75 + (- 64) = - 139}$
   • Таким чином, нове значення «х»: x = -139.
4. 4 Відніміть коефіцієнт «A» з значення «y». Щоб значення вихідного рівняння не змінилося, при додаванні одного числа до «x» потрібно відняти інше число з «y».
   • У нашому прикладі y = -102, а А = 87:
     • ${ Displaystyle y = -102-87 = -189}$
   • Таким чином, нове значення «у»: у = -189.
   • Нова пара координат запишеться так: ${ Displaystyle (x, y) = (- 139, -189)}$.
5. 5 Перевірте рішення. Щоб переконатися, що нова пара координат є рішенням вихідного рівняння, підставте значення в рівняння.
   • ${ Displaystyle 87x-64y = 3}$
   • ${ Displaystyle 87 (-139) -64 (-189) = 3}$
   • ${ Displaystyle 3 = 3}$
   • Оскільки рівність дотримано, рішення вірне.
6. 6 Запишіть вирази для знаходження безлічі рішень. Значення «x» дорівнюватимуть вихідного рішенням плюс будь-який кратне коефіцієнта «В». Це можна записати у вигляді наступного виразу:
   • x (k) = x + k (B), де «x (k)» - безліч значень «х», а «x» - вихідне (перше) значення «x», яке ви знайшли.
     • У нашому прикладі:
     • ${ Displaystyle x (k) = - 75-64k}$
   • y (k) = y-k (A), де «у (k)» - безліч значень «у», а «у» - вихідне (перше) значення «у», яке ви знайшли.
     • У нашому прикладі:
     • ${ Displaystyle y (k) = - 102-87k}$