1.4 Lineære kongruenser (ax ≡ b mod m)

$$a\equiv b\pmod m.$$

Tre likeverdige måter å si det samme — og du bør kunne veksle fritt mellom dem, for de brukes til ulike ting:

1. Samme rest: $a$ og $b$ gir samme rest ved divisjon med $m$. (Dette er intuisjonen.)
2. Differansen er delelig: $m\mid(a-b)$. (Dette er formen du bruker i bevis.)
3. Det finnes en $k$: $a=b+km$ for et helt tall $k$. (Dette er formen du regner med.)

Tallet $m$ heter modulusen. Merk at $\pmod m$ hører til hele utsagnet, ikke bare til høyresiden.

Notasjonen er viktig: $a\equiv b\pmod m$ med \equiv og \pmod. Skriv ikke $a=b\pmod m$ — kongruens er ikke likhet, og forskjellen er hele poenget. Og skriv ikke «mod» som ren tekst inne i en formel.

Eksempler: $17\equiv 5\pmod{12}$ (klokka), $-37\equiv 3\pmod{10}$ (se resten for negative tall i kap. 1.1), og $a\equiv 0\pmod m$ betyr nøyaktig at $m\mid a$.

1. Addisjon: $a+c\equiv b+e\pmod m$
2. Subtraksjon: $a-c\equiv b-e\pmod m$
3. Multiplikasjon: $ac\equiv be\pmod m$
4. Potens: $a^n\equiv b^n\pmod m$ for hvert $n\ge 1$

Alle fire må sitte utenat, og de er grunnen til at kongruensregning er praktisk: du kan redusere underveis, når som helst, og aldri arbeide med store tall.

Bevisidéen, som utledes på stedet i én linje: skriv $a=b+km$ og $c=e+lm$. For multiplikasjon:
$$ac=(b+km)(e+lm)=be+m(bl+ke+klm),$$
altså $ac-be$ er delelig med $m$. Regel 4 følger av regel 3 ved gjentakelse (formelt: ved induksjon, som i kap. 6.2).

Praktisk kraft, et eksempel: hva er $37^2\bmod 10$? I stedet for $37^2=1369$ reduserer vi først: $37\equiv 7\pmod{10}$, så $37^2\equiv 7^2=49\equiv 9\pmod{10}$. Under kode D er dette forskjellen mellom regnbart og ikke regnbart, og det er metoden som skaleres opp til $7^{402}$ i kap. 2.1.

Merk hva som IKKE står på listen: divisjon. Se neste kort — det er der hele faget skiller seg fra vanlig algebra.

$$[a]=\{a+km: k\in\mathbb{Z}\}=\{\dots,a-2m,\ a-m,\ a,\ a+m,\ a+2m,\dots\}.$$

Klarspråk: en restklasse er «alle tall som gir samme rest». Modulo $5$ er $[2]=\{\dots,-8,-3,2,7,12,17,\dots\}$ — alle tall som gir rest $2$.

Det avgjørende faktumet: det finnes nøyaktig $m$ restklasser modulo $m$, nemlig $[0],[1],\dots,[m-1]$. Grunnen er divisjonsalgoritmen fra kap. 1.1: hvert tall har nøyaktig én rest $r$ med $0\le r<m$, så hvert tall ligger i nøyaktig én klasse.

Hvorfor det betyr noe her: når vi spør hvor mange løsninger $ax\equiv b\pmod m$ har, mener vi hvor mange restklasser som løser den. Det er et endelig spørsmål, og svaret er et tall mellom $0$ og $m$. Ser vi på enkelttall i stedet, er svaret alltid «uendelig mange eller ingen» — som i kap. 1.3.

Notasjonen $[a]$ brukes når vi vil understreke at vi snakker om hele klassen. I praktisk regning skriver vi bare $x\equiv 9\pmod{116}$, og mener klassen.

Dette er måten løsninger telles i sjanger B, og formuleringen «oppgi alle inkongruente løsninger» er standard i oppgavetekstene.

Hvorfor det er den riktige tellingen: løsningene $9$ og $125$ av $84x\equiv 60\pmod{116}$ er ikke to forskjellige svar — $125=9+116$, så de er samme restklasse, samme informasjon. Skulle vi teller enkelttall, ville vi telt uendelig mange kopier av samme svar.

