Kongruensregning

Introduksjon til kongruenser

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

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

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

Vi kan gi dette notasjonen

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

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

<math>a\equiv r</math>

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

Elementære egenskaper

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

i) Refleksiv egenskap: <math>a\equiv a</math>

ii) Symmetrisk egenskap: <math>a\equiv c</math> hvis og bare hvis <math>c\equiv a</math>

iii) Transitiv egenskap: Hvis <math>a\equiv c</math> og <math>c\equiv e</math>, så må <math>a\equiv e</math>

<iframe width="560" height="315" src="https://www.youtube.com/embed/6kQpwp6SC8I?si=swuj6p_WA46aQgcl&amp;controls=0" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

Følgelig er kongruens en ekvivalensrelasjon