1.2 Euklids algoritme frem og baklengs (Bézout)

Oppskriften, med $a>b>0$:

1. Del $a$ på $b$: $a=q_1b+r_1$ med $0\le r_1<b$.
2. Er $r_1=0$, er $\gcd(a,b)=b$, og du er ferdig.
3. Ellers gjentar du med det forrige tallet du delte på og resten: del $b$ på $r_1$.
4. Fortsett slik til resten blir $0$. Den siste resten som ikke var $0$, er $\gcd(a,b)$.

Med symboler er dette divisjonskjeden
$$r_{k-1}=q_{k+1}r_k+r_{k+1},\qquad 0\le r_{k+1}<r_k.$$

Prosedyren må sitte utenat. Det er det tallmessige håndverket i 15 av 15 eksamenssett, og under kode D har du ingen alternativ metode for tall i denne størrelsesordenen.

Den vanligste feilen i steg 3: å dele det opprinnelige $a$ på den nye resten. Du skal alltid dele divisoren fra forrige linje på resten fra forrige linje. Tallene flytter seg ett hakk til venstre for hver linje.

$$a=q_1b+r_1,\quad b=q_2r_1+r_2,\quad r_1=q_3r_2+r_3,\quad\dots,\quad r_{k-1}=q_{k+1}r_k+0.$$

Legg merke til mønsteret, for det er den beste kontrollen du har mens du regner: hvert tall opptrer to ganger nedover kjeden — først som rest, så som divisor, så som dividend. Bryter mønsteret, har du gjort en avskrivningsfeil.

Restene $r_1>r_2>r_3>\dots$ er strengt avtakende og ikke-negative, siden hver rest er mindre enn divisoren den kom fra ($0\le r<b$ i divisjonsalgoritmen). Derfor må kjeden nå $0$ etter endelig mange steg.

Kjeden er også arbeidsmaterialet for baklengs-halvdelen. Ikke visk den ut når du har funnet $\gcd$ — du trenger hver linje igjen om et øyeblikk.

$$b>r_1>r_2>\dots\ge 0.$$

En slik følge kan ikke være uendelig — det finnes bare endelig mange hele tall mellom $0$ og $b$. Altså blir en rest $0$ etter endelig mange steg, og algoritmen stopper.

Dette er utledes på stedet og tar én linje å si, men det er ikke bare formalisme: det er argumentet for at prosedyren er en algoritme og ikke bare et forsøk.

Hvor rask er den? Verste tilfelle er nabotall i Fibonacci-følgen, og selv da vokser antall linjer bare som logaritmen av tallene. Praktisk konsekvens for eksamen: for firesifrede tall får du typisk 4–6 divisjonslinjer. Er kjeden din på tolv linjer, har du sannsynligvis regnet feil et sted — det er en gratis kontroll.

Dette er stedet folk leser av feil tall under tidspress. Kjeden ender slik:

$$\dots,\qquad r_{k-1}=q\cdot r_k+0.$$

Her er svaret $r_k$ — divisoren i den siste linja, som samtidig er resten i linja over. Det er ikke $r_{k-1}$, og det er ikke $0$.

Kontrollen tar fem sekunder og bør gjøres hver gang: sjekk at tallet ditt deler begge de opprinnelige tallene. Får du $\gcd(803,154)=11$, sjekk at $803=11\cdot 73$ og $154=11\cdot 14$. Stemmer begge, er $\gcd$ i hvert fall en felles divisor — og Euklids algoritme garanterer at den er den største.

For hvert positivt helt tall $a$ er $\gcd(a,0)=a$.

Grunnen: hvert tall deler $0$, siden $0=a\cdot 0$. Så divisorene i $0$ er alle tall, og de felles divisorene i $a$ og $0$ er nettopp divisorene i $a$. Den største av dem er $a$ selv.

Dette er ikke en kuriositet — det er sluttsteget i Euklids algoritme. Når kjeden når $r_{k-1}=q\cdot r_k+0$, er du i praksis kommet til paret $(r_k,0)$, og nøkkellemmaet pluss dette kortet gir at svaret er $r_k$.

