Как да решим линейно уравнение Diophantine

Diophantine уравнение - алгебрични уравнения се наложи допълнително условие, което се състои в това, че всички решения трябва да са с цяло число. Като цяло, уравнението Diophantine е трудно да се реши, а има и много методи за решаването им. Последна теорема на Ферма е известен пример за уравнение Diophantine остане неразрешен за повече от 350 години.

Въпреки това, линейната диофантово уравнение на форма брадва + чрез = С могат да бъдат решени относително лесно с помощта на алгоритъм, описани в тази статия. С помощта на следните методи, ние откриваме, че (4.7) е неразделна положително решение на уравнението 31x + = 180. 8у разделянето на работа в модулната аритметика може също да бъде представен като уравнение Diophantine. Например, 12/7 (блок 18) изисква решение на уравнението 7х = 12 (блок 18), който може да бъде пренаписана като 7х = 12 + 18y или 7х - 18y = 12. Въпреки че някои Diophantine уравнения са твърде сложни, чете тази статия да разбере как да се реши най-простият от тях.

стъпки Редактиране

Запишете уравнението в следната форма: брадва + с = с.

Нанесете на коефициентите А и Б на алгоритъм на Евклид на. Това се прави с две цели. Първо, трябва да се определи дали коефициентите А и В общ делител. Например, ако пред нас 4х уравнение + 10Y = 3, ние веднага забелязват, че лявата му страна винаги е дори и в дясно - странно, а след това има решения под формата на цели числа за това уравнение не съществува. По същия начин, решаване на уравнение 4X + 10Y = 2, може да се опрости да 2х + 5Y = 1. И второ, при наличието на разтвори може да се изгради един от тях от последователността на делителя получава при използване на Euclidean алгоритъм.

Ако една. В и С имат общ делител, да опрости уравнението, като се раздели на лява и дясна своите страни с този номер. Ако А и Б имат общ делител, който е не дели от в. след това ще спре. В този случай, уравнението все още няма целочислени решения.

Начертайте таблица с три реда, както е показано.

Попълнете в горния ред на разделителите на масата, намерен от алгоритъма на Евклид. Цифрата показва как ще изглежда до 87x уравнението - 64y = 3.

Попълнете долните два реда от ляво на дясно, както следва: за всяка клетка намерите продукт на една и съща колона на горната клетка и съседната клетка вляво от това. Регистрирайте клетка в размер на този продукт и стойностите на две клетки, намиращи се в ляво.

Погледнете последните две колони напълнени преди края на масата. Последната колона трябва да съдържа стойности на и б коефициенти (тъй като те са в етап 3). Ако не, проверете вашите изчисления. Предпоследният колоната също ще съдържа две стойности. В нашия пример с = 87 и Ь = 64 съдържа редица 34 и 25.

Имайте предвид, че 87 * 25-64 * 34 = -1. Най-определящ фактор за 2x2 матрица в долния десен ъгъл на таблицата винаги ще бъде равен на 1 или -1. Ако е отрицателен, се размножават двете страни от -1, и имате -87 + 25 * 64 * 34 = 1. Това ще бъде отправна точка, от която се конструира разтвор.

Назад към оригиналното уравнение. Препишете уравнение от предходния етап в 87 * (- 25) + 64 * (34) = 1, или 87 * (- 25) - 64 * (- 34) = 1, така че си вид е по-близо до първоначалното уравнение. Например, в случая, на второ предпочитано изпълнение, тъй като той е подходящ за -64y член, когато оригиналната уравнение у = -34.

Едва сега е време да погледнем в постоянен коефициент век от дясната страна на уравнението. Както вече ни разтвор се намери уравнение брадва + с = 1, се умножава двете страни на това уравнение с С. Ние се получи (СХ) + б (CY) = C. Така, ако (-25, -34) е разтворът на уравнение 87x - 64y = 1, тогава (-75, -102) се разтвор на 87x -64y = 3.

Ако уравнение Diophantine има поне един разтвор, следва, че има безкраен брой решения. Това се дължи на факта, че брадва + с = а (х + б) + б (у -а) = а (х + 2b) + б (у-2а), и като цяло, брадва + с = а (х + KB) + б (у -ka) за всяко цяло число к. По този начин, тъй като (-75, -102) е разтвор на 87x -64y = 3, има и други решения, като например (-11, -15), (53,72), (117,159), и т.н. Общо разтвор могат да бъдат написани като (53 + 64k. 72 + 87k), при к е цяло число.