Næste: 2.2 Restklasser Op: 2. Kongruens og modulusregning Foregående: 2. Kongruens og modulusregning

2.1 Kongruens

Vi starter med at definere kongruens:

DEFINITION 2.1   Hvis differencen mellem to tal $a$ og $b$ er delelig af et andet tal $m$, siger vi at $a$ er kongruent med $b$ modulus $m$, og det skrives således:

$$a \equiv b \pmod{m}$$ (2.1)

Vi kan også skrive det som en almindelig ligning i stedet:

$$\frac{a-b}{m} = n \Leftrightarrow a = nm + b,\quad n \in \mathbb{Z}$$ (2.2)

Det var C. F. Gauss (1777-1855) som opfandt denne notation[11, s. 69]. Notationen ligner den vi bruger til almindelige ligninger, og det viser sig at man kan regne på kongruenserne efter nogle specielle regler. Det var et stort fremskridt, da man nu havde fået et værktøj til at beskrive de ting, der sker når tal går op i hinanden.

Da de fleste af de følgende sætninger er ret trivielle at bevise, har jeg flyttet beviserne over i bilaget, se side .

SÆTNING 2.2   Følgende kongruenser er altid sande: $a \equiv b \pmod{1}$ og $a \equiv 0 \pmod{a}$.

SÆTNING 2.3   Vi kan gange både $a$ og $b$ med det samme tal: $a \equiv b \pmod{m} \Leftrightarrow ad \equiv bd \pmod{m}$. Som et specialtilfælde har vi at $a \equiv 0 \pmod{m} \Leftrightarrow an \equiv 0 \pmod{m}$.

SÆTNING 2.4   Kongruenser modulus det samme tal kan lægges sammen og trækkes fra hinanden: Hvis $a \equiv b$ og $c \equiv d \pmod{m}$ så gælder der at $a+c \equiv b+d \pmod{m}$.

SÆTNING 2.5   Kongruenser modulus det samme tal kan også ganges sammen: Hvis $a \equiv b$ og $c \equiv d \pmod{m}$ så gælder der at $ac \equiv bd \pmod{m}$. Hvis vi gentager processen får vi at der også gælder at: $a^k \equiv b^k \pmod{m}$.

SÆTNING 2.6   Hvis $a \equiv b$ og $b \equiv c \pmod{m}$ så gælder der at $a \equiv c \pmod{m}$.

SÆTNING 2.7   Vi kan lægge et helt antal $m$ til eller trække det fra $a$, og vil stadig få samme rest: $a\pm nm \equiv b \pmod{m}$.

SÆTNING 2.8   Kongruensen $a \equiv b \pmod{m}$ er kun sandt, hvis der samtidig gælder at $ac \equiv bc \pmod{mc}$.

SÆTNING 2.9   Hvis $ac \equiv bc \pmod{m}$ og største fælles divisor for $c$ og $m$ er $d$, så gælder der at $a \equiv b \pmod{\frac{m}{d}}$. Hvis $c$ og $m$ er indbyrdes primiske ($d=1$), og vi får så at $a \equiv b \pmod{m}$.

$ac \equiv bc \pmod{m}$ kan skrives om til $ac = jm+bc$. Den største fælles divisor for $c$ og $m$ er $d$, så der gælder så også at $a\frac{c}{d} = j\frac{m}{d} + b\frac{c}{d}$. Her er alle brøkerne heltal, da $d$ går op i både $c$ og $m$.

Vi kan så gange igennem med $\frac{d}{c}$, og får så at $a = \frac{m}{c} + b \Leftrightarrow a$ hvilket viser at $a$ er kongruent med $b$ modulus $\frac{m}{c}$. $\blacksquare$

Som et eksempel kan vi se på kongruensen $6\cdot 6 \equiv 1\cdot 6 \pmod{15}$. Her har vi at største fælles divisor for 6 og 15 lig 3. Vi kan derfor omskrive kongruensen til $6 \equiv 1 \pmod{5}$, hvilket tydeligvis også er sandt.

• Næste: 2.2 Restklasser
• Op: 2. Kongruens og modulusregning
• Foregående: 2. Kongruens og modulusregning