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:
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.
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 omtaler vi 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 likningen 5x + 4y = 12 har løsning x = 0, y = 3. 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ærer vi at a ≡ 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 ≡ c (mod b).
En lineær, diofantisk likning, ax + by = c, kan altså skrives om til en kongruenslikning, ax ≡ c (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 det beskrives 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 én seddel på 500 kr og ti 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 ser vi at det finnes uendelig mange løsninger til en løsbar kongruenslikning, og lærer hvordan vi ut fra én løsning kan beregne hvilke restklasser løsningene ligger 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 er en løsning til 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:
Vi ser på likningen 500x + 200y = 2500. Her er a = 500, b = 200 og d = SFF(200, 500) = 100.
I eksempel 2 fant vi 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:
I eksempel 3 fant vi at x0 = 5 og y0 = 0 er en løsning til likningen 500x + 200y = 2500. Tar vi utgangspunkt i denne løsningen, får vi følgende utregning når vi vil finne alle løsninger:
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 kr 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. Vi får altså to ulikheter vi må løse. Metoder for å løse ulikheter gjennomgås i algebra-artikkelen om ulikheter.
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
For å få xk ≥ 0, må vi altså ha 1 + 2k ≥ 0, og for å få yk ≥ 0, må vi ha 10 − 5k ≥ 0.
For å løse ulikheten 1 + 2k ≥ 0, flytter vi 1 over til høyre side med fortegnsskifte, og dividerer begge sider med 2, noe som gir k ≥ −0,5.
For å løse ulikheten 10 − 5k ≥ 0, flytter vi 10 over til høyre side med fortegnsskifte, og dividerer begge sider med −5. Vi må snu ulikhetstegnet når vi dividerer med et negativt tall, så dette gir k ≤ 2.
Vi har altså at k ≥ −0,5 og k ≤ 2, som vi kan skrive som −0,5 ≤ k ≤ 2. Siden k må være hele tall, tilsvarer dette k = 0, k = 1 og k = 2.
Da får vi
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
For å få xk ≥ 0, må vi altså ha 5 + 2k ≥ 0, og for å få yk ≥ 0, må vi ha −5k ≥ 0.
For å løse ulikheten 5 + 2k ≥ 0, flytter vi 5 over til høyre side med fortegnsskifte, og dividerer begge sider med 2, noe som gir k ≥ −2,5.
For å løse ulikheten −5k ≥ 0, dividerer vi begge sider med −5. Vi må snu ulikhetstegnet når vi dividerer med et negativt tall, så dette gir k ≤ 0.
Vi har altså at k ≥ −2,5 og k ≤ 0, som vi kan skrive som −2,5 ≤ k ≤ 0. Siden k må være hele tall, tilsvarer dette k = −2, k = −1 og k = 0.
Da får vi
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, altså 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.
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, 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 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.
Her er stigningstallet $−{\large \frac{5}{2}}$, så a = 5, b = 2. Starter vi i (1, 10) og bruker formelen (x+b, y−a), 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
Et alternativ til å løse diofantiske likninger ved å skrive dem om til kongruenslikninger er Euklids algoritme baklengs.
Løse ved Euklids algoritme baklengs
I artikkelen om faktorisering lærer 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:
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
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 perspektiv. Tallteori. 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.
Last ned regneark med tabellen vist over
