Moduloräkning förklarad

Alla räknar redan modulo: 10 timmar efter klockan 8 är klockan 6, och dagen efter söndag är måndag. Räkning som börjar om från 0 efter n steg visar sig ha en egen fullständig aritmetik, med regler, överraskningar och en central plats i talteorin och i den kryptografi som skyddar internet.

En klocka med tolv positioner numrerade från 0 till 11 och en spiralformad bana som slingrar sig ett varv runt urtavlan från 9 till 2
En klocka med tolv positioner numrerade från 0 till 11 och en spiralformad bana som slingrar sig ett varv runt urtavlan från 9 till 2

Rester och kongruens

Dela a med n och behåll bara resten: det är a mod n, ett tal från 0 till n − 1. 26 mod 7 = 5, eftersom 26 = 3 × 7 + 5. Tal med samma rest beter sig likadant mod n, så vi kallar dem kongruenta: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss införde detta skrivsätt i sin Disquisitiones Arithmeticae från 1801, och det gjorde Fermats och Eulers gamla iakttagelser till en egen aritmetik. På en klocka med n positioner hamnar varje heltal på sin rest; de hela varven glöms bort.

Carl Friedrich Gauss på ett porträtt av Christian Albrecht Jensen från 1840. Han införde kongruensbeteckningen a ≡ b (mod n) i Disquisitiones Arithmeticae från 1801.
Carl Friedrich Gauss på ett porträtt av Christian Albrecht Jensen från 1840. Han införde kongruensbeteckningen a ≡ b (mod n) i Disquisitiones Arithmeticae från 1801.

Addition, subtraktion och multiplikation

De tre vanliga räknesätten fungerar som vanligt, och du får reducera mod n när du vill: resten av en summa är resten av summan av resterna, och detsamma gäller differenser och produkter. För att hitta sista siffran i 37 × 48 multiplicerar du bara de sista siffrorna: 7 × 8 = 56, så den slutar på 6. Det är detta som gör moduloräkning så användbar för datorer: hur stora talen än är, blir mellanvärdena aldrig större än n².

Division kräver en invers

Division är undantaget. 2 × 3 ≡ 2 × 8 (mod 10), eftersom båda är 6 mod 10, men 3 och 8 är olika, så man kan inte bara förkorta bort 2:an. Att dividera med a betyder att multiplicera med dess invers, det tal x för vilket a × x ≡ 1, och den finns precis när a och n saknar gemensam faktor. Den utvidgade euklidiska algoritmen hittar den: den utför Euklides divisionssteg för största gemensamma delaren och håller reda på en faktor i varje steg, så att faktorn är inversen när resten når 1. När n är ett primtal har varje tal utom 0 en invers, och division fungerar alltid.

Potenser, Fermat och Euler

Potenser upprepar sig. Ta potenserna av 3 mod 7: 3, 2, 6, 4, 5, 1, och sedan 3 igen. Längden på den cykeln är ordningen för 3. År 1640 lade Pierre de Fermat märke till att för ett primtal p gäller a^(p − 1) ≡ 1 (mod p) när p inte delar a, så varje ordning delar p − 1. Leonhard Euler bevisade det och utvidgade det till varje n, med p − 1 ersatt av antalet värden som är relativt prima med n. Enorma potenser beräknas med upprepad kvadrering: a, a², a⁴, a⁸ …, var och en kvadraten av den föregående, reducerad mod n, och sedan multiplicerade enligt exponentens binära siffror.

Porträtt av Pierre de Fermat
Porträtt av Pierre de Fermat
Porträtt av Leonhard Euler
Porträtt av Leonhard Euler

Kontrollsiffror och kalendrar

Moduloräkning fångar misstag. Sista siffran i ett ISBN-10 väljs så att en viktad summa av alla tio siffror är en multipel av 11, så varje enskild felaktig siffra och varje byte av två grannar upptäcks. Kortnummer använder Luhn-kontrollen mod 10, och IBAN en kontroll mod 97. Kalendrar går mod 7: veckodagen för vilket datum som helst kan räknas ut med några få rester, och det är så eviga kalendrar och domedagsregeln fungerar.

Kryptografi

Modern kryptografi bygger på modulära potenser som är lätta att beräkna och svåra att vända på. I Diffie–Hellman-nyckelutbytet från 1976 kommer två personer överens om en gemensam hemlighet över en öppen linje genom att utbyta potenser modulo ett stort primtal. RSA, publicerat 1977 av Rivest, Shamir och Adleman, krypterar ett meddelande m som m^e mod n, där n är produkten av två stora primtal, och dekrypterar med en andra exponent d som bara den som känner de två primtalen kan beräkna. I läroboksexemplet är n = 3233 = 61 × 53, e = 17 och d = 413: 65 blir 2790, och 2790 blir 65 igen.

Utforska själv

Öppna den modulära klockan för att beräkna a mod n, summor, differenser, produkter, potenser, inverser och kvoter mod n, för tal med upp till 30 siffror. Varje svar kommer med sina steg: divisionen med rest, potenserna från upprepad kvadrering eller tabellen för den utvidgade euklidiska algoritmen. Klockan ritar hur svaret nås, från spiralen i en addition till potensernas cykel, och för små n visar operationens tabell alla svar på en gång.

Ofta ställda frågor

Vad betyder symbolen ≡?

a ≡ b (mod n) säger att a och b ger samma rest vid division med n, eller, vilket är samma sak, att n delar a − b. 38 ≡ 2 (mod 12), eftersom 38 − 2 = 36 är en multipel av 12.

Är mod samma sak som operatorn % i programmering?

För positiva tal, ja. För negativa tal returnerar många språk, som C, Java och JavaScript, en negativ rest: −7 % 3 är −1 där, medan −7 mod 3 = 2. Pythons % följer den matematiska konventionen för ett positivt n.

Vad är ordningen för ett tal mod n?

Det minsta k > 0 med a^k ≡ 1 (mod n). Den finns bara när a och n saknar gemensam faktor. Ordningen för 2 mod 7 är 3, eftersom 2³ = 8 ≡ 1, och ordningen för 3 mod 7 är 6, så potenserna av 3 går igenom varje rest som inte är noll: 3 är en primitiv rot mod 7.

Vem uppfann moduloräkning?

Rester användes långt tidigare, till exempel i den kinesiska restsatsen från 200- till 400-talet, och av Fermat och Euler. Gauss gjorde det till en systematisk aritmetik, med beteckningen för kongruenser, år 1801.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna den modulära klockan