Diofantiske likninger

Hva er diofantiske likninger

En likning på formen ax + by = c, der a, b og c er vilkårlige tall, kaller vi for en lineær likning. Et annet ord for lineær likning er førstegradslikning, fordi de ukjente, x og y er av første grad. Dette i motsetning til en likning som f.eks. ax2 + by = c, som er en andregradslikning.

Med å løse en slik likning mener vi å finne alle kombinasjoner av x og y som gjør at uttrykket på venstre og høyre side av likhetstegnet har samme verdi.

Eksempel 1:

Vi ser på likningen x + 2y = 2. (Her er a = 1, b = 2 og c = 2.)

Løser vi mhp. y, får vi $y = −{\large \frac{x}{2}} + 1$. Grafisk sett er dette ei rett linje med stigningstall $−{\large \frac{1}{2}}$, som skjærer y-aksen i y = 1:

Heltallsløsninger av likningen x + 2y = 2

I noen punkter på ei slik linje kan det være at både x og y er hele tall, slik som markert i grafen over.

En likning med flere ukjente der vi bare er ute etter heltallige løsninger, kalles diofantiske likninger, oppkalt etter grekeren Diofantos. Det vi skal studere i denne artikkelen, er lineære diofantiske likninger med to ukjente, det vil si likninger på formen ax + by = c, der a, b og c er hele tall. For enkelhets skyld kommer vi bare til å kalle dette diofantiske likninger.

Eksistens av løsninger

Hvis vi lurer på hvordan vi kan kombinere sedler på 500 kr og 200 kr til 2500 kr, vil svaret på dette være løsninger til den diofantiske likningen 500x + 200y = 2500, der x er antall sedler på 500 kr og y er antall sedler på 200 kr. Ved å prøve oss fram finner vi ut at det finnes tre muligheter:

x = 1, y = 10, altså 1 · 500 kr + 10 · 200 kr.

x = 3, y = 5, altså 3 · 500 kr + 5 · 200 kr.

x = 5, y = 0, altså 5 · 500 kr.

Men hvis vi i stedet spør om hvordan vi kan kombinere sedler på 1000 kr og 200 kr til 2500 kr, skjønner vi at det ikke går. Det finnes altså ikke noen heltallige løsninger av likningen 1000x + 200y = 2500, der x er antall sedler på 1000 kr og y er antall sedler på 200 kr.

Plottet under viser grafene til de to likningene. 500x + 200y = 2500 i blått, med de heltallige løsningene markert, og 1000x + 200y = 2500 i grønt. Vi ser at den grønne grafen ikke går gjennom noen punkter der både x og y er hele tall.

Grafer til to diofantiske likninger

Men hva er egentlig grunnen til at vi kan kombinere sedler på 500 kr og 200 kr til 2500 kr, men ikke sedler på 1000 kr og 200 kr? Med andre ord, hva er den prinsipielle forskjellen på de diofantiske likningene 500x + 200y = 2500 og 1000x + 200y = 2500?

Intuitivt kan vi si at det med sedler på 500 kr og 200 kr er mulig «å treffe på» 2500 kr, mens vi med sedler på 1000 kr og 200 kr «hopper forbi» 2500 kr. Vi kan få 2400 og 2600, men ikke 2500. Den matematiske årsaken har med største felles faktor, SFF, å gjøre:

Vi har SFF(500, 200) = 100, og SFF(1000, 200) = 200. Og forskjellen er at 100 går opp i totalbeløpet på 2500, mens 200 ikke gjør det. Generelt har vi:

$\fbox{$ \text{En diofantisk likning } ax + by = c \text{ har løsning hvis og bare hvis } SFF(a, b) \, | \, c$}$

Med andre ord må alle tall som går opp i a og b også gå opp i c. Største felles faktor lærte vi om i artikkelen om faktorisering.

Det kan imidlertid være at x og/eller y er negative tall, slik at løsningene ikke kan representere fysiske enheter. Spør vi for eksempel hvordan vi kan kombinere vekter på 4 og 5 kg til totalt 11 kg, skjønner vi at det ikke går. Men det betyr ikke at likningen 4x + 5y = 11 ikke har løsning, for SFF(4, 5) = 1 | 11. Men løsningene involverer negative tall, for eksempel y = −1 hvis x = 4. Og siden vi ikke kan ha et negativt antall vekter, finnes ingen fysisk løsning.

