Kongruence modulo

Asi všichni jsme se tak v druhé třetí třídě učili dělit. Učitel/ka ve škole se nás ptal/a třeba: Kolik je \(\frac{10}{2}\) ? Kolik \(\frac{20}{2}\)? Kolik \(\frac{50}{5}\)?

Všechny příklady mají něco společného, vyjde nějaké celé číslo (konkrétně po řadě \(5, \ 10\) a \(1\)). Co kdybychom ale chtěli počítat \(\frac{10}{6}\)? To bychom buď napsali jako desetinné číslo (konkrétně \(1\), \(\overline{6}\)) nebo jako \(1\) a zbytek \(4\).

Zkusme si formalizovat tu myšlenku zbytků. Že \(\frac{10}{6}\) je \(1\) a zbytek \(4\) jsme mohli zapsat jako \(10 = 1*6+4\).  Samozřejmě také jako
\(2*6-2 = 3*6-8=… \)

Obecněji máme v tomto příkladě, že \(10 = k*6+b\), což můžeme přepsat na \(10-b = k*6\). Tato rovnost bude splněná ale jen pro nějaká \(b\), a jak je výše naznačeno, tak ta \(b\) jsou z množiny \(\left \{2, 8, 14, … \right \}\)

Definice kongruence modulo

Samozřejmě se nemusíme zamýšlet jen na \(10\) a \(6\), takže si vezměme nějaké obecné \(a\) a \(b\), které spolu vydělíme a dojdeme podobnými úvahami jako u \(10\) a \(6\) ke vztahu
$$ a-b = k*x$$

Místo tohoto zápisu používáme tento zápis
$$ a \equiv b \ \ (mod \ x) \Leftrightarrow a-b = k*x $$
kde \(a, b, x \in \mathbb {Z} \).

$$ a \equiv b \ \ (mod \ x) $$ čteme jako „\(a\) je kongruentní s \(b\) modulo \(x\)“.

Např. tato rovnice (kterou čteme jako „10 je kongruentní s 3 modulo 7“) platí
$$ 10 \equiv 3 \ \ (mod \ 7) $$
protože \(10-3 = k*7\), konkrétně pro \(k = 1\).
Také tuto rovnici můžeme chápat tak, že \(10\) i \(3\) dají stejný zbytek po dělení \(7\).
\(\frac{10}{7} = 1\) a zbytek \(3\), \(\frac{3}{7} = 0\) a zbytek \(3\).

Ale např.
$$ 10 \not \equiv 4 \ \ (mod \ 7) $$
neboť \(10-4 = k*7\) pro \(k = \frac {6}{7} \), což není celé číslo.
Také tuto rovnici můžeme chápat tak, že \(10\) i \(4\) dají JINÝ zbytek po dělení \(7\).
\(\frac{10}{7} = 1\) a zbytek \(3\), \(\frac{4}{7} = 0\) a zbytek \(4\)

Věty o kongruenci modulo

Je celkem intuitivní, že když přičtu k \(10\) i \(3\) nějaké stejné číslo, pořád dají při dělení 7 stejný zbytek. Jinými slovy

$$ 10 \equiv 3 \ \ (mod \ 7) \Rightarrow  10 +b \equiv 3+b \ \ (mod \ 7) $$

A co víc, dokonce platí pro libovolná celá čísla \(a, b, c, x\), že

$$ a \equiv b \ \ (mod \ x) \Rightarrow  a +c \equiv b+c \ \ (mod \ x)$$

Abychom si tyto kongruence více osahali, pojďme si toto a několik dalších věcí dokázat.

Z definice kongruence máme, že
$$ a \equiv b \ \ (mod \ x) \Leftrightarrow a-b = k*x $$

Ale \(a-b = k*x  \Leftrightarrow a-b-c+c = k*x \Leftrightarrow (a+c)-(b+c) = k*x \)

Z definice kongruence ale máme, že

\(  (a+c)-(b+c) = k*x \Leftrightarrow a+c \equiv b+c  \ (mod \ x) \), což jsme chtěli dokázat.

Dále např. platí, že
$$  [(a \equiv b \ (mod \ x) ) \land (c \equiv d \ (mod \ x)) ] \Rightarrow [a+c \equiv b+d \ (mod \ x)] $$

