Kapitola 1 - Zbytkové třídy celých čísel#
Teorie#
Definice 1
Nechť \(a,b,m \in \mathbb{Z}, m>1\). Řekneme, že číslo \(a\) je kongruentní s číslem \(b\) modulo \(m\) (případně podle modulu \(m\)), jestliže \(m | a-b\).
Skutečnost, že jsou dvě čísla \(a\) a \(b\) kongruentní modulo \(m\) zapisujeme pomocí \(a \equiv b \pmod m\) případně zkráceně jako \(a \equiv_m b\).
Věta 1
Nechť \(m \in \mathbb{Z}, m>1\). Pak pro každé \(a, b, c \in \mathbb{Z}\) platí:
a) \(a \equiv a \pmod m\),
b) pokud \(a \equiv b \pmod m\), pak \(b \equiv a \pmod m\),
c) pokud \(a \equiv b \pmod m\) a \(b \equiv c \pmod m\), pak \(a \equiv c \pmod m\).
Věta 2
Celá čísla \(a\) a \(b\) jsou kongruentní modulo \(m\) právě tehdy, když mají po dělení číslem \(m\) stejný zbytek.
Věta 3
Nechť \(a, b, c, d, m \in \mathbb{Z}, m>1\). Jestliže \(a \equiv b \pmod m\) a \(c \equiv d \pmod m\), pak
a) \(a+c \equiv b+d \pmod m\),
b) \(a\cdot c \equiv b\cdot d \pmod m\).
Důsledek 1
Nechť \(a \equiv b\pmod m, c \in \mathbb{Z}, n \in \mathbb{N}\). Pak
a) \(a+c \equiv b+c \pmod m\),
b) \(a\cdot c \equiv b\cdot c \pmod m\).
c) \(a^n \equiv b^n \pmod m\).
Věta 4
Nechť \(a,b,c \in \mathbb{Z}, m>1\). Pokud \(a \cdot c \equiv b \cdot c \pmod m\) a zároveň \(\textrm{D}(m,c)=1\), pak \(a \equiv b \pmod m\).
\(\textrm{D}(a,b)\) značí nejmenší společní dělitel čísel \(a\) a \(b\).
Věta 5
Nechť \(\oplus\) a \(\odot\) jsou operace sčítání a násobení na systému zbytkových tříd \(\overline{\mathbb{Z}}_m\). Pak
a) obě operace jsou komutativní a asociativní,
b) v \(\overline{\mathbb{Z}}_m\) existuje nulový prvek (neutrální prvek operace \(\oplus\)) a jednotkový prvek (neutrální prvek operace \(\odot\)),
c) ke každému prvku ze \(\overline{\mathbb{Z}}_m\) existuje prvek opačný (inverzní prvek vzhledem k operaci \(\oplus\)),
d) operace \(\odot\) je distributivní vzhledem k operaci \(\oplus\).
Cvičení#
Příklad 1
a) Určete zbytek po dělení čísla \(142\) číslem \(6\).
Zobrazit řešení
Nejprve si číslo \(142\) vhodně upravíme na součet dvou čísel, přičemž se budeme snažit, aby první bylo co největší a dělitelné číslem \(6\) beze zbytku: \(142=\underbrace{138}_{=6\cdot 23}+4\).
Číslo \(138\) je dělitelné číslem \(6\) beze zbytku a tedy platí, že \(138\equiv 0 \pmod 6\)
Využijeme vlastnost a) Důsledku 1.1. Protože víme, že \(138\equiv 0 \pmod 6\) a \(4\in \mathbb{Z}\), můžeme psát \(138 + 4 \equiv 0+4 \pmod 6\)
Můžeme tedy psát \(142 \equiv 4 \pmod 6\).
Zbytek po dělení čísla \(142\) číslem \(6\) je tedy roven \(4\).
b) Určete zbytek po dělení čísla \(122+171\) číslem 8.
Zobrazit řešení
Postup A:
S oběma čísly se vypořádáme zvlášť a budeme postupovat analogicky, jako v předchozím příkladě:
\(122=8\cdot12+2\) a tedy \(122\equiv 2 \pmod 8\).
\(171=8\cdot21+3\) a tedy \(171\equiv 3 \pmod 8\).
Nyní využijeme vlastnost a) Věty 1.3. Protože \(122\equiv 2 \pmod 8\) a \(171\equiv 3 \pmod 8\), můžeme psát \(122+171 \equiv \underbrace{2 + 3}_{=5} \equiv 5 \pmod 8\).
Zbytek po dělení čísla \(122+171\) číslem \(8\) je tedy roven \(5\).
Postup B:
Nejprve obě čísla sečteme a následně budeme postupovat jako v prvním příkladě:
\(122+171=293=8\cdot 36 +5\) a tedy \(293 \equiv 5 \pmod 8\).
Zbytek po dělení čísla \(122+171\) číslem \(8\) je tedy roven \(5\).
c) Určete zbytek po dělení čísla \(2^{30}\) číslem \(15\).
Zobrazit řešení
Pokusíme se najít nějakou vhodnou mocninou čísla \(2\), která je kongruentní s číslem \(0, 1\) nebo \(-1\):
\(2^4 =16\) a je zřejmé, že \(16 \equiv 1 \pmod {15}\)
Tohoto poznatku využijeme a upravíme si mocninu čísla \(2\): \(2^{30}=2^{4\cdot7+2}=2^{4\cdot7}\cdot 2^2 = 16^7 \cdot 4\)
Nyní využijeme vlastnost c) Důsledku 1.1. Protože \(16\equiv 1 \pmod {15}\), můžeme psát \(16^{7} \equiv \underbrace{1^7}_{=1} \equiv 1 \pmod {15}\).
Na závěr využijeme vlastnost b) Důsledku 1.1. Protože \(16^7\equiv 1 \pmod {15}\) a \(4\in \mathbb{Z}\), můžeme psát \(16^7 \cdot 4 \equiv \underbrace{1 \cdot 4}_{=4} \equiv 4 \pmod {15}\).
Zbytek po dělení čísla \(2^{30}\) číslem \(15\) je tedy roven \(4\).
d) Určete zbytek po dělení čísla \(181\cdot 3^{70}\) číslem 13.
Zobrazit řešení
S oběma čísly se vypořádáme zvlášť a budeme postupovat analogicky, jako v předchozích příkladech:
\(181=13\cdot13+12\) a tedy \(181\equiv 12 \pmod{13}\).
Opět se pokusíme najít vhodnou mocninu čísla \(3\): \(3^3=27\equiv 1 \pmod{13}\). Upravíme si tedy mocninu \(3^{70}=3^{3\cdot23+1}=3^{3\cdot 23}\cdot 3=27^{23}\cdot 3\). Využijeme vlastností b) a c) Důsledku 1.1 a můžeme psát: \(27^{23}\cdot 3\equiv 1 \cdot 3 \equiv 3 \pmod{13}\).
Na závěr využijeme vlastnost b) Věty 1.3. Protože \(181\equiv 12 \pmod{13}\) a \(3^{70}\equiv 1 \pmod{13}\), platí: \(181\cdot 3^{70} \equiv 12\cdot3 \equiv 36 \equiv 10 \pmod{13}\).
Zbytek po dělení čísla \(181\cdot 3^{70}\) číslem 13 je tedy roven \(10\).
Příklad 2
Nechť \(a=352 \cdot 71 + 55^2 \cdot 86 + 15 \cdot 39\). Určete
a) paritu čísla \(a\):
Zobrazit řešení
Problém vyřešíme tak, že spočítáme zbytek výrazu \(a\) po dělení číslem 2. Pokud bude zbytek roven 0, jedná se o sudé číslo, pokud bude roven \(1\) půjde o číslo liché.
Číslo \(352\) je sudé, tedy dělitelné číslem \(2\) beze zbytku. Můžeme proto psát \(352 \equiv 0 \pmod 2\)
Naopak číslo \(71\) je liché, tedy po dělení číslem \(2\) nám zůstane zbytek \(1\). Můžeme tedy psát \(71 \equiv 1 \pmod 2\)
Číslo \(55\) je liché, tedy opět bude zbytek po dělení roven jedné, tj. \(55 \equiv 1 \pmod 2\) a tedy s využitím Důsledku 1.1 můžeme psát \(55^2 \equiv 1^2 \pmod 2\)
Analogicky lze odvodit, že \(86 \equiv 0 \pmod 2\), \(15 \equiv 1 \pmod 2\) a \(39 \equiv 1 \pmod 2\)
Nyní můžeme získané poznatky spojit dohromady:
\(352 \cdot 71 + 55^2 \cdot 86 + 15 \cdot 39 \equiv \underbrace{0 \cdot 1 + 1^2 \cdot 0+1\cdot 1}_{=1} \equiv 1 \pmod 2\)
Výraz \(a\) je tedy kongruentní s \(1\) modulo \(2\). A protože zbytek po dělení čísla \(1\) číslem \(2\) je roven \(1\), je i zbytek po dělení výrazu \(a\) číslem \(2\) roven \(1\). \(a\) je tedy liché číslo.
b) poslední číslici čísla \(a\):
Zobrazit výsledek
Poslední číslice čísla \(a\) je \(7\).
c) zbytek po dělení čísla \(a\) číslem 7:
Zobrazit výsledek
Zbytek po dělení je roven \(1\).
Příklad 3
Dokažte, že
a) číslo \(2^{70}+3^{70}\) je dělitelné číslem \(13\),
Zobrazit řešení
Je třeba ukázat, že \(2^{70}+3^{70} \equiv 0 \pmod{13}\):
Postup A:
Nejprve se vypořádáme s výrazem \(2^{70}\). Při zkoumání mocnin čísla \(2\) si můžeme všimnout, že \(2^6=64\) a zbytek po dělení čísla \(64\) číslem \(13\) je \(12\) \((64-4\cdot 12=64-52=12)\). Můžeme tedy napsat, že \(64 \equiv 12 \pmod {13}\). Platí ovšem také \(12 \equiv -1 \pmod {13}\) protože \(-1\) a \(12\) patří do stejné zbytkové třídy. Nyní je třeba výraz \(2^{70}\) vhodně upravit, abychom mohli nově získáný poznatek aplikovat: \(2^{70}=2^{6\cdot 11+4}=2^{6\cdot 11}\cdot 2^4=64^{11}\cdot2^4\). S využitím výše zmíněné kongruence získáváme \(64^{11}\cdot2^4 \equiv {-1}^{11}\cdot 2^4 \equiv -1 \cdot 16 \equiv -16 \pmod{13}\).
Nyní se zaměříme na výraz \(3^{70}\), tedy prozkoumáme mocniny čísla \(3\). Je zřejmé, že \(3^3=27\) a platí \(27 \equiv 1 \pmod{13}\). Upravíme si tedy výraz \(3^{70}=3^{3\cdot 23+1}=3^{3\cdot 23}\cdot 3= 27^{23}\cdot3\) a aplikujeme kongruenci \(27^{23}\cdot3 \equiv 1^{27}\cdot 3 = 3 \pmod{13}\).
Teď už zbývá jen získáné poznatky spojit:
\(2^{70}+3^{70} \equiv -16 +3 \equiv 0 \pmod {13}\).
Tedy ano, dokázali jsme, že číslo \(2^{70}+3^{70}\) je beze zbytku dělitelném číslem \(13\).
Postup B:
Alternativní postup, tentokrát již bez komentáře
\(2^{70}+3^{70} \equiv\) \((2^2)^{35}+(3^2)^{35}\equiv\) \(4^{35}+9^{35}\equiv\) \(4^{34+1}+9^{34+1}\equiv\) \((4^2)^{17}\cdot4+(9^2)^{17}\cdot 9\equiv\) \(16^{17}\cdot4+81^{17}\cdot9\equiv\) \(3^{17}\cdot 4+ 3^{17}\cdot 9\equiv\) \(3^{17}\cdot(4+9)\equiv\) \(3^{17}\cdot13 \equiv\) \(3^{17}\cdot 0\equiv\) \(0 \pmod{13}\)
Tedy ano, dokázali jsme, že číslo \(2^{70}+3^{70}\) je beze zbytku dělitelném číslem \(13\).
b) číslo \(23^{25}+25^{23}\) je dělitelné číslem \(48\),
Zobrazit výsledek
Ano, je dělitelné.
Příklad 4
Dokažte, že pro každé \(n \in \mathbb{N_0}\) je číslo \(6^{n+1}+13\cdot 5^{2 n}\) násobkem čísla \(19\).
Zobrazit výsledek
Ano, číslo \(6^{n+1}+13\cdot 5^{2 n}\) je násobkem čísla \(19\) pro každé \(n \in \mathbb{N_0}\).
Příklad 5
Dokažte, že pro každé \(n \in \mathbb{N_0}\) platí: číslo \(7\) nedělí \(3^n + 5^{3 n+4}\).
Zobrazit výsledek
Ano, číslo \(7\) opravdu nedělí číslo \(3^n + 5^{3 n+4}\).
Příklad 6
Dokažte, že pro každé \(n \in \mathbb{N}\) platí: číslo \(31\) dělí \(5^{n+1}+6^{2 n-1}\).
Zobrazit výsledek
Ano, číslo \(31\) opravdu dělí \(5^{n+1}+6^{2 n-1}\) pro každé \(n \in \mathbb{N}\).