Merk at $\gcd(0,0)$ ikke er definert: alle tall er felles divisorer, og det finnes ingen største.

Grunnen er at $\gcd$ ikke ser fortegn:
$$\gcd(a,b)=\gcd(|a|,|b|),$$
siden $d\mid a$ nøyaktig når $d\mid(-a)$.

Trenger du Bézout-koeffisienter for negative tall, regner du med absoluttverdiene og snur fortegnet på koeffisienten til slutt. Har du funnet $\gcd(803,154)=803\cdot 5+154\cdot(-26)$, så er
$$\gcd(-803,154)=11=(-803)\cdot(-5)+154\cdot(-26).$$

Praktisk råd: gjør dette som første linje i besvarelsen, ikke underveis. «Siden $\gcd(a,b)=\gcd(|a|,|b|)$, regner vi med positive tall» — én setning, og du har fjernet en fortegnsfelle fra hele resten av oppgaven.

Oppskriften:

1. Gå til den nest siste linja i kjeden — den der resten er $\gcd$. Løs den for $\gcd$:
$$\gcd = r_{k-2}-q_k\cdot r_{k-1}.$$
2. Ta linja over, løs den for sin rest, og sett uttrykket inn.
3. Trekk sammen, men bare de to tallene som nå står der — ikke regn ut produktene.
4. Gjenta oppover til bare $a$ og $b$ står igjen.

Prosedyren må sitte utenat. Koeffisientene den produserer, gjør det ikke — de utledes på stedet, for hvert nytt tallpar.

Det ene rådet som forhindrer flest feil: ikke gang ut tallene. Står det $5\cdot 33$, la det stå som $5\cdot 33$ til slutt. Ganger du ut til $165$, mister du sporet av hvilket tall som skal substitueres neste gang, og da er kjeden ødelagt. Mange skriver derfor de to «aktive» tallene i en boks eller understreket for hver linje.

$$A=q\cdot B+r$$

løses for resten:

$$r=A-q\cdot B.$$

Det er alt. Skrittet baklengs består i å bytte ut ett tall (resten $r$) med to (dividenden $A$ og divisoren $B$), og hver gang du gjør det, klatrer du én linje oppover i kjeden.

Bokføringen: etter hvert steg står $\gcd$ som en kombinasjon av nøyaktig to tall fra kjeden, og de to tallene ligger alltid ved siden av hverandre i kjeden. Er du i tvil om du har gjort det riktig, sjekk at du har to og ikke tre.

Kontrollen underveis (verdt de ti sekundene på et langt tallpar): regn ut uttrykket ditt numerisk etter hvert steg. Det skal alltid gi $\gcd$. Får du noe annet, ligger feilen i det siste steget, og ikke tolv linjer tilbake.

Slik føres hver Euklid-oppgave i boka, og slik bør du føre den på eksamen. Malen er identisk i alle kapitler der Euklids algoritme brukes.

(i) Divisjonskjeden frem. Divisjonene linje for linje til rest $0$, med siste ikke-null rest identifisert som $\gcd$.

(ii) Substitusjonskjeden baklengs. Fra nest siste linje og oppover, eksplisitt, til $\gcd(a,b)=ax+by$.

(iii) Konklusjonssetning. «Altså er $\gcd(a,b)=d=a\cdot x+b\cdot y$» — skrevet ut som en setning, med tall.

Malen må sitte utenat, og hvert av de tre stegene bærer uttelling for seg selv. Grunnen er instruksen som står på hvert eneste sett: alle svar må begrunnes. Et riktig $\gcd$ uten kjeden er et sluttall uten metode, og koeffisienter uten kjeden er ikke etterprøvbare.

Legg til kontrollen. Sett koeffisientene inn i $ax+by$ og se at du får $d$. Det tar tjue sekunder, og det er den eneste feilen i dette stoffet du kan oppdage helt sikkert selv.

De utledes på stedet, alltid — de finnes ikke i noen tabell, og under kode D finnes det heller ikke noen tabell. Substitusjonskjeden er den ene måten du får dem.