En diofantisk likning som er løsbar, vil alltid ha et uendelig antall løsninger hvis vi aksepterer negative tall.

Oppgave 1:

Avgjør om de diofantiske likningene
4x + 12y = 16
og
3x + 12y = 16
har løsning

​Se løsningsforslag

For å løse en diofantisk likning kan vi i enkle tilfeller prøve oss fram, for eksempel ser vi lett at x = 0, y = 3, er en løsning til 5x + 4y = 12. I andre tilfeller kan dette imidlertid være vanskelig fordi tallene er for store, som for eksempel i 1257x + 389y = 47893. Det kan også være vanskelig å avgjøre om vi har funnet alle relevante løsninger.

Vi skal derfor systematisk se på metoder for å løse lineære, diofantiske likninger.

Løse ved omforming til kongruenslikninger

Hvis vi har en likning på formen ax + by = c, kan vi flytte leddet by over på høyre side, og få ax = c + b(−y). Kaller vi −y for k, og b for n, blir det ax = c + kn.

I artikkelen om kongruens lærte vi at ab (mod n) betyr at det finnes et heltall, k, slik at a = b + kn.

Siden vi i en diofantisk likning bare opererer med heltall, betyr det at ax = c + kn er det samme som axc (mod b).

En lineær, diofantisk likning, ax + by = c, kan altså skrives om til en kongruenslikning, axc (mod b) eller by ≡ c (mod a), og så løses ved hjelp av de verktøyene vi har til rådighet for å løse slike likninger, slik vi lærte i artikkelen om kongruenslikninger.

Eksempel 2:

Vi kan løse problemet med å kombinere sedler på 500 kr og 200 kr til 2500 kr på følgende måte:

Vi starter med likningen 500x + 200y = 2500

Vi flytter y-leddet over på høyre side: 500x = 2500 − 200y

Vi skriver som kongruenslikning: 500x ≡ 2500 (mod 200).

Skulle vi fulgt standardoppskriften, skulle vi nå erstattet 500 og 2500 med mindre tall som er kongruente modulo 200. Men i dette tilfellet er det så lett å finne SFF at vi gjør det først, og forenkler likningen ved å dividere.

Vi har SFF(a, n) = SFF(500, 200) = 100. Vi dividerer alle ledd med 100 og får:

5x ≡ 25 (mod 2).

Vi kan her forenkle videre ved å dividere på begge sider av kongruenstegnet med 5. Modulus forblir uendret fordi SFF(5, 2) = 1. Og vi får:

x ≡ 5 (mod 2).

Siden 5 > 2, erstatter vi 5 med $5 − \lfloor \frac{\displaystyle 5}{\displaystyle 2} \rfloor \cdot 2 = 5 − 2 \cdot 2 = 1$.

Det endelige resultatet blir x ≡ 1 (mod 2).

(Denne erstatningen kunne vi gjort uten den omstendelige utregningen, for alle oddetall er kongruente med 5 modulo 2, så vi kunne puttet inn 1 uten mer dikkedarer.)

x = 1 er altså en løsning til kongruenslikningen, og derved også til den diofantiske likningen vi startet med.

Setter vi x = 1 inn i den diofantiske likningen, altså 500x + 200y = 2500, får vi 500 · 1 + 200y = 2500, som løst mhp. y gir y = 10.

Vi kan altså få 2500 kr ved å kombinere én seddel på 500 kr og ti på 200 kr.

Vi vet at hvis en kongruenslikning modulo n har løsning, har den uendelig mange, som kan være fordelt på alt fra 1 til n restklasser. Det betyr at en løsbar diofantisk likning også har uendelig mange løsninger. Dette kommer vi tilbake til i et senere avsnitt.

I eksempel 2 var det b, ikke a, vi brukte som modulus da vi omformet den diofantiske likningen til en kongruenslikning. Men vi kan like gjerne bruke a, slik det er vist i eksempel 3.

Eksempel 3:

Vi starter med samme likning som i eksempel 2: 500x + 200y = 2500

Så flytter vi x-leddet over på høyre side: 200y = 2500 − 500x

Vi skriver som kongruenslikning:

200y ≡ 2500 (mod 500).

