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. $ax^2 + 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.

Likninger på formen $ax + by = c$, der $a$ og $b$ er hele tall, og vi bare er ute etter løsninger der $x$ og $y$ er hele tall, kaller vi lineære, diofantiske likninger, oppkalt etter grekeren Diofantos.

Hvis vi for eksempel skal ta ut 2500 kroner av minibanken og lurer på hvordan vi kan kombinere sedler på 500 og 200 kroner, finner vi svaret ved å løse den lineære, diofantiske likningen $500x + 200y = 2500$, der $x$ er antall 500-lapper og $y$ er antall 200-lapper.

Alle diofantiske likninger vi ser på i denne artikkelen er lineære, selv om vi for enkelhets skyld av og til bare sier "diofantiske likninger".

Eksistens av løsninger

Hvis vi i stedet for å spørre om hvordan vi kan kombinere femhundrelapper og tohundrelapper til 2500 kroner, spør om hvordan vi kan kombinere tusenlapper og tohundrelapper til 2500 kroner, skjønner vi fort at det ikke går. Det finnes altså ikke noen heltallsløsninger av likningen
$1000x + 200y = 2500$, der $x$ er antall 1000-lapper og $y$ er antall 200-lapper.

Det er nemlig slik at ikke alle diofantiske likninger har løsning. Så før vi går i gang med å prøve å løse en diofantisk likning, bør vi undersøke om den faktisk er løsbar.