De er ikke entydige. Har du funnet ett par, får du uendelig mange andre ved å flytte langs
$$x'=x+\frac{b}{d}t,\qquad y'=y-\frac{a}{d}t,\qquad t\in\mathbb{Z}.$$
Kontroll: $\displaystyle ax'+by'=ax+by+\frac{ab}{d}t-\frac{ab}{d}t=d$, som før.

Praktisk betydning for eksamen: fasiten din kan ha andre koeffisienter enn løsningsforslaget og fortsatt være riktig. Det som avgjør, er at innsettingen stemmer. Kontroller derfor alltid ved innsetting — da vet du at du er trygg selv om tallene ser annerledes ut enn du forventet.

Dette er også nøkkelen til hele løsningsmengden i kap. 1.3: parametriseringen over er den samme formelen som gir alle løsninger av en diofantisk likning.

$$ax+by=1.$$

Begge retninger er korte. Er $\gcd(a,b)=1$, gir Bézout slike $x,y$. Og finnes det slike $x,y$, må $\gcd(a,b)$ dele $1$ etter lineærkombinasjonsregelen, altså være $1$.

Dette er den mest brukte formen av Bézout på eksamen, og grunnen er praktisk: å vise at to tall er relativt primiske krever ellers at du utelukker alle felles primfaktorer. Med Bézout holder det å presentere én lineærkombinasjon som gir $1$ — og det er en enkelt likning å skrive ned.

Dette er nøyaktig grepet i parameter-i-koeffisient-varianten i løkke 6, der tallene ikke er tall men uttrykk i en ukjent $n$, og faktorisering derfor ikke er en mulighet i det hele tatt.

I substitusjonskjeden veksler fortegnene systematisk, og det gir en kontroll som er verdt å kunne.

Regelen: når $\gcd(a,b)$ er mindre enn både $a$ og $b$, har de to koeffisientene motsatt fortegn. Den ene er positiv, den andre negativ.

Grunnen er en størrelsesbetraktning: skal $ax+by$ bli et lite positivt tall mens $a$ og $b$ er store, må de to leddene nesten kansellere hverandre. To positive ledd gir minst $a+b$; to negative gir noe negativt.

Bruk den som kontroll. Får du to positive koeffisienter på et par der $\gcd$ er lite, har du regnet feil — sannsynligvis mistet et minustegn i en substitusjon.

Ser du på eksemplene i kapitlet, stemmer mønsteret hver gang: $(5,-26)$ for $(803,154)$, $(13,-32)$ for $(897,364)$, $(-13,32)$ for $(1729,703)$, $(-13,30)$ for $(2431,1054)$.

Oppsettet. Lag en tabell med kolonnene $r$ (rest), $q$ (kvotient), $x$ og $y$. Start med to rader:

Invarianten som gjør det riktig: i hver rad gjelder $ax+by=r$. Det er en gratis kontroll — velg en rad, sett inn, og se at det stemmer.

Bruk: vis den gjerne som tillegg, eller bruk den til å kontrollere baklengs-kjeden din. Men før alltid substitusjonskjeden også — det er den som er føringsstandarden i dette emnet.

Metoden: finn hele tall $u$ og $v$ (som ikke avhenger av $n$) slik at
$$u\cdot(\text{første uttrykk})+v\cdot(\text{andre uttrykk})=1.$$
Da er $\gcd=1$ for alle $n$, etter Bézout — eller mer direkte: enhver felles divisor deler venstresiden, altså deler den $1$.

Slik finner du $u$ og $v$: velg dem slik at $n$-leddene kanselleres. Er uttrykkene $an+b$ og $cn+d$, skal $u\cdot a+v\cdot c=0$, så $u=c$ og $v=-a$ er det naturlige forsøket. Regn deretter ut hva konstantleddet blir, og skaler om det ikke ble $\pm 1$.

Hvorfor dette er den eneste veien: her er tallene ikke tall. Det finnes ingenting å faktorisere og ingen divisjonskjede å kjøre. Bézout-formen er den ene karakteriseringen av «relativt primisk» som tåler en ukjent — og det er derfor kortet «Relativt primisk, sett gjennom Bézout» er verdt å ha sittende.

