Lineaariseen Diofantokseen ratkaisumenetelmä

Olkoon lukujen a(1),a(2),...,a(n)suurin yhteinen tekijä (syt) = (a(1),a(2),...,a(n)) = d.

(a(1), ...a(r),a(r 1),...,a(n)) = ((a(1),a(2),...,a(r)), a(r 1),...,a(n))

Olkoon meillä yhtälö

(1) a(1) x(1) a(2) x(2) ... a(n) x(n) = b

Tällä on ratkaisu sjvs kun (a(1),...,a(n)) l b (tuo syt d jakaa luvun b).

Tuo syt löytyy toistamalla Euklideen algoritmia:

Ensin lasketaan (a(1),a(2)), sitten ((a(1),a(2)),a(3)) jne lopulta löytyy tuo (a(1),...,a(n)).

Menetelmä johtaa siihen, että löytyy luvut u(1),...,u(n) joille pätee

(2) a(1) u(1) a(2) u(2) ... a(n) u(n) = d.

Nyt d l b eli b = d c

Kun yhtälö (2) kerrotaan puolittain luvulla c saadaan yhtälön (1) ratkaisu:

x(i) = u(i) c, 1 <= i <= n

Näin saadaan yksi ratkaisu. Jos x(i) ja y(i) (1 <= i <= n) ovat ratkaisuja niin

(3) a(1) (x(1) - y(1)) ... a(n) (x(n) - y(n)) = 0

eli kahden ratkaisun erotus on tuon homogeenisen yhtälön ratkaisu. Jos siis tunnetaan yhtälön (3) kaikki ratkaisut ja yhtälön (1) erikoisratkaisu niin tunnetaan yhtälön (1) kaikki ratkaisut.

Mutta enpä mene nyt setvimään asiaa tämän pitemmälle.Jätän lukijoille mietittäväksi miten kaikki ratkaisut saadaan.

Esimerkkilaskussa Euklideen algoritmin avulla saadaan

43 -42 x 23 579348 x 435 - 190344 x 1324 = 1

Tässä d = 1 ja b = 1 joten c = 1 ja tuo lauseke antaa ratkaisun suoraan :

x = 1, y = - 42, z = 579348 ja w = - 190344.

Tämä on siis yksi esimerkkiyhtälön ratkaisu.


Ohman

Tiedän vain että lineaarisen Diofantoksen yhtälön voi ratkaista matriisien avulla