Modulær aritmetik forklaret

Alle bruger allerede modulær aritmetik: 10 timer efter klokken 8 er klokken 6, og dagen efter søndag er mandag. Optælling, der starter forfra fra 0 efter n trin, viser sig at have sin egen fuldstændige aritmetik med regler, overraskelser og en central plads i talteorien og i den kryptografi, der beskytter internettet.

Et ur med tolv positioner nummereret fra 0 til 11 og en spiralformet bane, der snor sig én gang rundt om skiven fra 9 til 2
Et ur med tolv positioner nummereret fra 0 til 11 og en spiralformet bane, der snor sig én gang rundt om skiven fra 9 til 2

Rester og kongruens

Divider a med n, og behold kun resten: det er a mod n, et tal fra 0 til n − 1. 26 mod 7 = 5, fordi 26 = 3 × 7 + 5. Tal med samme rest opfører sig ens mod n, så vi kalder dem kongruente: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss indførte denne notation i sin Disquisitiones Arithmeticae fra 1801, og den gjorde Fermats og Eulers gamle iagttagelser til en selvstændig aritmetik. På et ur med n positioner lander hvert helt tal på sin rest; de hele omgange glemmes.

Carl Friedrich Gauss på et portræt af Christian Albrecht Jensen fra 1840. Han indførte kongruensnotationen a ≡ b (mod n) i sine Disquisitiones Arithmeticae fra 1801.
Carl Friedrich Gauss på et portræt af Christian Albrecht Jensen fra 1840. Han indførte kongruensnotationen a ≡ b (mod n) i sine Disquisitiones Arithmeticae fra 1801.

Addition, subtraktion og multiplikation

De tre almindelige regnearter virker som sædvanligt, og du må reducere mod n, når du vil: resten af en sum er resten af summen af resterne, og det samme gælder differenser og produkter. For at finde det sidste ciffer i 37 × 48 multiplicerer du kun de sidste cifre: 7 × 8 = 56, så det ender på 6. Det er det, der gør modulær aritmetik så nyttig for computere: uanset hvor store tallene er, overstiger mellemresultaterne aldrig n².

Division kræver en invers

Division er undtagelsen. 2 × 3 ≡ 2 × 8 (mod 10), da begge er 6 mod 10, men 3 og 8 er forskellige, så man kan ikke bare forkorte 2-tallet væk. At dividere med a betyder at multiplicere med dens inverse, det tal x, for hvilket a × x ≡ 1, og den findes netop, når a og n ingen fælles faktor har. Den udvidede euklidiske algoritme finder den: den udfører Euklids divisionstrin for den største fælles divisor og holder styr på en faktor ved hvert trin, så når resten når 1, er faktoren den inverse. Når n er et primtal, har alle tal undtagen 0 en invers, og division virker altid.

Potenser, Fermat og Euler

Potenser gentager sig. Tag potenserne af 3 mod 7: 3, 2, 6, 4, 5, 1, og så 3 igen. Længden af den cyklus er ordenen af 3. I 1640 bemærkede Pierre de Fermat, at der for et primtal p gælder a^(p − 1) ≡ 1 (mod p), når p ikke går op i a, så enhver orden går op i p − 1. Leonhard Euler beviste det og udvidede det til ethvert n, hvor p − 1 erstattes af antallet af værdier, der er indbyrdes primiske med n. Enorme potenser udregnes ved gentagen kvadrering: a, a², a⁴, a⁸ …, hver kvadratet af den foregående, reduceret mod n, og derefter multipliceret efter eksponentens binære cifre.

Portræt af Pierre de Fermat
Portræt af Pierre de Fermat
Portræt af Leonhard Euler
Portræt af Leonhard Euler

Kontrolcifre og kalendere

Modulær aritmetik fanger fejl. Det sidste ciffer i et ISBN-10 vælges, så en vægtet sum af alle ti cifre er et multiplum af 11, så ethvert enkelt forkert ciffer og enhver ombytning af to naboer opdages. Betalingskortnumre bruger Luhn-kontrollen mod 10 og IBAN-numre en kontrol mod 97. Kalendere går mod 7: ugedagen for enhver dato kan regnes ud med nogle få rester, og sådan virker evighedskalendere og dommedagsreglen.

Kryptografi

Moderne kryptografi bygger på modulære potenser, der er lette at udregne og svære at gøre om. I Diffie–Hellman-nøgleudvekslingen fra 1976 bliver to personer enige om en fælles hemmelighed over en åben linje ved at udveksle potenser modulo et stort primtal. RSA, offentliggjort i 1977 af Rivest, Shamir og Adleman, krypterer en meddelelse m som m^e mod n, hvor n er produktet af to store primtal, og dekrypterer med en anden eksponent d, som kun den, der kender de to primtal, kan udregne. I lærebogseksemplet er n = 3233 = 61 × 53, e = 17 og d = 413: 65 bliver til 2790, og 2790 bliver til 65 igen.

Udforsk det selv

Åbn det modulære ur for at udregne a mod n, summer, differenser, produkter, potenser, inverse og kvotienter mod n for tal med op til 30 cifre. Hvert svar kommer med sine trin: divisionen med rest, potenserne fra gentagen kvadrering eller tabellen fra den udvidede euklidiske algoritme. Uret tegner, hvordan svaret nås, fra spiralen ved en addition til potensernes cyklus, og for små n viser tabellen for operationen alle svarene på én gang.

Ofte stillede spørgsmål

Hvad betyder symbolet ≡?

a ≡ b (mod n) siger, at a og b giver samme rest ved division med n, eller, hvad der er det samme, at n går op i a − b. 38 ≡ 2 (mod 12), fordi 38 − 2 = 36 er et multiplum af 12.

Er mod det samme som operatoren % i programmering?

For positive tal, ja. For negative tal returnerer mange sprog, såsom C, Java og JavaScript, en negativ rest: −7 % 3 er −1 dér, mens −7 mod 3 = 2. Pythons % følger den matematiske konvention for et positivt n.

Hvad er ordenen af et tal mod n?

Det mindste k > 0 med a^k ≡ 1 (mod n). Den findes kun, når a og n ingen fælles faktor har. Ordenen af 2 mod 7 er 3, fordi 2³ = 8 ≡ 1, og ordenen af 3 mod 7 er 6, så potenserne af 3 gennemløber alle rester forskellige fra nul: 3 er en primitiv rod mod 7.

Hvem opfandt modulær aritmetik?

Rester blev brugt længe før, for eksempel i den kinesiske restsætning fra det 3. til 5. århundrede og af Fermat og Euler. Gauss gjorde det til en systematisk aritmetik med notationen for kongruenser i 1801.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn det modulære ur