Cvičení 1 (25. 9. 2023)#
Příklad 1#
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\).
Příklad 2#
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\).
Příklad 3#
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\).
Příklad 4#
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 5#
Dokažte, že číslo \(23^{25}+25^{23}\) je dělitelné číslem \(48\).
Zobrazit řešení
S oběma čísly se vypořádáme zvlášť a budeme postupovat analogicky, jako v předchozích příkladech:
\(23^{25}\equiv\) \(23^{24+1}\equiv\) \(23^{24}\cdot 23^{1}\equiv\) \(23^{2\cdot 12}\cdot 23^{1}\equiv\) \(529^{12}\cdot 23\equiv\) \(1^{12}\cdot 23\equiv\) \(1\cdot 23\equiv\) \(23 \pmod{48}\)
\(25^{23}\equiv\) \(25^{22+1}\equiv\) \(25^{22}\cdot 25^{1}\equiv\) \(25^{2\cdot 11}\cdot 25^{1}\equiv\) \(625^{11}\cdot 25\equiv\) \(1^{11}\cdot 25\equiv\) \(1\cdot 25\equiv\) \(25 \pmod{48}\)
Nyní dáme obě zjištění dohromady:
\(23^{25}+25^{23}\equiv\) \(23+25\equiv\) \(48\equiv\) \(0 \pmod {48}\).
Tedy ano, dokázali jsme že číslo \(23^{25}+25^{23}\) je dělitelné číslem \(48\).
Příklad 6#
Dokažte první dvě vlastnosti Věty 1.1.
Příklad 7#
Dokažte, že čí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\).