Konvensjonen for hvordan du oppgir dem: velg representantene i intervallet $0\le x<m$. For $84x\equiv 60\pmod{116}$ er svaret
$$x\equiv 9,\ 38,\ 67,\ 96\pmod{116}$$
— fire tall, alle mellom $0$ og $115$, alle i forskjellige klasser.

Kontrollen at du har talt riktig: antallet skal være $d=\gcd(a,m)$, og de skal ligge $m/d$ fra hverandre. Her: $d=4$, og $38-9=29=116/4$ ✓.

$$a\equiv b\pmod{mn}\iff a\equiv b\pmod m\ \text{ og }\ a\equiv b\pmod n,\qquad\text{når }\gcd(m,n)=1.$$

Retningen «venstre mot høyre» er lett: deler $mn$ differansen $a-b$, gjør $m$ og $n$ det også.

Retningen tilbake krever $\gcd(m,n)=1$, og den følger av resultatet i kap. 1.1, oppgave 10: er $m\mid k$ og $n\mid k$ med $\gcd(m,n)=1$, så $mn\mid k$. Sett $k=a-b$.

Kravet er ikke til å hoppe over. Uten det er påstanden gal: $12\equiv 0\pmod 4$ og $12\equiv 0\pmod 6$, men $12\not\equiv 0\pmod{24}$. Her er $\gcd(4,6)=2\ne 1$.

Hvor den brukes: dette er teoretisk grunnlag for det kinesiske restteoremet (kap. 2.4, 12 av 15 sett), og det er grepet som «rydder» et system der modulene ikke er parvis relativt primiske. Det er også hvordan du splitter en beregning modulo $100$ i én modulo $4$ og én modulo $25$ — en standardteknikk i sjanger E.

$$d\mid b,\qquad\text{der }d=\gcd(a,m).$$

Kriteriet må sitte utenat, og det skal kommenteres i besvarelsen — ikke bare brukes. Fasitene i arkivet skriver det ut som en setning, sammen med antallet: «Siden $d=4$ deler $b=60$, er kongruensen løsbar, og den har $4$ inkongruente løsninger modulo $116$.»

Merk hvilket tall som skal deles. Det er $b$ — høyresiden — ikke $m$ og ikke $a$. Sammenlign med kap. 1.3, der kriteriet var $d\mid c$ med $c$ som høyreside: det er samme regel, siden $ax\equiv b\pmod m$ er likningen $ax-my=b$.

Når kriteriet svikter, er du ferdig. «Kongruensen har ingen løsninger» er et fullstendig svar, og det er verdt full uttelling når begrunnelsen står der. Ikke forsøk å regne videre.

Kontrollen som avslører at du har hoppet over sjekken: blir $b/d$ en brøk når du skal forkorte, var kongruensen uløselig.

De ligger jevnt fordelt med avstand $m/d$:
$$x\equiv x_0,\ x_0+\frac md,\ x_0+2\cdot\frac md,\ \dots,\ x_0+(d-1)\cdot\frac md\pmod m.$$

Dette må sitte utenat, og det er den mest belagte feilen i sjanger B: å finne én løsning og stoppe. Har $d=4$, mangler tre firedeler av svaret.

Kontrollen, i tre deler, som gjør at du aldri tar feil her:

1. Tell. Har du $d$ løsninger? Er $d=3$, skal det stå tre tall.
2. Mål avstanden. Nabo-løsningene skal ligge $m/d$ fra hverandre. For $84x\equiv 60\pmod{116}$: $d=4$, $m/d=29$, og løsningene $9,38,67,96$ ligger $29$ fra hverandre ✓.
3. Sett inn. Alle $d$ skal gi samme rest $b$. Det tar noen sekunder per løsning og er en fullstendig kontroll.

Merk at «alle inkongruente løsninger» og «minste positive løsning» er ulike spørsmål. Det første ber om alle $d$; det andre om den minste blant dem som er positiv. Les oppgaveteksten.

$$\frac ad\,x\equiv\frac bd\ \left(\!\!\!\mod \frac md\right).$$

Alle tre tallene deles: $a$, $b$ og $m$. Det siste er det som glemmes.

Hvorfor du vil gjøre det: etter forkortingen er $\gcd(a/d,\ m/d)=1$, og kongruensen har da nøyaktig én løsning modulo $m/d$. Du har altså gjort en oppgave med $d$ løsninger om til en med én — og den ene finner du med invers.

