1.3 Lineære diofantiske likninger (ax + by = c)

$$ax+by=c,$$

der $a$, $b$ og $c$ er gitte hele tall, og der vi bare godtar hele tall som løsninger for $x$ og $y$.

Ordet diofantisk betyr nettopp «vi krever heltallsløsninger». Uten kravet ville likningen vært trivielt løsbar: velg $x=0$ og $y=c/b$, og du er ferdig. Det er heltallskravet som gjør oppgaven til et tallteoretisk spørsmål.

Ordet lineær betyr at $x$ og $y$ opptrer i første potens. Ikke-lineære diofantiske likninger finnes også i pensum: $x^2-Dy^2=1$ er Pells likning (kap. 7.1), og $x^2+y^2=z^2$ gir de pytagoreiske triplene (kap. 7.2). De løses med helt andre metoder.

Geometrisk: $ax+by=c$ er en rett linje i planet, og vi spør hvilke gitterpunkt (punkt med heltallskoordinater) linja treffer. Svaret er enten ingen, eller uendelig mange jevnt fordelt langs linja — aldri et endelig antall.

Slik finner du den, i to skritt:

1. Etter Bézout, finn $x',y'$ med $ax'+by'=d$ (substitusjonskjeden baklengs fra kap. 1.2).
2. Skalér med $k=c/d$:
$$x_0=k\,x',\qquad y_0=k\,y'.$$

Da er $ax_0+by_0=k\cdot d=c$, som ønsket.

Skaleringen må sitte utenat, og den må gjøres. Bézout gir deg alltid $d$ på høyre side — aldri $c$. Er $c=d$, er $k=1$ og skaleringen er usynlig; det er nettopp derfor den glemmes når $c\ne d$.

Kontrollen tar tjue sekunder: sett $(x_0,y_0)$ inn i den opprinnelige likningen og se at du får $c$. Gjør det hver gang.

Tallet $k=c/d$ du ganger Bézout-likningen med.

To ting å merke:

- $k$ er et helt tall — det er nettopp det løsbarhetskriteriet $d\mid c$ garanterer. Får du en brøk her, har du hoppet over løsbarhetssjekken, og likningen har ingen løsning.
- $k$ kan være negativ. Er $c$ negativ, blir $k$ negativ, og partikulærløsningen skifter fortegn. Det er helt i orden — heltallsløsninger har ingen fortegnsrestriksjon med mindre oppgaven sier noe annet.

Den mest belagte feilen i sjanger A er å glemme dette steget: man finner $d=ax'+by'$ riktig, og oppgir $(x',y')$ som svar. Men $(x',y')$ løser likningen $ax+by=d$, ikke $ax+by=c$.

Kontrollen som fanger den: sett svaret inn. Får du $d$ i stedet for $c$, mangler skaleringen — og du er ett multiplikasjonssteg fra riktig svar.

$$x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb{Z}.$$

Fire ting som må stemme, og som hver for seg er en vanlig feil:

1. Fortegnene krysser. $x$ får pluss, $y$ får minus. (Motsatt fungerer også — det svarer til å bytte $t$ mot $-t$ — men samme fortegn på begge er galt.)
2. Koeffisientene bytter plass. $x$ får $b/d$ (det andre tallet), $y$ får $a/d$ (det første). Dette er kryssingen som gjør at leddene kansellerer.
3. Det er $b/d$, ikke $b$. Skrittlengden er delt på $\gcd$. Bruker du $b$, hopper du over $d-1$ av $d$ løsninger.
4. $t$ løper over alle hele tall, også de negative. Skriv $t\in\mathbb{Z}$ eksplisitt.

Kontrollen som fanger alle fire: sett inn og se at $t$ faller ut. Gjør den til rutine — det tar tjue sekunder, og alternativet er et svar som er systematisk galt.

Utledningen utledes på stedet, i to linjer: for at et skritt $\Delta x$ i $x$ skal kunne kompenseres av et helt skritt $\Delta y$ i $y$, må $a\Delta x=-b\Delta y$. Det minste positive $\Delta x$ som gjør høyresiden delelig med $a$, er $\Delta x=b/d$ — og da er $\Delta y=-a/d$. Med $\Delta x=b$ ville $\Delta y=-a$, som også virker, men det er $d$ ganger for langt skritt.

Konkret hva feilen koster. For $803x+154y=44$ er $d=11$, og skrittlengden er $154/11=14$. Løsningene i $x$ er
$$\dots,-8,\ 6,\ 20,\ 34,\ 48,\dots$$
Bruker du $b=154$ i stedet, får du bare $\dots,20,174,\dots$ — altså 1 av 11 løsninger. Du har mistet ti elleventedeler av svaret, og med dem «minste positive», som var $6$.

Merk sammenhengen: $\displaystyle a\cdot\frac bd=\operatorname{lcm}(a,b)$. Skrittet er altså nøyaktig så langt at begge ledd flytter seg et helt multiplum av det minste felles multiplum.

