По страницата се работи
Какво трябва да знаем?
Алгоритъм за решаване на уравнението ax+by=1 в цели числа с матрици
УТЕШЕВ Алексей Юрьевич, Станчо Вълканов Павлов
Желаем да решим уравнението 17x+138y=1 в цели числа.
Записваме неизвестните x и y в един ред, а под тях числата 17 и 138:
Делим по-голямото на по-малкото с частно и остатък и след това умножаваме частното по израза над него и го прибаваме към другия израз.
Заменяме по-голямото число (138) с неговия остатък при делението на по-малкото (17) .
Продължаваме по описания начин, докато в числовия ред се получи за първи път 1.
Буквеният израз над тази единица приравняваме на 1 а другия - на нула:
Решавайки тази система, която има целочислено решение получаваме стойностите на x и y (65, -8).
За да получим матрицата на системата разглеждаме таблицата с празно засега съдържание. В горния ред са записани 17 и 138.
В левия стълб са същите числа. Този ред и стълб ще наричаме "главни":
Запълваме матрицата с целочислените частни на числата от реда с числата по главния стълб:
Главния ред и стълб заменяме с остатъците при деление на членовете им с минималното число сред тях:
Продължаваме този процес, докато получим първата единица в главните места:
Определените по този начин матрици се умножават в последователност, обратна на получаването им.
Решаване на уравнението a1x1 + a2x2 + … + anxn = 1
Да нека a1, a2, a3, … , an са взаимно-прости в съвкупност цели числа.
Подобно на предния пример ги разполагаме в главния ред и стълб в еднаква последователност.
Определяме най-малкото от тях в главния стълб а в реда на матрицата записваме частните на елементите от главния ред с този минималн елемент.
Останалите елементи на матрицата запълваме с единици по главнтия диагонал и нули на останалите места.
Новите елементи по главния ред се определят като старите се заменят с остатъците от делението на тях с минималния елемент. Тези, които са равни на него остават непроменени.
След това се разполагат в същата последователност в главния стълб.
Процедурата се повтаря докато в главния ред се появи първата единица.
Получените матрици се умножават в ред обратен на тяхното получаване.
Решава се система с матрица на коефициентите, равна на произведението.
Свободните членове са нули, освен на мястото на получената единица.
Ще решим уравнението 6x+14y+21z=1 по описания способ.
Получаваме последователно матриците до първата единица на главните места.
Минималните елементи са очветени с червено.
Умножаваме матриците в ред обратен на тяхното получаване:
Образуваме система със свободни членове равни на нула, освен на мястото на главната единица.
По този начин получаваме решението на уравнението (-1, -1, 1).
По подобен начин се решава и уравнението 42x+66y+77z=1.
?
Какво ще научим?