Fortegnet betyr ingenting. Ender du med $-1$ i stedet for $1$, gang hele likningen med $-1$. En felles divisor som deler $-1$, deler også $1$.

Med denne notasjonen er kjeden
$$r_{k-1}=q_{k+1}r_k+r_{k+1},$$
og algoritmen stopper når $r_{k+1}=0$, med $\gcd=r_k$.

Hvorfor notasjonen er verdt å kjenne: den brukes i kjedebrøk-kapitlet (kap. 7.1), der de samme kvotientene $q_1,q_2,\dots$ viser seg å være nøyaktig leddene i kjedebrøkutviklingen. Euklids algoritme og kjedebrøk er samme regning sett på to måter.

I praktisk føring på eksamen trenger du ikke indeksene — skriv tallene. Notasjonen er for teoriens skyld.

$$\{ax+by: x,y\in\mathbb{Z}\}=\{k\cdot\gcd(a,b): k\in\mathbb{Z}\}.$$

Begge inklusjoner er korte. Hver lineærkombinasjon er delelig med $\gcd(a,b)$, etter lineærkombinasjonsregelen. Og hvert multiplum $k\cdot\gcd(a,b)$ nås ved å skalere Bézout-likningen med $k$.

Dette er den setningen som gir løsbarhetskriteriet i kap. 1.3: likningen $ax+by=c$ har heltallsløsninger nøyaktig når $c$ ligger i denne mengden, altså når $\gcd(a,b)\mid c$. Hele sjanger A hviler på denne ene observasjonen.

Begge metodene finner $\gcd$. Valget mellom dem er praktisk, og under kode D er det avgjort.

$$ax+by\ \overset{?}{=}\ \gcd(a,b).$$

Gjør dette hver gang. Det tar tjue sekunder, det krever ingen ny innsikt, og det fanger nøyaktig den feiltypen du ellers ikke oppdager — et mistet fortegn eller en gal sammentrekning midt i substitusjonskjeden.

To ting til å kontrollere samtidig, som er like billige:

- Deler $\gcd$-en din begge de opprinnelige tallene? Hvis ikke, ligger feilen i divisjonskjeden, ikke i substitusjonene.
- Har koeffisientene motsatt fortegn? Når $\gcd$ er lite i forhold til $a$ og $b$, skal de ha det.

Under kode D er selvkontroll den eneste kontrollen du har. Det er ikke noe å slå opp i og ingen fasit å sammenligne med — så kontrollrutinene er en del av ferdigheten, ikke et tillegg til den.

Har du $\gcd(a,m)=1$ og Bézout-likningen

$$ax+my=1,$$

les den modulo $m$. Leddet $my$ er et multiplum av $m$ og forsvinner:

$$ax\equiv 1\pmod m.$$

Altså er $x$ inversen til $a$ modulo $m$. Ligger $x$ utenfor $0\le x<m$, legg til eller trekk fra $m$ til den er inne — det endrer ikke restklassen.

Dette er hele metoden, og det er derfor kapitlet er en forutsetning for kap. 1.4 og for RSA i kap. 3.1. Legg merke til at kravet er $\gcd(a,m)=1$ og ingenting mer: modulusen behøver ikke være et primtall.

Vi bruker grepet i eksempel 3 og i oppgave 4.

Et føringskort, ikke et fagkort — men det er verdt en plass i bunken, fordi det er den dyreste vanen å ikke ha.

Regelen: når en oppgave nevner Euklids algoritme, forventes både $\gcd$ og veien dit, frem og baklengs. Grunnlaget er instruksen på hvert sett — alle svar må begrunnes — sammen med fasitpraksisen i arkivet, som konsekvent skriver ut begge kjedene.

To grunner til at det ikke er formalisme:

1. Uttelling. Et $\gcd$ uten kjede er et sluttall uten metode, og teller lite. Motsatt: en riktig ført kjede med en regnefeil i siste linje gir betydelig uttelling.
2. Fremdrift. Koeffisientene er det du trenger videre — til løsningsmengden i kap. 1.3, til inversen i kap. 1.4, til $d$ i RSA. Har du dem ikke, stopper oppgaven.

