Kongruencje
Definicja
Niech n będzie liczb± naturaln± oraz niech $a$ oraz $b$ będ± liczbami całkowitymi. Mówimy, że $a$ przystaje do $b$ modulo $n$, jeś¶li $n$ dzieli $a - b$
co zapisujemy:
$a\equiv b\ ({\bmod {\ }}n) \Leftrightarrow $ istnieje liczba całkowita $k$, że $a - b = k \cdot n$
Uwaga Dwie liczby całkowite przystaj± do siebie modulo $n$ wtedy i tylko wtedy, gdy daj± t± sam± resztę z dzielenia przez $n$.
Przykłady
$10 \equiv 1\ ({\bmod {\ }}9)$, bo $10 - 1 $ dzieli liczbę $9$.
$-1 \equiv 113\ ({\bmod{\ }}6)$, bo $113 + 1$ dzieli liczbę $6$.
$-12 \equiv 13\ ({\bmod{\ }}5)$, bo $12 + 13$ dzieli liczbę $5$.
$-5 \not \equiv 31\ ({\bmod{\ }}7)$, bo $31 + 5$ nie dzieli liczby $7$.
Które z kongruencji s± prawdziwe?
$-26 \equiv 44\ ({\bmod{\ }}10)$
$23 \equiv 71\ ({\bmod{\ }}11)$
Własno¶ci kongruencji
Przystawanie modulo $n$ jest relacj±
równoważno¶ciow±, tzn.:
- $a \equiv a\ ({\bmod {\ }}n)$ (zwrotno¶ć)
- $a \equiv b\ ({\bmod {\ }}n) \Rightarrow b \equiv a\ ({\bmod {\ }}n)$ (symetryczno¶ć)
- $a \equiv b\ ({\bmod {\ }}n),\ b \equiv c\ ({\bmod {\ }}n) \Rightarrow a\equiv c\ ({\bmod{\ }}n)$(przechodnio¶ć)
Dowód
- $a \equiv a\ ({\bmod {\ }}n) \Rightarrow a - a$ dzieli liczbę $n$.
- $a \equiv b\ ({\bmod {\ }}n) \Rightarrow $ istnieje liczba całkowita $k$, że $a - b = k \cdot n \Rightarrow b - a = l \cdot n$, gdzie $l = -k$ jest liczb± całkowit±.
- $a \equiv b\ ({\bmod {\ }}n),\ b \equiv c\ ({\bmod {\ }}n) \Rightarrow $ istnieje liczba całkowita $k$, że $a - b = k \cdot n$, istnieje liczba całkowita $l$, że $b - c = l \cdot n $ Wtedy $a - c = a - b + b - c = k \cdot n + l \cdot n = (k+l)\cdot n = m \cdot n$, gdzie $m=k+l$ jest całkowita. Zatem
$a \equiv c\ ({\bmod {\ }}n)$
Kongruencje można dodawać, odejmować, mnożyć stronami:
$a \equiv b\ ({\bmod {\ }}n), \ c \equiv d\ ({\bmod {\ }}n) \Rightarrow a+c \equiv b+d\ ({\bmod{\ }}n), a-c \equiv b-d\ ({\bmod{\ }}n)$,
$a\cdot c \equiv b\cdot d\ ({\bmod{\ }}n)$
Przykładowo pokażemy dodawanie stronami:
$a \equiv b\ ({\bmod {\ }}n), \ c \equiv d\ ({\bmod {\ }}n) \Rightarrow$ istniej± liczby całkowite $k, l$ , że $a-b = k\cdot n$ oraz $c - d = l \cdot n \Rightarrow (a+c) - (b+d) = (a - b)+(c - d)= k\cdot n + l\cdot n = (k+l)\cdot n$, czyli $a+c \equiv $b+$d\ ({\bmod{\ }}n)$
Pozostałe własno¶ci uzasadnij samodzielnie.
Z powyższej własno¶ci mamy:
Dodaj±c do siebie $k$ razy kongruencję $a \equiv b\ ({\bmod {\ }}n)$ dostajemy $ka \equiv kb\ ({\bmod {\ }}n)$, gdzie $k$ jest liczb± naturaln±.
Analogicznie odejmuj±c j± od siebie $l+1$ razy dostajemy $l \cdot a \equiv l \cdot b\ ({\bmod {\ }}n)$, gdzie l jest liczb± całkowit± ujemn±.
Zatem $a \equiv b\ ({\bmod {\ }}n) \Rightarrow m \cdot a \equiv m \cdot b\ ({\bmod {\ }}n)$, gdzie $m$ jest dowoln± liczb± całkowit±.
Wniosek 1
Kongruencje możemy mnożyć stronami przez dowoln± liczbę całkowit±.
Z drugiej strony mnoż±c przez siebie $k$ razy kongruencję $a \equiv b\ ({\bmod {\ }}n)$ dostajemy $a^{k} \equiv b^{k} ({\bmod {\ }}n)$, gdzie $k$ jest liczb± naturaln±.
Zatem $a \equiv b\ ({\bmod {\ }}n) \Rightarrow a^{k} \equiv b^{k} ({\bmod {\ }}n)$, gdzie $k$ jest dowoln± liczb± naturaln±.
Wniosek 2
Kongruncje możemy podnosić do dowolnej potęgi naturalnej stronami.
Korzystaj±ć z tych wniosków po dodaniu stronami odpowiednich kongruencji mamy:
$a \equiv b\ ({\bmod {\ }}n) \Rightarrow a_{n} \cdot a^{n} + ... +a_{1} \cdot a^{1} + a_{0} \equiv a_{n} \cdot b^{n} + ... + a_{1} \cdot b^{1} + a_{0}$, gdzie $a_{n}, ... , a_{0}$ s± dowolnymi liczbami całkowitymi, a więc
$f(a) \equiv f(b) \ ({\bmod {\ }}n)$, gdzie $f(x) = a_{n} \cdot x^{n} + ... + a_{1} \cdot x + a_{0}$
Wniosek 3
$a \equiv b\ ({\bmod {\ }}n) \Rightarrow f(a) \equiv f(b) \ ({\bmod{\ }}n)$, gdzie $f(x) = a_{n} \cdot x^{n} + ... + a_{1} \cdot x + a_{0}$
Szczególnie w programowaniu pomocne s± następuj±ce równo¶ci:
$$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$$
$$(a \cdot b) \bmod n = ((a \mod n) \cdot (b \mod n)) \bmod n$$
Wskazówka
$a+n \equiv a \ ({\bmod {\ }}n)$
powrót do spisu
