Kongruensregning

Introduksjon til kongruenser

Anta at alle størrelser er heltall med mindre annet er spesifisert.

Gitt $a$ og $b$ vet vi at det finnes unike $s,r$ slik at

$a=bs+r$

Vi kan gi dette notasjonen

$a\equiv r(\text{mod}b)$

(les: $a$ er kongruent med $r$ modulo $b$) eller ganske enkelt

$a\equiv r$

dersom $(\text{mod}b)$ er inneforstått.

Elementære egenskaper

For det første er det åpenbart at hvis $a=c+bd$, så er $a\equiv c(\text{mod}b)$. Følgelig har vi at

i) Refleksiv egenskap: $a\equiv a$

ii) Symmetrisk egenskap: $a\equiv c$ hvis og bare hvis $c\equiv a$

iii) Transitiv egenskap: Hvis $a\equiv c$ og $c\equiv e$, så må $a\equiv e$

Følgelig er kongruens en ekvivalensrelasjon