Selvtesten: kan noen som leser besvarelsen din, følge hvert steg fra de to opprinnelige tallene til $\gcd=ax+by$ uten å regne selv? Da er føringen god nok.

Starter du med det minste tallet øverst, ordner første linje det selv. Deler du $154$ på $803$, får du
$$154=0\cdot 803+154,$$
altså kvotient $0$ og resten uendret. Neste linje deler da $803$ på $154$ — og du er i gang som normalt, bare med én tom linje ekstra.

Praktisk råd likevel: sorter. Det koster ingenting, og den tomme linja er en unødvendig kilde til forvirring når du senere skal gå baklengs gjennom kjeden. Skriv det største tallet først, hver gang.

Merk også at $\gcd$ er symmetrisk: $\gcd(a,b)=\gcd(b,a)$. Rekkefølgen påvirker altså bare bokføringen, aldri svaret. Bézout-koeffisientene bytter naturligvis plass med tallene sine.

$$\gcd(a,b)=\gcd(a-b,b).$$

Beviset er det samme argumentet som for nøkkellemmaet: $a-b$ er en lineærkombinasjon av $a$ og $b$, og $a=(a-b)+b$ er en lineærkombinasjon av $a-b$ og $b$, så de to parene har nøyaktig samme felles divisorer.

Faktisk er dette spesialtilfellet $q=1$ av nøkkellemmaet — og divisjonsvarianten er bare «trekk fra $b$ så mange ganger du kan, på én gang».

Når den er nyttig: som argument i bevis, der en enkelt subtraksjon er lettere å skrive enn en divisjon. Vi brukte den formen i kap. 1.1, oppgave 5.

Når den ikke er nyttig: til regning. $\gcd(1000,3)$ ville tatt over 300 subtraksjoner og tar to divisjoner. På eksamen bruker du alltid divisjonsvarianten.

$$\gcd(a,b,c)=\gcd\!\left(\gcd(a,b),\,c\right).$$

Bézout-formen blir tilsvarende: det finnes hele tall $x,y,z$ med
$$\gcd(a,b,c)=ax+by+cz.$$

Slik regner du den ut i praksis, i to runder:

1. Kjør Euklids algoritme på $a$ og $b$: $\gcd(a,b)=au+bv$.
2. Kjør den så på $\gcd(a,b)$ og $c$: $\gcd(a,b,c)=\gcd(a,b)\cdot s+c\cdot t$.
3. Sett inn uttrykket fra runde 1: $\gcd(a,b,c)=a(us)+b(vs)+ct$.

Merk fellen: at tre tall har $\gcd=1$ betyr ikke at de er parvis relativt primiske. $\gcd(6,10,15)=1$, men ingen av de tre parene er relativt primiske. Skillet er avgjørende i det kinesiske restteoremet (kap. 2.4), som krever den parvise egenskapen.

Kjører du algoritmen på $\gcd(55,34)$, blir hver kvotient $1$, og kjeden blir så lang som den kan bli:
$$55=1\cdot 34+21,\quad 34=1\cdot 21+13,\quad 21=1\cdot 13+8,\quad\dots$$
Hver linje flytter deg bare ett hakk nedover i følgen, i stedet for å hoppe.

Konsekvensen er en øvre grense: antall divisjonslinjer vokser bare som logaritmen av tallene. Det er derfor algoritmen er praktisk på store tall, og det er derfor firesifrede tall gir 4–6 linjer — som er nøyaktig hva du møter på eksamen.

Bruk det som kontroll: blir kjeden din uventet lang, og alle kvotientene er $1$, er tallene Fibonacci-lignende. Blir den lang med varierende kvotienter, har du sannsynligvis regnet feil.

Fibonacci-tallene dukker opp igjen i kap. 6.2, der identiteter om dem bevises ved induksjon (sjanger J), og i kap. 7.1, der de er konvergent-nevnerne til den enkleste kjedebrøken.