Vi har SFF(a, n) = SFF(200, 500) = 100. Vi dividerer alle ledd med 100 og får:

2y ≡ 25 (mod 5).

Siden 25 > 2, erstatter vi 25 med $25 − \lfloor \frac{\displaystyle 25}{\displaystyle 5} \rfloor \cdot 5 = 25 − 5 \cdot 5 = 0$.

Og vi får: 2y ≡ 0 (mod 5).

(Denne erstatningen kunne vi også gjort uten den omstendelige utregningen, for siden 5 går opp i 25, skjønner vi at 25 er kongruent med 0 modulo 5, og kunne puttet inn 0 uten mer dikkedarer.)

Nå kunne vi gått veien om en multiplikativ invers for å finne den endelige løsningen, men vi ser direkte at y = 0 er en løsning.

y = 0 er altså en løsning til kongruenslikningen, og derved også til den diofantiske likningen vi startet med.

Setter vi y = 0 inn i den diofantiske likningen, altså 500x + 200y = 2500, får vi 500x + 200 · 0 = 2500, som løst mhp. x gir x = 5.

Vi kan altså få 2500 kr med fem sedler på 500 kr ingen på 200 kr.

Vi fikk ikke samme svar i eksempel 3 som i eksempel 2, men den diofantiske likningen har altså uendelig mange løsninger, og nå har vi funnet to av dem.

Når vi skal velge om vi skal flytte x-leddet eller y-leddet over på høyre side, gjør det ofte utregningene enklere å velge slik at vi får lavest modulus. I eksempel 2 fikk vi 200 når vi flyttet y-leddet, og i eksempel 3 fikk vi 500 når vi flyttet x-leddet.

Oppgave 2:

Avgjør om den lineære, diofantiske likningen 21x + 14y = 147 er løsbar, og finn i så fall en løsning.

​Se løsningsforslag

Finne alle løsninger

I eksemplet med sedlene fikk vi 1 seddel på 500 kr og 10 sedler på 200 kr da vi regnet modulo 200, og fem sedler på 500 kr og ingen sedler på 200 kr da vi regnet modulo 500. Det er to forskjellige svar, men begge svarene er riktige. Og en løsbar diofantisk likning har altså uendelig mange løsninger.

Generelt er det slik at vi løser diofantiske likninger ved først å finne én spesiell løsning, og så generalisere ut fra den.

I artikkelen om kongruensregning så vi at det fantes uendelig mange løsninger til en løsbar kongruenslikning, og lærte hvordan vi ut fra én løsning kunne beregne hvilke restklasser løsningene lå i. Metoden kan også brukes på diofantiske likninger, men i en diofantisk likning er vi bare interessert i selve løsningene, ikke hvilke restklasser de tilhører, og hvis vi har løst den diofantiske likningen ved hjelp av Euklids algoritme baklengs, har vi heller ikke noen kongruenslikning å arbeide ut fra.

Vi angir derfor en metode til å finne alle løsninger til en lineær, diofantisk likning basert på den opprinnelige likningen. La oss si at vi har funnet et løsningspar, to heltall x = x0 og y = y0, som tilfredsstiller den diofantiske likningen ax + by = c. Da vil alle løsninger av likningen være på formen

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k$

og

$y_k = y_0 − \frac{\displaystyle a}{\displaystyle d}k$

der k er et vilkårlig helt tall, og d = SFF(a, b).

Forklart med ord betyr dette at når vi har funnet et tallpar, x0 og y0, som er en løsning, kan vi finne nye løsningspar, xk og yk, ved å addere heltallige multipler av $\frac{\displaystyle b}{\displaystyle d}$ til x0, og å subtrahere heltallige multipler av $\frac{\displaystyle a}{\displaystyle d}$ fra y0, der vi henter a og b fra den opprinnelige likningen og beregner d som SFF(a, b). For eksempel

$x_1 = x_0 + \frac{\displaystyle b}{\displaystyle d} \cdot 1$ og $y_1= y_0 − \frac{\displaystyle a}{\displaystyle d} \cdot 1$

$x_2 = x_0 + \frac{\displaystyle b}{\displaystyle d} \cdot 2$ og $y_2 = y_0 − \frac{\displaystyle a}{\displaystyle d} \cdot 2$

$x_{−1} = x_0 + \frac{\displaystyle b}{\displaystyle d}(−1)$ og $y_{−1} = y_0 − \frac{\displaystyle a}{\displaystyle d}(−1)$

