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.
<object width="420" height="315"><param name="movie" value="https://www.youtube.com/watch?v=dRqjkLXjusk&list=PLU9Gs7tAVUEWCM-d20Hg0qKY00Wq_okNF&index=49"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/-mcbsrAXlAg?version=3&hl=en_US" type="application/x-shockwave-flash" width="420" height="315" allowscriptaccess="always" allowfullscreen="true"></embed></object>
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) <math>a\equiv a</math>
- ii) <math>a\equiv c</math> hvis og bare hvis <math>c\equiv a</math>
- iii) Hvis <math>a\equiv c</math> og <math>c\equiv e</math>, så må <math>a\equiv e</math>
Følgelig er kongruens en ekvivalensrelasjon