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$

<embedvideo service="https://www.youtube.com/watch?v=6kQpwp6SC8I&amp;list=PLU9Gs7tAVUEWCM-d20Hg0qKY00Wq_okNF&amp;index=52" </embedvideo>

Følgelig er kongruens en ekvivalensrelasjon