Hvorfor det er lovlig: etter den generelle forkortingsregelen over, anvendt med $c=d$.

Hva du gjør etterpå: du har nå $x\equiv x_0\pmod{m/d}$, men oppgaven spurte modulo $m$. Løsningene modulo $m$ er
$$x\equiv x_0+k\cdot\frac md\pmod m,\qquad k=0,1,\dots,d-1.$$
Dette siste steget må ikke glemmes — det er det som gjør de $d$ løsningene synlige.

Kontrollen: etter forkortingen skal $\gcd$ av de nye $a$ og $m$ være $1$. Er den ikke det, har du ikke delt med hele $d$.

$$au\equiv 1\pmod m.$$

Vi skriver $u\equiv a^{-1}\pmod m$. Merk at $a^{-1}$ her ikke betyr brøken $1/a$ — det betyr «det tallet som ganget med $a$ gir $1$ modulo $m$», og det er et helt tall.

Eksistensbetingelsen: $a$ har en invers modulo $m$ hvis og bare hvis $\gcd(a,m)=1$.

Begge retninger er korte, og de utledes på stedet:

- Finnes inversen: fra $au\equiv 1\pmod m$ følger $au-1=km$, altså $au-km=1$. Da deler $\gcd(a,m)$ tallet $1$, så $\gcd(a,m)=1$.
- Er $\gcd(a,m)=1$: etter Bézout finnes $x,y$ med $ax+my=1$. Lest modulo $m$: $ax\equiv 1\pmod m$, så $u=x$ er inversen.

Inversen er entydig modulo $m$. Har du to, $u_1$ og $u_2$, gir $au_1\equiv au_2$ og forkorting med $a$ (lovlig, siden $\gcd(a,m)=1$) at $u_1\equiv u_2$.

Merk at $m$ ikke behøver være et primtall. Kravet er bare $\gcd(a,m)=1$. Det er nettopp derfor RSA fungerer, der modulusen alltid er et produkt $pq$ av to primtall.

Slik finner du $a^{-1}$ modulo $m$, når $\gcd(a,m)=1$:

1. Kjør Euklids algoritme på $m$ og $a$ (største først), frem til rest $0$. Sjekk at $\gcd=1$ — ellers finnes ingen invers.
2. Gå baklengs gjennom substitusjonskjeden til du har $1=am\text{-kombinasjon}$, altså $ax+my=1$.
3. Les likningen modulo $m$. Leddet $my$ forsvinner, og du står med $ax\equiv 1\pmod m$.
4. Juster inn i intervallet $0\le u<m$ ved å legge til eller trekke fra $m$.
5. Kontrollér: regn $au$ og se at resten ved divisjon med $m$ er $1$.

Prosedyren må sitte utenat. Selve inversen utledes på stedet — den finnes ikke i noen tabell, og under kode D finnes det heller ingen tabell.

Steg 4 glemmes ofte. Bézout gir gjerne en negativ koeffisient: for $a=21$, $m=29$ får du $-11$, og inversen er $-11+29=18$. Begge er riktige som representanter, men konvensjonen er å oppgi den i $0\le u<m$.

Steg 5 er ikke valgfritt. Det tar tjue sekunder og er en fullstendig kontroll av alt arbeidet i steg 1–4.

Fra $ax\equiv b\pmod m$ med $\gcd(a,m)=1$: gang begge sider med $u=a^{-1}$:
$$\underbrace{ua}_{\equiv\,1}\,x\equiv ub\pmod m,\qquad\text{altså}\qquad x\equiv ub\pmod m.$$

Reduser $ub$ modulo $m$ til slutt, så svaret ligger i $0\le x<m$.

Dette er hele grunnen til at inversen er interessant: den gjør «divisjon» mulig. I vanlig algebra ville vi delt på $a$; her ganger vi med $a^{-1}$, som er samme operasjon uttrykt med bare multiplikasjon.

Merk at dette bare virker når $\gcd(a,m)=1$. Er $d>1$, må du forkorte først (løkke 4), og deretter finne inversen i den forkortede kongruensen — der $\gcd$ er $1$ etter konstruksjon. Det er nøyaktig rekkefølgen i steg 2–4 i eksemplene.