Kongruencje
Definicja
Niech n bęie liczbą naturalną oraz niech $a$ oraz $b$ bż liczbami ca3kowitymi. Móy, ż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ę 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Ăłz kongruencji sÄ… prawdziwe?
$-26 \equiv 44\ ({\bmod{\ }}10)$
$23 \equiv 71\ ({\bmod{\ }}11)$
Własności kongruencji
Przystawanie modulo $n$ jest relacjÄ…
równważ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)$
Pozosta3e w3asności uzasadnij samodzielnie.
Z powyższej w3asności mamy:
DodajÄ…c do siebie $k$ razy kongruencja $\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Ä… cakowitÄ….
Wniosek 1
Kongruencje możemy mnożyć tronami przez dowolną liczbę całkowitą.
Z drugiej strony mnoĹĽÄ…c przez siebie $k$ razy kongruencjÄ™ $\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ć dowolnej potęgi naturalnej stronami.
KorzystajÄ…c tych wnioskĂłw 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?
$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ąją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\bmod n)) \bmod n$$
W szczególności
$a+n \equiv a \ ({\bmod {\ }}n)$