$x_{−2} = x_0 + \frac{\displaystyle b}{\displaystyle d}(−2)$ og $y_{−2} = y_0 − \frac{\displaystyle a}{\displaystyle d}(−2)$

og så videre. Det finnes i utgangspunktet uendelig mange muligheter, og vi finner dem ved å sette inn forskjellige verdier av k. For eksempel 1, 2, −1, −2, slik vi har vist over.

Eksempel 4:

I eksempel 2 fant vi at en løsning av den diofantiske likningen 500x + 200y = 2500.

Vi har da at a = 500, b = 200 og d = SFF(200, 500) = 100.

Og vi har sett at x0 = 1 og y0 = 10 er en løsning til denne likningen. Så, som et generelt uttrykk for xk og yk, får vi:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k = 1 + {\large \frac{200}{100}}k = 1 + 2k$

$y_k = y_0 − \frac{\displaystyle a}{\displaystyle d}k = 10 − {\large \frac{500}{100}}k = 10 − 5k$

Tabellen under viser løsningene for verdier av k mellom −5 og 5. Alle parene av x og y gir riktig løsning av likningen, men hvis x og y skal representere antall pengesedler, kan tallene ikke være negative. Løsningene der både x og y er større eller lik null er derfor markert med gult.

k −5 −4 −3 −2 −1 0 1 2 3 4 5
x −9 −7 −5 −3 −1 1 3 5 7 9 11
y 35 30 25 20 15 10 5 0 −5 −10 −15

Eksempel 5:

Tar vi utgangspunkt i løsningen i eksempel 3, får vi følgende utregning når vi vil finne alle løsninger:

x0 = 5 og y0 = 0. Vi har som før at a = 500, b = 200 og d = SFF(200, 500) = 100. Så da får vi som et generelt uttrykk for xk og yk:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k = 5 + {\large \frac{200}{100}}k = 5 + 2k$

$y_k = y_0 − \frac{\displaystyle a}{\displaystyle d}k = 0 − {\large \frac{500}{100}}k = − 5k$

Tabellen under viser løsningene for verdier av k mellom −5 og 5. Kombinasjoner der både x og y er større eller lik null er markert med gult.

k −5 −4 −3 −2 −1 0 1 2 3 4 5
x −5 −3 −1 1 3 5 7 9 11 13 15
y 25 20 15 10 5 0 −5 −10 −15 −20 −25

Vi ser at tallene markert med gult er de samme i tabellene i eksempel 4 og 5. k er forskjellig, men det har ingen betydning for løsningene.

Vi kan altså få 2500 kroner ved å kombinere

1 seddel på 500 kr og 10 sedler på 200 kr.

3 sedler på 500 kr og 5 sedler på 200 kr.

5 sedler på 500 kr og ingen sedler på 200 kr.

Oppgave 3:

Finn et uttrykk for alle løsninger til den lineære, diofantiske likningen fra oppgave 2, 21x + 14y = 147.

​Se løsningsforslag

Finne ikke-negative løsninger

Som vi så et eksempel på da vi regnet med sedler, er vi av og til ikke interessert i negative løsninger av en diofantisk likning. Slik er det ofte når vi opererer med ting fra den virkelige verden. Skruer og muttere, voksne og barn, gule og røde lodd, etc. Vi må alltid ha 0 eller flere enheter.

Skal vi holde oss til ikke-negative løsninger, betyr det at vi i den generelle løsningen må begrense k slik at vi bare får løsninger der xk ≥ 0 og yk ≥ 0. Det vil si at vi i det generelle uttrykket vi fant for x og y må ha

$x_0 + \frac{\displaystyle b}{\displaystyle d}k \geq 0$

og

$y_0 − \frac{\displaystyle a}{\displaystyle d}k \geq 0$

Her må vi altså sette inn verdiene vi finner for x0, y0, a, b og d, og løse ulikhetene med hensyn på k.

Eksempel 6:

I eksempel 4, da vi regnet modulo 200, fant vi at et generelt uttrykk for løsningen til likningen 500x + 200y = 2500 var:

xk = 1 + 2k

yk = 10 − 5k

Her må vi ha at xk = 1 + 2k ≥ 0.

