Kongruenser

Vi antar at vi her regner med heltall.

Kongruenser

Vi husker kanskje at fra geometri i kursene 1T og 1P omtales kongruente trekanter. Dette er fomrlike og like store trekanter. De dekker hverandre helt. Når vi snakker om kongruenser og kongruensregning omhandler det tall som er delelig med hverandre.

Vi regner på restklassene vi får ved divisjon på et heltall.

Dersom a og b er heltall og n \geq 1, sier vi at a er kongruent med b modulo n, dersom n|(a − b), altså om n deler differansen mellom a og b.Dette kan vi skrive somFotnoter1)http://www.math.ntnu.no/emner/MA1301/2005h/11-10.pdf

(1)   \begin{align*} a  \equiv b(\text{mod } n) \end{align*}

Vi ser på noen eksempler:

Alle tall går opp i 1, derfor er

(2)   \begin{align*} 5 \equiv 2(\text{mod }1) \end{align*}

Vi kan derfor anta videre at n \geq 2.

(3)   \begin{align*} 15 &\equiv 5(\text{mod } 2)\\ 27 &\equiv 6(\text{mod } 7 \end{align*}

Når a \equiv b(\text{mod }n) finnes det et heltall k slik at kn=a-b. Dette gjelder også omvendt. Ved divisjon finnes det heltall q og r hvor 0\leq r < n slik at a=qn+r, eller a-r=qn

(4)   \begin{align*} a \equiv r(\text{mod } n), \; 0 \leq r < n \end{align*}

Dersom 0 < a < n og 0 < b < n kan ikke n dele a-b, bortsett fra om a=b. Alle tall er kongruent modulo n til ett tall r når 0 \leq r < n.

Lemma

(5)   \begin{align*} a \equiv  b (\text{mod } n) \end{align*}

hvis og bare hvis a og b har samme rest når de deles på n

Lemma
For alle heltall a, b, c og n \leq 2 har vi disse egenskapene:

(6)   \begin{align*} i)\, a &\equiv a (\text{mod }n)\\ ii)\, a &\equiv b (\text{mod } n) \text{ gir }b \equiv  a (\text{mod } n)\\ iii)\, a &\equiv b (\text{mod } n) \text{ og }b \equiv  c (\text{mod } n) \text{ gir } a \equiv c (\text{mod } n) \end{align*}

Dette sier at \equiv (\text{mod }n) er en ekvivalensrelasjon.

Siden 3 \equiv  8 (\text{mod }5) er også 8 \equiv 3 (\text{mod }5).
Siden 3 \equiv 8 (\text{mod }5) og 8 \equiv 8008 (\text{mod }5) er også 3 \equiv 8008 (\text{mod }5).

Vi kan også regne:

Lemma
a, b, c, d heltall, n \leq 2:

(7)   \begin{align*} iv) a &\equiv b (\text{mod }n) \text{ og } c \equiv d (\text{mod }n) \text{ gir }\\ &a+c \equiv b + d (\text{mod }n) \text{ og } ac \equiv bd (\text{mod }n)\\ v) a &\equiv b (\text{mod }n) \text{gir } a + c \equiv b + c (\text{mod }n) \text{ og } ac ≡ bc (\text{mod }n)\\ vi) a &\equiv b (\text{mod }n) \text{ gir } a^f ≡ b^f (\text{mod }n) \text{ når } f \in \mathbb{W}  \end{align*}

Siden 3 \equiv 8 (\text{mod }5) og 7 \equiv 12 (\text{mod }5) er også 10 \equiv 20 (\text{mod }5) og 21 \equiv 96 (\text{mod } 5).
NB: Vi kan vanligvis ikke dele! 12 \equiv 18 (\text{mod }6) men 4 \not{\equiv} 6 (\text{mod }6).

Referanser   [ + ]

1. http://www.math.ntnu.no/emner/MA1301/2005h/11-10.pdf