1. Skriv løsningsmengden $\displaystyle x=x_0+\frac bd t$.
2. Krev $x\ge 1$ og løs for $t$:
$$t\ \ge\ \frac{1-x_0}{b/d}\qquad\text{(snu ulikheten hvis }b/d<0).$$
3. Velg det minste hele tallet $t$ som oppfyller ulikheten — altså rund oppover.
4. Regn ut både $x$ og $y$ for den $t$-en, og kontroller ved innsetting.

Prosedyren må sitte utenat, og steg 4 er ikke valgfritt: et «minste positive»-svar uten kontroll er lett å ta feil av med én skrittlengde.

Merk forskjellen på «positiv» og «ikke-negativ». «Minste positive» betyr $x\ge 1$. Er $x=0$ tillatt, sier oppgaven «ikke-negativ» eller «minste $x\ge 0$». Les nøye — de gir forskjellige svar når $x_0$ er et multiplum av skrittlengden.

Og merk at svaret skal skrives ut som en setning. «Minste positive $x$ er $6$, med tilhørende $y=-31$.» Fasitene i arkivet peker eksplisitt på dette svaret; det er et eget delpunkt.

Varianten der oppgaven begrenser $x$ eller $y$ til et intervall — «finn alle løsninger med $0<y<200$», eller «hvor mange løsninger har begge koordinater positive?»

Prosedyren er den samme som for «minste positive», men med to ulikheter:

1. Sett inn parametriseringen i begge grensene.
2. Løs den doble ulikheten for $t$.
3. Tell de hele tallene $t$ i intervallet du får — det er antall løsninger.
4. List dem opp hvis oppgaven ber om det, med kontroll på minst én.

Fellen å unngå: å telle feil i endepunktene. Er intervallet $0<y<200$ (strengt), skal $t$-verdier som gir $y=0$ eller $y=200$ ikke med. Er det $0\le y\le 200$, skal de med. Skriv ut hvilke $t$ du inkluderer og hvorfor.

Typisk «frimerke»-form: krav om at begge er ikke-negative. Da får du to ulikheter — én fra $x\ge 0$ og én fra $y\ge 0$ — og svaret er $t$-ene som oppfyller begge. Ofte er det ingen, og det er et fullgodt svar så lenge du viser at intervallet er tomt.

Oppgavetypen: koeffisientene inneholder en ukjent $n$, og du skal vise at likningen er løsbar for alle hele tall $n$ — og gjerne finne løsningen.

Prosedyren, i tre skritt:

1. Vis at $\gcd=1$ ved å presentere $1$ som en eksplisitt lineærkombinasjon av de to uttrykkene. Velg multiplikatorene slik at $n$-leddene kanselleres.
2. Konkludér løsbarhet: siden $\gcd=1$ deler enhver høyreside, er likningen løsbar for alle $c$ — etter løsbarhetskriteriet.
3. Skalér lineærkombinasjonen med $c$ for å få en partikulærløsning, og skriv løsningsmengden med $b$ og $a$ (nå uttrykk i $n$) som skrittlengder. Siden $d=1$, er skrittlengdene $b$ og $a$ selv.

Hvorfor dette er den eneste veien: her er tallene ikke tall. Det finnes ingenting å faktorisere, ingen divisjonskjede å kjøre, ingen prøvedivisjon som gir mening. Bézout-formen «$\gcd=1$ nøyaktig når $ax+by=1$ har løsning» er den ene karakteriseringen som tåler en ukjent.

Merk at svaret nå inneholder $n$. Både partikulærløsningen og skrittlengdene er uttrykk i $n$, og det er riktig — du har løst uendelig mange likninger på én gang.

Kapitlets samlede prosedyre, i den rekkefølgen fasitene i arkivet fører den:

1. Euklid frem: regn $d=\gcd(a,b)$ med divisjonskjeden.
2. Løsbarhet: sjekk og kommentér at $d\mid c$. Er $d\nmid c$: konkludér «ingen heltallsløsninger» og stopp.
3. Euklid baklengs: finn $x',y'$ med $ax'+by'=d$.
4. Skalér med $k=c/d$: $x_0=kx'$, $y_0=ky'$.
5. Hele løsningsmengden: $\displaystyle x=x_0+\frac bd t$, $\displaystyle y=y_0-\frac ad t$, $t\in\mathbb{Z}$.
6. Svar «minste positive» eksplisitt hvis det spørres, med både $x$ og $y$ og en kontroll.

Oppskriften må sitte utenat. Steg 2 og steg 6 er de som glemmes, og begge er egne føringspoeng.

Legg til kontroll to steder: etter steg 4 (sett $(x_0,y_0)$ inn, få $c$) og etter steg 5 (sett parametriseringen inn, se at $t$ faller ut). Til sammen førti sekunder, og de fanger nesten alle feilene i listen over «Typiske feil».

To ord som skiller de to typene svar, og som oppgaveteksten bruker presist.

Partikulær løsning: ett tallpar $(x_0,y_0)$ som oppfyller likningen. Oppgaveformuleringer: «finn en heltallsløsning», «vis at likningen har en løsning».

Generell løsning: hele mengden, med parameter. Oppgaveformuleringer: «finn samtlige heltallsløsninger», «angi den generelle løsningen», «finn alle løsninger».

Regelen for føring: oppgir oppgaven «samtlige» eller «generell», skal $t\in\mathbb{Z}$ stå i svaret. Er du i tvil, gi den generelle — den inneholder den partikulære, og et for fullstendig svar taper ingenting.

Merk at partikulærløsningen ikke er entydig. Din $(x_0,y_0)$ kan avvike fra løsningsforslagets og likevel være riktig — de skiller seg med et multiplum av skrittlengdene. Kontrollen ved innsetting er det som avgjør.

Likningen $ax+by=c$ beskriver en rett linje i planet. De diofantiske løsningene er punktene på linja med heltallskoordinater — gitterpunktene den treffer.

Bildet forklarer tre ting på én gang:

- Løsningene ligger jevnt fordelt. Skrittet fra ett gitterpunkt til det neste er alltid $(b/d,\,-a/d)$ — samme vektor hver gang. Derfor er svaret en parametrisering med én parameter.
- Antallet er null eller uendelig. Treffer linja ett gitterpunkt, treffer den uendelig mange (gå i begge retninger). Treffer den ingen, treffer den aldri noe. Et endelig antall større enn null er umulig.
- Intervallvarianten er et linjestykke. «Alle løsninger med $0\le x\le 100$» er gitterpunktene på et avgrenset stykke av linja — derfor blir svaret et endelig antall, og derfor teller du hele tall $t$ i et intervall.

Vektoren $(b/d,-a/d)$ er retningsvektoren til linja, skalert ned til det korteste heltallsskrittet. Det er derfor $d$ står i nevneren.

Metoden: to ulikheter, én fra hver koordinat, og du finner de $t$ som oppfyller begge.

$$x_0+\frac bd t\ge 0\qquad\text{og}\qquad y_0-\frac ad t\ge 0.$$

Den første gir en nedre grense for $t$, den andre en øvre. Svaret er de hele tallene mellom.

Tre mulige utfall, alle fullgode svar:

- Tomt intervall: ingen slik løsning finnes. Vis at grensene krysser, og konkludér.
- Ett helt tall: nøyaktig én løsning.
- Flere: list dem, med kontroll på minst én.

Merk at «har løsninger» og «har ikke-negative løsninger» er to forskjellige spørsmål. En likning kan ha uendelig mange heltallsløsninger og ingen ikke-negative — se eksempel 4. Les oppgaveteksten nøye.

Har du parametriseringen og et intervall for $x$ (eller $y$), er antall løsninger antallet hele tall $t$ i et intervall du regner ut.

Prosedyren:

1. Sett inn parametriseringen i begge grensene, og løs for $t$. Du får $t_{\min}\le t\le t_{\max}$ med (typisk) desimaltall som grenser.
2. Rund innover: nedre grense oppover, øvre grense nedover. Nå har du hele tall.
3. Antallet er $t_{\max}-t_{\min}+1$ — husk å legge til $1$, ellers teller du ett for lite.

De to fellene:

- Å glemme $+1$. Fra $t=2$ til $t=5$ er det fire verdier, ikke tre.
- Å runde feil vei i endepunktene. Er ulikheten streng ($x<100$ og ikke $x\le 100$), skal $t$-verdien som gir $x=100$ ikke med. Skriv ut hvilke $t$ du inkluderer, så ser den som retter at du har tenkt på det.

Kontrollen: regn ut $x$ for både $t_{\min}$ og $t_{\max}$ og sjekk at begge ligger inne i intervallet, og at $t_{\min}-1$ og $t_{\max}+1$ ligger utenfor.

Når du går ett skritt i $t$, endrer venstresiden seg med
$$a\cdot\frac bd-b\cdot\frac ad=\frac{ab}{d}-\frac{ab}{d}=0,$$
og de to leddene som kansellerer, er hver på $\displaystyle \frac{ab}{d}$. Men fra kap. 1.1 er
$$\frac{ab}{\gcd(a,b)}=\operatorname{lcm}(a,b).$$

Altså: hvert skritt flytter $ax$-leddet opp med $\operatorname{lcm}(a,b)$ og $by$-leddet ned med det samme. Det er den minste flyttingen som kan gjøres med hele tall i begge koordinater — og det er derfor $b/d$ og $a/d$ er de riktige skrittlengdene.

Bruk det som kontroll: regn ut $a\cdot(b/d)$ og $b\cdot(a/d)$. De skal være like, og de skal være $\operatorname{lcm}(a,b)$. Er de ikke like, har du delt på feil tall et sted.