For et positivt heltall n er to hele tall a og b kongruent modulo n uttrykt som
\(\displaystyle a \equiv b \;(\mod n)\)
hvis a-b er et heltallsmultiplum av n
En 12-timers klokke, deler døgnet inn i to 12-timers perioder og er et eksempel på aritmetikk modulo 12. En gammeldags klokke er en ring med heltall, og 12 er kongruent med både 0 og 12. 0≡12 mod12
Hvis klokken er 6 og ønsker å vite hva klokken er 8 timer seinere er, 6+8=14, så vil klokken være 2
Dette er addisjon modulo 12 hvor en sirkel er delt i n like store deler, for en klokke er n=12. Modulo finner resten etter deling av et heltall med et annet
To tall a og b sies å være kongruent (≡, merk forskjell fra likhetstegnet =) modulo n:
\(\displaystyle a \equiv b (\bmod n) \;\;\; \text{hvis} \;\;a-b=kn\)
for et heltall k. a og b kan også være negative heltall.
Tallene 37 og 57 er kongruente(≡) modulo 10, begge med rest 7 når de deles på 10 og 37-57=-20 som er delelig på 10.
Modulær multiplikativ invers til et heltall a modulo n er et heltall x slik at:
\(\displaystyle a^{-1} \equiv x(\bmod n)\)
Dette er ekvialent med :
\(\displaystyle ax \equiv aa^{-1} \equiv 1(\bmod n)\)
Hvis vi vil finne x for a=3 og n=11, så vil x=4
Kongruens modulo n er en ekvivalensrelasjon og klasseinndeling av heltallene Z, hvor a og b er ekvivalente hvis differansen mellom dem er delelig med n.
Hvis a er et positivt så har vi følgende undergruppe av heltallene Z:
\(\{\dots,-3a, -2a, -a, 0, a, 2a, 3a,\dots \}\)
Det er flere eksempler på bruk av modulær matematikk i tillegg til kryptoalgoritmer e.g. Diffie-Hellman-Merkle og RSA kryptografi.
I IBAN-nummeret (International Bank Account Numbers) som bankene benytter brukes modulo 97 for å beregne kontrollsummen for å finne feil bruk av bankkontonummer.
CAS-nummeret som brukes til å identifisere alle kjemiske stoffer har et unikt sistesiffer for ethvert kjemikalium. Dette beregnes ved å ta siste siffer i de to første delene av CAS-nummeret ganger 1, neste siffer ganger 2, neste siffer ganger 3 osv, som til slutt brukes til å beregne sum modulo 10.
Modulo 7 for å finne ukedag i kalenderen. Modulo 12 i tolvtonemusikk. Modulo 2 i summering av bits, samt moduloregning innen en rekke disipliner økonomi, sosialvitenskap, spillteori og lignende.
Fermats lille teorem
For å teste om et tall er et primtall kan man bruke Fermat´s lille teorem som sier at hvis p er et primtall så vil ap-a, hvor a er et heltall, være et heltallmultippel av p
\(\displaystyle a^p \equiv a (\bmod p)\)
Det sier også at hvis a ikke er delelig på p så tilsvarer dette at ap-1-1 er et heltallmultippel av p:
\(\displaystyle a^{p-1} \equiv 1(\bmod p)\)
Et spesialtilfelle av Fermats lille teorem er at p er et primtall hvis og bare hvis:
\(\displaystyle 2^p \equiv 2(\bmod p)\)
En generalisering er Eulers teorem:
\(a^{\phi(n)}\equiv1(\bmod n)\)