Důkaz:
Z definice kongruence máme, že \(a = kx+b \land c = rx+d\) pro nějaká celá \(a, b, c, d, k, r, x\). Když tyto dvě rovnice sečteme, dostáváme, že \(a+c = kx+rx+b+d = (k+r)*x+b+d\). Nechť \(k+r = k’\) a přesuňme \(b+d\) na levou stranu.

Dostáváme, že \( (a+c)-(b+d) = k’x\), což ale podle definice kongruence znamená, že
$$ a+c \equiv b+d \ (mod \ x) $$
což jsme chtěli dostat.

Dále např. platí, že
$$ [a \equiv b \ (mod \ x)  \land c \equiv d \ (mod \ x) ] \Rightarrow [a*c \equiv b*d \ (mod \ x)] $$

Důkaz:
Opět podle definice kongruence máme, že \(a-b = k*x \land c-d =r*x \) pro nějaká celá \(a, b, c, d, k, r, x\).

Potom \(ac-bd = ac-cb+cb-bd = c*(a-b)+b*(c-d) = ckx+brx =
(ck+br)x \). Ale \(ck+br\) je nějaké celé číslo, tak ho nazvěme třeba \(k’\) a dostáváme, že
$$ ac-bd = k’x $$
což ale podle definice kongruence znamená, že
$$ a*c \equiv b*d \ (mod \ x) $$.

Zkusme si spočítat nějaký příklad. Určitě platí, že \(10 \equiv 3 \ (mod \ 7) \) a \(31 \equiv 24 \ (mod  \ 7) \). Podle věty, kterou jsme právě dokázali, musí platit, že také \(10*31 \equiv 3*24 \ (mod \ 7) \) neboli, že \(310 \equiv 72 \ (mod \ 7) \). Všimněme si, že jsme vůbec nemuseli počítat, jaký zbytek po dělení sedmi dají čísla \(310\) a \(72\), a přesto víme, že tyto zbytky jsou stejné. Nebo jinak řečeno, \(310-72 = 238\) je dělitelné \(7\).

Tuto větu můžeme aplikovat znova, opět mějme, že \(31 \equiv 24 \ (mod  \ 7) \) a nyní k tomu, víme, že \(310 \equiv 72 \ (mod \ 7) \). Tedy i \(31*310 \equiv 24*72 \ (mod \ 7) \), neboli \(9610 \equiv 1728\ (mod \ 7) \), takže bez jakéhokoliv počítání (samozřejmě kromě relativně triviálního násobení a odčítání), vidíme, že \(9610-1728 = 7882 \) je dělitelné  \(7\).

A naposled si dokažme např. to, že

$$ [a \equiv b \ (mod \ x)   \Rightarrow [a^n \equiv b^n \ (mod \ x)] $$

Důkaz:
Podle předchozí věty víme, že
$$ [a \equiv b \ (mod \ x)  \land a \equiv b \ (mod \ x) ] \Rightarrow [a^2 \equiv b^2 \ (mod \ x)] $$

Můžeme aplikovat opět danou větu a dostaneme, že
$$ [a \equiv b \ (mod \ x)  \land a^2 \equiv b^2 \ (mod \ x) ] \Rightarrow [a^3 \equiv b^3 \ (mod \ x)] $$

Je zjevné, že bychom dále mohli pokračovat až k libovolné mocnině, takže odsud máme, že
$$ [a \equiv b \ (mod \ x) ] \Rightarrow [a^n \equiv b^n \ (mod \ x)] $$

Záporná čísla

Spíše jen poznámka na okraj – máme-li např. \(mod \ 3\), vždy nám vyjde jen \(0, 1\) nebo \(2\). Kolik by bylo \(2+1\) v takovémto „prostoru čísel“? Byla by to opět \(0\).

Kolik by bylo \(-1\)? \(-1 = 0-1\) a místo \(0\) budu psát k lepší představě číslo \(3\), čili máme \(-1 = 0-1 = 3-1 = 2\). A takto můžeme zjistit, kolik bude libovolné celé číslo v „prostoru“ daným naším \(mod\).

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *