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.

Likninger på formen ax + by = c, der a, b og c 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. 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 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 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 | 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.

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 å få 2500 kroner ved hjelp av 200- og 500-lapper 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 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 også 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 axc (mod b) og ikke med byc (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 1: 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 kroner ved å bruke fem 500-lapper og ingen 200-lapper.

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 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 = 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 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 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 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 mhp. 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 altså ha at

1 + 2k ≥ 0, noe som gir k ≥ -0,5.

og

10 – 5k ≥ 0, noe som 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

5 + 2k ≥ 0, noe som gir k ≥ -2,5.

og

– 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 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 = -\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 500- og 200-lapper kunne kombineres til 2500 kroner, 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 ≠ 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 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) | 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 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.
  •