Hva er egentlig grunnen til at vi kan kombinere 500-lapper og 200-lapper til 2500 kroner, men ikke 1000-lapper og 200-lapper? 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 500-lapper og 200-lapper er mulig "å treffe på" 2500 kroner, mens vi med 1000-lapper og 200-lapper "hopper forbi" 2500 kroner. 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 likning } ax + by = c \text{ har heltallsløsninger 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 én eller begge løsningene 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 kilo til totalt 11 kilo, 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 \mid 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.

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 $a \equiv b \; (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 $ax \equiv c \; (mod \: n)$.

En lineær, diofantisk likning, $ax + by = c$, kan altså skrives om til en kongruenslikning, $ax \equiv c \; (mod \, b)$ eller $by \equiv 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 200- og 500-lappene på følgende måte:

Vi starter med likningen $500x + 200y = 2500$

Flytter y-leddet over på høyre side: $500x = 2500 – 200y$

Skriver som kongruenslikning: $500x \equiv 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 \equiv 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 \equiv 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 \equiv 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.

Setter vi $x = 1$ inn i den opprinnelige likningen, får vi $500 \cdot1 + 200y = 2500$, som løst mhp. $y$ gir $y = 10$.

Vi kan altså få 2500 kroner ved å kombinere én 500-lapp og ti 200-lapper.

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 har uendelig mange løsninger. Dette kommer vi tilbake til i et senere avsnitt.

Men først spør vi oss hvorfor det var $b$ og ikke $a$ vi brukte som modulus da vi omformet den diofantiske likningen til en kongruenslikning. Hvorfor erstattet vi $ax + by = c$, med $ax \equiv c \; (mod \: b)$ og ikke med $by \equiv c \; (mod \: a)$? Svaret er at det ikke er noen grunn, det ene er like riktig som det andre. Så utregningen med pengesedlene kunne like gjerne vært slik:

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$.

Skriver som kongruenslikning: $200y \equiv 2500 \; (mod \; 500)$.

Vi har $SFF(a, n) = SFF(200, 500) = 100$. Vi dividerer alle ledd med $100$ og får: $2y \equiv 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 \equiv 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å kan 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.

Setter vi $y = 0$ inn i den opprinnelige likningen, får vi $500x + 200 \cdot 0 = 2500$, som løst mhp. $x$ gir $x = 5$.

Vi kan altså få 2500 kroner ved å bruke fem 500-lapper og ingen 200-lapper.

Vi fikk ikke samme svar i eksempel 3 som i eksempel 2, da vi brukte $b$ som modulus og flyttet $y$-leddet over til høyre side, men den diofantiske likningen har altså uendelig mange løsninger, og når har vi funnet en av de andre.

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 1:

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 én femhundrelapp og ti tohundrelapper når vi regnet modulo $200$, og fem femhundrelapper og ingen tohundrelapper når vi regnet modulo $500$. 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 = x_0$ og $y = y_0$, 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 helt tall, og $d = SFF(a, b)$.

Forklart med ord betyr dette at når vi har funnet et tallpar, $x_0$ og $y_0$, som er en løsning, kan vi finne nye løsningspar, $x_k$ og $y_k$, ved å addere heltallige multipler av $\frac{\displaystyle b}{\displaystyle d}$ til $x_0$, og å subtrahere heltallige multipler av $\frac{\displaystyle a}{\displaystyle d}$ fra $y_0$, 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$ er $x_0 = 1$ og $y_0 = 10$. Vi har da at $a = 500$, $b = 200$ og $d = SFF(200, 500) = 100$. Så som et generelt uttrykk for $x_k$ og $y_k$ 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:

$x_0 = 5$ og $y_0 = 0$. Vi har som før $a = 500$, $b = 200$ og $d = 100$. Så da får vi som et generelt uttrykk for $x_k$ og $y_k$:

$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 femhundrelapp og 10 tohundrelapper

3 femhundrelapper og 5 tohundrelapper

5 femhundrelapper og 0 tohundrelapper

Oppgave 2:

Finn et uttrykk for alle løsninger til den lineære, diofantiske likningen fra oppgave 1, $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.

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 $x_k \geq 0$ og $y_k \geq 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 $x_0$, $y_0$, $a$, $b$ og $d$ og løse ulikhetene mhp. $k$.

Eksempel 6:

I eksempel 4, da vi regnet modulo $200$, fikk vi følgende generelle uttrykk for $x$ og $y$:

$x_k = 1 + 2k$

$y_k = 10 – 5k$

Her må vi altså ha at

$1 + 2k \geq 0$, noe som gir $k \geq – 0,5$

og

$10 – 5k \geq 0$, noe som gir $k \leq 2$.

Det betyr altså at $-0,5 \leq k \leq 2$. Siden $k$ må være hele tall, tilsvarer dette $k = 0$, $k = 1$ og $k = 2$, slik vi fant i tabellen i eksempel 4.

Eksempel 7:

I eksempel 5, da vi regnet modulo $500$, fikk vi følgende generelle uttrykk for $x$ og $y$:

$x_k = 5 + 2k$

$y_k = -5k$

Her må vi altså ha at

$5 + 2k \geq 0$, noe som gir $k \geq – 2,5$

og

$-5k \geq 0$, noe som gir $k \leq 0$.

Det betyr altså at $-2,5 \leq k \leq 0$. Siden $k$ må være hele tall, tilsvarer dette $k = -2$, $k = -1$ og $k = 0$, slik vi fant i tabellen i eksempel 5.

​Oppgave 3:

Finn alle ikke-negative løsninger til den lineære, diofantiske likningen fra oppgave 1 og 2, $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 = -{\large \frac{a}{b}}x + {\large\frac{c}{b}}$. Dette kjenner vi igjen som likningen for ei rett linje med stigningstall $-{\large \frac{a}{b}}$ som skjærer y-aksen i ${\large \frac{c}{b}}$.

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 ${\large -\frac{a}{b}}$, komme fra én heltallsløsning, $(x, y)$, til neste ved å addere $b$ til $x$ og $-a$ til $y$: $(x + b, y – a)$.

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

I eksemplet med sedlene hadde vi likningen $500x + 200y = 2500$, som omformet og forkortet blir $y = -{\large \frac{5}{2}}x + {\large \frac{25}{2}}$, med en graf som ser slik ut:

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

Her har vi markert de ikke-negative, heltallige løsningene, som var $(1, 10)$, $(3, 5)$ og $(5, 0)$. Stigningstallet er ${\large -\frac{5}{2}}$, og vi ser at vi kommer fra ett løsningspunkt til det neste ved å bruke verdiene fra stigningstallet og addere $2$ til $x$, og $-5$ til $y$.

Oppgave 4:

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

Se løsningsforslag

Oppgave 5:

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 \ne 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}3 &= {\color{brown}{43}} – 8 \cdot {\color{brown}{5}} \\
2 &= {\color{brown}{5}} – 1 \cdot {\color{brown}{3}} \\
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 6:

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) \mid 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 \mid 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 \cdot 2 = 10$, $y = 5 \cdot (-7) = -35$ løsninger til likningen $25x + 7y = 5$.

Oppgave 7:

Finn en løsning til likningen fra oppgave 1,  $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.
  • Wikipedia
  •