Lineære diofantiske likninger

Dette innlegget har allerede blitt vist 2287 ganger!

En lineær diofantisk likning er på formen ax + by = c, hvor a,b,c er heltall mens vi ønsker å finne heltall x og y slik at likningen har løsning.  Denne likningen har kun en løsning dersom gcd(a,b) c. Det som er interresant er at når man løser gcd(a,b) med Euklids algoritme er man halvveis til å finne løsningen på likningen. Det eneste som gjenstår for å finne én løsning er å gå baklengs gjennom utregninga.

Alle løsningene er på formen:
x = x0 + b’t
y = y– a’t
der x0 og y0 er én løsning på likningen, a’ = a/gcd(a,b) og b’ = b/gcd(a,b)

Eksempel:

Løs likningen 321x + 78y = 3
(her ar a = 321, b = 78 og c = 3)
Som beskrevet over er det første vi gjør å regne ut gcd(a,b), her bruker vi Euklids algoritme:
gcd(321,78):
321 = 4×78 + 9
78 = 8×9 + 6
9 = 1×6 + 3 (tydelig at 36, så vi trenger ikke regne mer)

Siden gcd(321,78) = 3, og 33 (gcd(a,b)c) vet vi at likningen har løsning. For å finne løsningen går vi baklengs, og begynner med å snu på likningen 9 = 1×6 + 3
3 = 9 – 1×6 (så setter vi inn for 6 ved hjelp av likningen 78 = 8×9 + 6 => 6 = 78 – 8×9)
3 = 9 – 1×(78-8×9) = 9 – 78 + 8×9 = -78 + 9×9 (så setter vi inn for 9)
3 = -78 + 9×(321 – 4×78) = -78 + 9×321 -36×78 = 9×321 – 37×78
3 = 9×321 -37x78

Dermed har vi en løsning: x0 = 9 og y0 = -37
For å finne flere løsninger:
a’ = a/gcd(a,b) = 321/gcd(321,78) = 321/3= 107
b’ = b/gcd(a,b) = 78/gcd(321,78) = 78/3 = 26
x = x0 + b’t = 9 + 26t
y = y0 + a’t = -37 – 107t
For et alle heltall t.