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) $a\equiv a$

ii) $a\equiv c$

hvis og bare hvis $c\equiv a$

iii) Hvis $a\equiv c$

og $c\equiv e$ , så må $a\equiv e$

Følgelig er kongruens en ekvivalensrelasjon

Regning med kongruenser