Lineare diofantiske ligninger

Dette innlegget har allerede blitt vist 2039 ganger!

En linear diofantisk ligning er en ligning på formen ax + bx = c, der alle tallene er i Ζ (heltall).

Lingningen har løsning hvis og bare hvis gcd(a,b) c, altså c = gcd(a,b)*q for ett heltall q.

Alle løsninger er på formen x = x0 + b’*t, y = y0 – a’*t der a’ = a/gcd(a,b) og b’ = b/gcd(a,b).

For å finne x0 og y0 bruker vi euklids algoritme: (tar utgangspunkt i at a > b, hvis ikke, gjør motsatt).
Dersom ba: gcd(a,b) = b
Ellers: gcd(a,b) = gcd(b, a mod b).

Fra dette regner vi oss tilbake i motsatt rekkefølge til vi finner x0 og y0.