matematikk.net

Lurer på framgangsmåten på å løse denne diofantiske ligningen:

17x + 13y = 1

I følge fasiten skal dette bli:

x = 10-13t
y = 13-17t

Men ser ikke hvordan en kommer frem til dette.

kan en ikke bare skrive første som

[tex]17x=1-13y[/tex]

[tex]17x\equiv 1(mod\,13)[/tex]

[tex]17x\equiv 1+13^2(mod\,13)\equiv 170(mod\,13)[/tex]

[tex]x\equiv 10(mod\,13)[/tex]

[tex]x=10-13t[/tex]

evt

[tex]x=10+13t[/tex]

[tex]t \in Z[/tex]

-----------------------------
og tilsvarende for 13y = 1 - 17x

Dette er en tre-stegsprosess. Hvilken del er det som byr på problemer?:

1) Bruk euklids algoritme til å finne en lineær kombinasjon av koeffisientene i ax + by som gir deg gcd(a,b).

2) Bruk dette til å finne to tall som tilfredsstiller likningen over

2) Utvid resultatet til den generelle løsningen

Er vel euklids algoritme jeg må jobbe mer med, skal se på noen fler oppgaver og se om jeg ikke ser tankegangen her, så får jeg heller komme med flere spørsmål her hvis jeg fremdeles ikke finner ut av det.