Vi løser ulikheten ved å flytte 1 over til høyre side med fortegnsskifte og dividere begge sider med 2, noe som gir k ≥ −0,5.

Vi må også ha at yk = 10 − 5k ≥ 0.

Vi løser ulikheten ved å flytte 10 over til høyre side med fortegnsskifte og dividere begge sider med −5. Vi husker at vi må snu ulikhetstegnet når vi didviderer med et negativt tall, så dette gir k ≤ 2.

Det betyr altså at −0,5 ≤ k ≤ 2. Siden k må være hele tall, tilsvarer dette k = 0, k = 1 og k = 2.

Og vi får

x0 = 1 + 2 · 0 = 1
y0 = 10 − 5 · 0 = 10

x1 = 1 + 2 · 1 = 3
y1 = 10 − 5 · 1 = 5

x2 = 1 + 2 · 2 = 5
y2 = 10 − 5 · 2 = 0

Altså (1, 10), (3, 5) og (5, 0).

Som er det samme som vi fant i tabellen i eksempel 4.

Eksempel 7:

I eksempel 5, da vi regnet modulo 500, fant vi et annet generelt uttrykk for løsningen til likningen 500x + 200y = 2500 som var:

xk = 5 + 2k

yk = − 5k

Her må vi altså ha at

xk = 5 + 2k ≥ 0, noe som gir k ≥ −2,5.

og

yk = −5k ≥ 0, noe som gir k ≤ 0.

Det betyr altså at −2,5 ≤ k ≤ 0. Siden k må være hele tall, tilsvarer dette k = −2, k = −1 og k = 0.

Og vi får
x−2 = 5 + 2(−2) = 1
y−2 = −5(−2) = 10

x−1 = 5 + 2(−1) = 3
y−1 = −5(−1) = 5

x0 = 5 + 2 · 0 = 5
y0 = −5 · 0 = 0

Altså (1, 10), (3, 5) og (5, 0).

Som er det samme som vi fant i tabellen i eksempel 5.

​Oppgave 4:

Finn alle ikke-negative løsninger til den lineære, diofantiske likningen fra oppgave 2 og 3, 21x + 14y = 147.

Se løsningsforslag

Grafisk framstilling av løsninger

En lineær likning på formen ax + by = c kan ved hjelp av enkel algebra omformes til $y = −\frac{\displaystyle a}{\displaystyle b}x + \frac{\displaystyle c}{\displaystyle b}$. Dette kjenner vi igjen som likningen for ei rett linje med stigningstall $−\frac{\displaystyle a}{\displaystyle b}$ som skjærer y-aksen i $\frac{\displaystyle b}{\displaystyle c}$.

I introduksjonen skrev vi likningen x + 2y = 2 på denne måten som $y = −{\large \frac{1}{2}}x + 1$, en funksjon som har grafen under.

Heltallsløsninger av likningen x + 2y = 2

I grafen er punkter som er heltallige løsninger av likningen, markert. Vi ser at hvis vi fra ett av disse punktene går to skritt til høyre og ett ned, kommer vi til neste punkt. Mer formelt sagt adderer vi 2 til x-verdien, og adderer −1 til y-verdien

Tallene 2 og −1 kommer fra stigningstallet. Generelt vil vi i grafen til ax + by = c , med stigningstall $−\frac{\displaystyle a}{\displaystyle b}$, komme fra én heltallsløsning, (x, y), til neste ved å addere b til x og −a til y: (x + b, ya).

Vi kan selvsagt også gå fra høyre mot venstre ved å subtrahere b fra x og −a fra y: (xb, y +a).

I eksemplet der vi studerte hvordan sedler på 500 kr og 200 kr kunne kombineres til 2500 kr, hadde vi likningen 500x + 200y = 2500, som omformet og forkortet blir $y = −{\large \frac{5}{2}}x + {\large \frac{25}{2}}$. Grafen til denne funksjonen er vist under, med de heltallige løsningene (1, 10), (3, 5) og (5, 0) markert.

Heltallsløsninger til likningen 500x + 200y = 2500

Grafen til 500x + 200y = 2500 med heltallsløsninger markert

Her er stigningstallet $−{\large \frac{5}{2}}$, så a = 5, b = 2. Starter vi i (1, 10) og bruker formelen (x+b, ya), får vi (1+2, 10−5) = (3, 5). Gjør vi det samme en gang til, får vi (3+2, 5−5) =(5, 0). Som er de to andre løsningene til den diofantiske likningen.

