Modulær aritmetikk (kongruensregning)
Modulær aritmetikk er regning med rester som oppstår ved divisjon. Når 17 deles på 5, blir svaret 3 med rest 2, så 17 mod 5 = 2. Dette systemet brukes i kryptografi, datamaskiner og hverdagslige situasjoner som klokkeregning og kalendere.
Bakgrunn
Modulær aritmetikk ligger til grunn for moderne kryptografi som beskytter nettbank og digitale betalinger. Bankkortnummer bruker Luhn-algoritmen med modulo 10 for å oppdage inntastingsfeil. Datamaskiner bruker modulo 2-regning i binære operasjoner for alt fra grafikk til internettprotokoll. I hverdagen møter vi modulær aritmetikk når vi regner med ukedager (7 dager i uken), månedsregnskap (28-31 dager) eller når 24-timers klokka går fra 23:59 til 00:00. Programmerere bruker hash-tabeller med modulær aritmetikk for rask datalagring. ISBN-koder på bøker bruker modulo 11 for å verifisere riktige tall. På høyere nivå innen matematikk dukker modulær aritmetikk opp i tallteori, algebra og diskret matematikk.
Slik løser du modulær aritmetikk (kongruensregning)
Modulær aritmetikk (kongruensregning)
- a mod n er resten når a deles på n: a = n·q + r med 0 ≤ r < n.
- a ≡ b (mod n) betyr at (a − b) er et multiplum av n — ekvivalent: a og b gir samme rest ved divisjon med n.
- Addisjon og multiplikasjon respekterer kongruens: (a + b) mod n og (a · b) mod n kan regnes ut ved først å redusere hver del mod n.
- For å løse ax ≡ b (mod n) når gcd(a, n) = 1, multipliser begge sider med den modulære inversen til a.
Example: 17 mod 5 = 2 (siden 17 = 3·5 + 2). Og 17 ≡ 2 (mod 5) fordi 17 − 2 = 15 er et multiplum av 5.
Eksempler
Regn ut 19 mod 3.
Svar: 1
- Finn det største multiplumet av 3 som er ≤ 19 → 3 × 6 = 18 — Vi vil ha det største tallet på formen 3·k som ikke er større enn 19. Deler vi, blir 19 : 3 = 6 med noe til rest, så 3·6 = 18.
- Trekk fra for å finne resten → 19 − 18 = 1 — Resten er det som er igjen etter å ha trukket fra multiplumet: 19 − 18 = 1.
- Skriv svaret → 19 mod 3 = 1 — Altså 19 mod 3 = 1 (siden 19 = 3·6 + 1).
Er 49 ≡ 5 (mod 11)?
Svar: yes
- Regn ut differansen a − b → 49 − 5 = 44 — To tall er kongruente mod n nettopp når differansen deres er et multiplum av n. Vi regner 49 − 5 = 44.
- Sjekk om 44 er delelig med 11 → 44 = 11 · 4 — Deler vi: 44 : 11 = 4 rest 0. Resten er 0, så differansen er et multiplum av n.
- Svar → Yes — 49 ≡ 5 (mod 11) — Ja: siden 44 er et multiplum av 11, er 49 ≡ 5 (mod 11).
Regn ut (27 + 18) mod 5.
Svar: 0
- Regn ut summen først → 27 + 18 = 45 — Gjør utregningen inni først: 27 + 18 = 45.
- Reduser 45 modulo 5 → 45 = 5 · 9 + 0 — Del 45 på 5: 45 : 5 = 9 rest 0. Det er resten vi beholder.
- Skriv svaret → (27 + 18) mod 5 = 0 — Altså (27 + 18) mod 5 = 45 mod 5 = 0.
Vanlige feil
- En vanlig feil er å tro at 17 mod 5 = 3,4 i stedet for 2, ved å blande sammen divisjon og modulær aritmetikk.
- Mange regner feil ved å si at 23 ≡ 8 (mod 6) fordi 23 - 8 = 15, men glemmer å sjekke at 15 faktisk er delelig med 6 (15 = 6 × 2,5 gir ikke heltall).
- Ved modulær addisjon regnes ofte (14 + 17) mod 5 som 14 mod 5 + 17 mod 5 = 4 + 2 = 6, men glemmer at 6 mod 5 = 1 er det endelige svaret.