Kongruensregning

Introduksjon til kongruenser

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

Gitt <tex>a</tex> og <tex>b</tex> vet vi at det finnes unike <tex>s,r</tex> slik at

<tex>a=bs+r</tex>

Vi kan gi dette notasjonen

<tex>a\equiv r \,(\text{mod}\,b)</tex>

(les: <tex>a</tex> er kongruent med <tex>r</tex> modulo <tex>b</tex>) eller ganske enkelt

<tex>a\equiv r</tex>

dersom <tex>\,(\text{mod}\,b)</tex> er inneforstått.

Elementære egenskaper

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

i) <tex>a\equiv a</tex>

ii) <tex>a\equiv c</tex> hvis og bare hvis <tex>c\equiv a</tex>

iii) Hvis <tex>a\equiv c</tex> og <tex>c\equiv e</tex>, så må <tex>a\equiv e</tex>

Følgelig er kongruens en ekvivalensrelasjon