Oppgave 5:

Løs likningen fra oppgave 2, 3 og 4, 21x + 14y = 147, som en vanlig likning med hensyn på y og tegn grafen i GeoGebra. Plott inn løsningene fra oppgave 4.

Se løsningsforslag

Oppgave 6:

En snekker lager krakker med 3 bein og bord med 4 bein. En dag har han brukt opp 33 bein, hvor mange krakker og bord han kan ha laget?

Se løsningsforslag

Vi skal avslutte med å se på et alternativ til å løse diofantiske likninger ved å skrive dem om til kongruenslikninger, Euklids algoritme baklengs.

Løse ved Euklids algoritme baklengs

I artikkelen om faktorisering lærte vi å bruke Euklids algoritme til å finne to talls største felles faktor. Brukt baklengs kan algoritmen benyttes til å løse lineære, diofantiske likninger.

Metoden virker i utgangspunktet bare på spesialtilfeller av den diofantiske likningen ax + by = c, der SFF(a, b) = 1 og c = 1, men utvides lett til å fungere også når SFF(a, b) > 1 eller c ≠ 1.

Prinsippet er at vi tar utgangspunkt i likningen ax + by = 1 og bruker Euklids algoritme til å finne SFF(a, b). Så nøster vi oss tilbake gjennom utregningen for å finne en lineær kombinasjon av a og b som er en løsning til likningen.

Vi illustrerer med et par eksempler.

Eksempel 8:

Vi skal løse likningen 43x + 5y = 1.

Her er SFF(a, b) = 1 og c = 1.

Vi starter med å bruke Euklids algoritme til å finne SFF(43, 5).

$\begin{align}43 &= 8 \cdot 5 + 3\\
5 &= 1 \cdot 3 + 2\\
3 &= 1 \cdot 2 + 1\\
2 &= 2 \cdot 1 + 0 \end{align}$

Konklusjonen er at SFF(43, 5) = 1, men det visste vi jo allerede. Det vi egentlig er ute etter, er å uttrykke resten, r, som en lineær kombinasjon av de to andre tallene, a og b. I siste linje er resten 0, så den er ikke så interessant. Men de andre linjene skriver vi om som vist under, a og b er markert med brunt:

$\begin{align}43 &= 8 \cdot 5 + 3 \, \Rightarrow \, 3 = {\color{brown}{43}} − 8 \cdot {\color{brown}{5}}\\
\\
5 &= 1 \cdot 3 + 2 \, \Rightarrow \, 2 = {\color{brown}{5}} − 1 \cdot {\color{brown}{3}}\\
\\
3 &= 1 \cdot 2 + 1 \, \Rightarrow \, 1 = {\color{brown}{3}} − 1 \cdot {\color{brown}{2}}\end{align}$

I siste linje erstatter vi så 2-tallet med uttrykket i linja over:

Estatning av tall i Euklids algoritme baklengs

Altså

$1 = {\color{brown}{3}} − 1 \cdot {\color{brown}{2}}$
$\Downarrow$
$1 = {\color{brown}{3}} − 1 \cdot ({\color{brown}{5}} − 1 \cdot {\color{brown}{3}})$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{3}} − 1 \cdot {\color{brown}{5}}$

Vi passer på å ikke gjøre utregningene fullt ut, i stedet holder vi rede på hvor mange av de brune tallene vi har.

Vi har nå

$\begin{align}3 &= {\color{brown}{43}} − 8 \cdot {\color{brown}{5}}\\
1 &= 2 \cdot {\color{brown}{3}} − 1 \cdot {\color{brown}{5}} \\
\end{align}$

I siste linje erstatter vi 3-tallet med uttrykket i linja over

Estatning av tall i Euklids algoritme baklengs

Altså

$1 = 2 \cdot {\color{brown}{3}} − 1 \cdot {\color{brown}{5}}$
$\Downarrow$
$1 = 2 \cdot ({\color{brown}{43}} − 8 \cdot {\color{brown}{5}}) − 1 \cdot {\color{brown}{5}}$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{43}} − 17 \cdot {\color{brown}{5}}$

Det betyr at x = 2, y = 17 er en løsning til den diofantiske likningen 43x + 5y = 1, som vi startet med.

Eksempel 9:

Vi skal løse likningen 25x + 7y = 1.

Her er SFF(a, b) = 1 og c = 1.

Vi starter med å bruke Euklids algoritme til å finne SFF(25, 7):

$\begin{align}25 &= 3 \cdot 7 + 4\\
7 &= 1 \cdot 4 + 3\\
4 &= 1 \cdot 3 + 1\\
3 &= 3 \cdot 1 + 0 \end{align}$

Vi dropper den siste linja, i de andre uttrykker vi resten, r, som en lineær kombinasjon av a og b, markert med brunt:

$\begin{align}4 &= {\color{brown}{25}} − 3 \cdot {\color{brown}{7}} \\
3 &= {\color{brown}{7}} − 1 \cdot {\color{brown}{4}} \\
1 &= {\color{brown}{4}} − 1 \cdot {\color{brown}{3}} \\
\end{align}$

I siste linje erstatter vi så 3-tallet med uttrykket i linja over

$1 = {\color{brown}{4}} − 1 \cdot {\color{brown}{3}}$
$\Downarrow$
$1 = {\color{brown}{4}} − 1 \cdot ({\color{brown}{7}} − 1 \cdot {\color{brown}{4}})$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{4}} − 1 \cdot {\color{brown}{7}}$

Vi har nå

$\begin{align}4 &= {\color{brown}{25}} − 3 \cdot {\color{brown}{7}}\\
1 &= 2 \cdot {\color{brown}{4}} − 1 \cdot {\color{brown}{7}} \\
\end{align}$

I siste linje erstatter vi 4-tallet med uttrykket i linja over

$1 = 2 \cdot {\color{brown}{4}} − 1 \cdot {\color{brown}{7}}$
$\Downarrow$
$1 = 2 \cdot ({\color{brown}{25}} − 3 \cdot {\color{brown}{7}}) − 1 \cdot {\color{brown}{7}}$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{25}} − 7 \cdot {\color{brown}{7}}$

Det betyr at x = 2, y = −7 er en løsning til den diofantiske likningen 25x + 7y = 1, som vi startet med.

Oppgave 7:

Finn en løsning til den diofantiske likningen 11x + 3y = 1, ved hjelp av Euklids algoritme baklengs.

​Se løsningsforslag

Så langt har vi altså sett på spesialtilfeller av den diofantiske likningen ax + by = c, der SFF(a, b) = 1 og c = 1. Nå skal vi generalisere metoden ved hjelp av to enkle triks.

Siden vi må ha SFF(a, b) | c for at likningen skal ha løsning, vil vi alltid kunne forkorte likningen med SFF(a, b), slik at vi får SFF(a, b) = 1.

Eksempel 10:

Vi skal løse den diofantiske likningen 50x + 14y = 10. Her har vi SFF(50, 14) = 2. Siden 2 | 10, har likningen løsning. Vi forkorter med 2 og får

25x + 7y = 5, som vi arbeider videre med i eksempel 11.

Siden vi kan multiplisere med samme tall på begge sider i en likning, vil vi, hvis a og b er løsninger til ax + by = 1, ha at ca og cb er løsninger til ax + by = c. Vi kan altså løse likningen ax + by = c ved først å løse ax + by = 1, og så multiplisere svarene med c.

Eksempel 11:

Vi skal løse den diofantiske likningen 25x + 7y = 5. Vi ser da først på likningen 25x + 7y = 1. Denne likningen løste vi i eksempel 9, og fikk

x = 2, y = −7.

Derfor er x = 5 · 2 = 10, y = 5 · (−7) = −35 løsninger til likningen 25x + 7y = 5.

Oppgave 8:

Finn en løsning til likningen fra oppgave 2, 21x + 14y = 147, ved hjelp av Euklids algoritme baklengs. 

​Se løsningsforslag

Vi så tidligere at en lineær, diofantisk likning kan gjøres om til en kongruenslikning, og selvsagt kan vi også gå andre veien, gjøre en kongruenslikning om til en diofantisk likning. Det betyr at Euklids algoritme baklengs også kan brukes til å løse kongruenslikninger ved at vi først gjør dem om til diofantiske likninger.

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
    • Rinvold, A. R. (2009). Visuelle perspektivTallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.