1. Vyřešte kongruenci \( 7x \equiv 4 \pmod{15} \).
Řešení příkladu:
Máme kongruenci \(7x \equiv 4 \pmod{15}\). Nejprve zjistíme, zda má řešení. Spočítáme \(\gcd(7, 15)\).
\(\gcd(7, 15) = 1\), protože \(7\) je prvočíslo a \(15\) není dělitelné \(7\). Proto existuje inverzní prvek k \(7\) modulo \(15\).
Najdeme inverzi čísla \(7\) modulo \(15\), tj. číslo \(y\), které splňuje \(7y \equiv 1 \pmod{15}\).
Pomocí rozšířeného Eukleidova algoritmu:
\(15 = 7 \times 2 + 1 \Rightarrow 1 = 15 – 7 \times 2\)
Tedy \(7 \times (-2) \equiv 1 \pmod{15}\). Proto inverze \(7\) modulo \(15\) je \(13\), protože \(-2 \equiv 13 \pmod{15}\).
Nyní vynásobíme obě strany původní kongruence inverzí \(7\):
\(x \equiv 4 \times 13 \equiv 52 \equiv 7 \pmod{15}\).
Řešením je tedy \(x \equiv 7 \pmod{15}\).
2. Najděte všechna řešení kongruence \(12x \equiv 8 \pmod{20}\).
Řešení příkladu:
Určíme \(\gcd(12, 20)\).
\(\gcd(12, 20) = 4\).
Podmínka existence řešení je, že \(\gcd\) dělí pravou stranu kongruence, tedy \(4\) musí dělit \(8\), což platí.
Rozdělíme celou kongruenci dělením \(4\):
\(3x \equiv 2 \pmod{5}\).
Najdeme inverzi \(3\) modulo \(5\). Jelikož \(3 \times 2 = 6 \equiv 1 \pmod{5}\), inverze je \(2\).
Vynásobíme obě strany rovnice 2:
\(x \equiv 2 \times 2 = 4 \pmod{5}\).
Protože jsme původní modulus dělili \(4\), máme \(4\) různé třídy řešení modulo \(20\), konkrétně:
\(x \equiv 4 + 5k, k = 0, 1, 2, 3\).
To znamená řešení jsou \(x \equiv 4, 9, 14, 19 \pmod{20}\).
3. Určete zbytek po dělení čísla \(7^{100}\) číslem \(13\).
Řešení příkladu:
Potřebujeme najít \(7^{100} \pmod{13}\).
Podle Fermatova malého teorému, protože 13 je prvočíslo, platí \(7^{12} \equiv 1 \pmod{13}\).
Rozložíme exponent \(100\) na násobky \(12\):
\(100 = 12 \times 8 + 4\).
Proto:
\(7^{100} = 7^{12 \times 8 + 4} = (7^{12})^8 \times 7^4 \equiv 1^8 \times 7^4 \equiv 7^4 \pmod{13}\).
Spočítáme \(7^4\) modulo \(13\):
\(7^2 = 49 \equiv 10 \pmod{13}\), protože \(49 – 3 \times 13 = 49 – 39 = 10\).
\(7^4 = (7^2)^2 = 10^2 = 100 \equiv 9 \pmod{13}\), protože \(100 – 7 \times 13 = 100 – 91 = 9\).
Výsledkem je \(7^{100} \equiv 9 \pmod{13}\).
4. Najděte všechna řešení soustavy kongruencí:
\(x \equiv 3 \pmod{5}\)
\(x \equiv 4 \pmod{7}\)
Řešení příkladu:
Máme systém:
\(x \equiv 3 \pmod{5}\)
\(x \equiv 4 \pmod{7}\)
Podle Čínské věty o zbytcích (moduly jsou nesoudělné: \(\gcd(5,7)=1\)) existuje jednoznačné řešení modulo \(35\).
Nejprve vyjádříme \(x\) z první kongruence:
\(x = 3 + 5k\), kde \(k \in \mathbb{Z}\).
Dosadíme do druhé kongruence:
\(3 + 5k \equiv 4 \pmod{7}\)
\(5k \equiv 1 \pmod{7}\).
Najdeme inverzi \(5\) modulo \(7\). Jelikož \(5 \times 3 = 15 \equiv 1 \pmod{7}\), inverze je \(3\).
Vynásobíme obě strany rovnice \(3\):
\(k \equiv 3 \times 1 = 3 \pmod{7}\).
Proto \(k = 3 + 7t\), kde \(t \in \mathbb{Z}\).
Dosadíme zpět do \(x\):
\(x = 3 + 5 \times (3 + 7t) = 3 + 15 + 35t = 18 + 35t\).
Řešení soustavy je tedy:
\(x \equiv 18 \pmod{35}\).
5. Najděte všechny prvočíselné zbytky \(x\) modulo 11, které splňují \(x^2 \equiv 3 \pmod{11}\).
Řešení příkladu:
Hledáme řešení kongruence \(x^2 \equiv 3 \pmod{11}\).
Vypočítáme hodnoty \(x^2 \pmod{11}\) pro \(x = 0, 1, 2, \dots, 10\):
- \(0^2 \equiv 0\)
- \(1^2 \equiv 1\)
- \(2^2 = 4\)
- \(3^2 = 9\)
- \(4^2 = 16 \equiv 5\)
- \(5^2 = 25 \equiv 3\)
- \(6^2 = 36 \equiv 3\)
- \(7^2 = 49 \equiv 5\)
- \(8^2 = 64 \equiv 9\)
- \(9^2 = 81 \equiv 4\)
- \(10^2 = 100 \equiv 1\)
Vidíme, že \(x^2 \equiv 3 \pmod{11}\) pro \(x \equiv 5\) a \(x \equiv 6\).
Řešení jsou tedy \(x \equiv 5 \pmod{11}\) a \(x \equiv 6 \pmod{11}\).
6. Vyřešte kongruenci \(35x \equiv 10 \pmod{50}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(35, 50)\).
\(\gcd(35, 50) = 5\).
Podmínka existence řešení: \(5\) musí dělit \(10\), což platí.
Podělíme kongruenci \(5\):
\(7x \equiv 2 \pmod{10}\).
Protože \(\gcd(7, 10) = 1\), inverze \(7\) modulo \(10\) existuje. Najdeme ji:
Hledáme \(y\), aby \(7y \equiv 1 \pmod{10}\).
Zkoušíme hodnoty: \(7 \times 3 = 21 \equiv 1 \pmod{10}\), inverze je tedy \(3\).
Vynásobíme obě strany rovnice \(3\):
\(x \equiv 2 \times 3 = 6 \pmod{10}\).
Protože jsme modulus dělili \(5\), máme \(5\) řešení mod \(50\):
\(x \equiv 6 + 10k, k = 0, 1, 2, 3, 4\).
Řešení jsou tedy \(x \equiv 6, 16, 26, 36, 46 \pmod{50}\).
7. Najděte hodnotu \(x\), která splňuje \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{4}\) a \(x \equiv 1 \pmod{5}\).
Řešení příkladu:
Máme systém kongruencí:
\(x \equiv 2 \pmod{3}\)
\(x \equiv 3 \pmod{4}\)
\(x \equiv 1 \pmod{5}\)
Moduly \(3, 4, 5\) jsou po dvou nesoudělné, takže použijeme Čínskou větu o zbytcích s výsledným modulem \(60\).
Nejprve spojíme první dvě kongruence:
\(x = 2 + 3a\)
Dosadíme do druhé:
\(2 + 3a \equiv 3 \pmod{4} \Rightarrow 3a \equiv 1 \pmod{4}\).
Inverze 3 modulo 4 je 3, protože \(3 \times 3 = 9 \equiv 1 \pmod{4}\).
\(a \equiv 3 \times 1 = 3 \pmod{4}\).
Tedy \(a = 3 + 4b\).
Dosadíme zpět do \(x\):
\(x = 2 + 3(3 + 4b) = 2 + 9 + 12b = 11 + 12b\).
Nyní dosadíme do třetí kongruence:
\(11 + 12b \equiv 1 \pmod{5} \Rightarrow 12b \equiv -10 \equiv 0 \pmod{5}\).
Protože \(12 \equiv 2 \pmod{5}\), dostáváme:
\(2b \equiv 0 \pmod{5}\).
To znamená \(b \equiv 0 \pmod{5}\), tedy \(b = 5c\).
Řešení pro \(x\) je:
\(x = 11 + 12 \times 5c = 11 + 60c\).
Nejmenší kladné řešení je \(x = 11\).
8. Pro číslo \(a = 17\) a modul \(m = 31\) najděte inverzní prvek k \(a\) modulo \(m\).
Řešení příkladu:
Potřebujeme najít \(x\), aby platilo \(17x \equiv 1 \pmod{31}\).
Použijeme rozšířený Eukleidův algoritmus pro nalezení \(\gcd(17, 31)\) a koeficientů Bézoutovy identity.
Postup:
\(31 = 17 \times 1 + 14\)
\(17 = 14 \times 1 + 3\)
\(14 = 3 \times 4 + 2\)
\(3 = 2 \times 1 + 1\)
\(2 = 1 \times 2 + 0\)
Nyní zpětně vyjádříme 1 jako kombinaci \(17\) a \(31\):
\(1 = 3 – 2 \times 1\)
\(2 = 14 – 3 \times 4 \Rightarrow 1 = 3 – (14 – 3 \times 4) = 5 \times 3 – 14\)
\(3 = 17 – 14 \Rightarrow 1 = 5 \times (17 – 14) – 14 = 5 \times 17 – 6 \times 14\)
\(14 = 31 – 17 \Rightarrow 1 = 5 \times 17 – 6 \times (31 – 17) = 11 \times 17 – 6 \times 31\)
Tedy \(11 \times 17 \equiv 1 \pmod{31}\).
Inverze čísla \(17\) modulo \(31\) je \(11\).
9. Spočítejte \(3^{1000} \pmod{7}\).
Řešení příkladu:
Podle Fermatova malého teorému \(3^6 \equiv 1 \pmod{7}\), protože \(7\) je prvočíslo.
Rozložíme exponent \(1000\) na násobky \(6\):
\(1000 = 6 \times 166 + 4\).
Proto:
\(3^{1000} = 3^{6 \times 166 + 4} = (3^6)^{166} \times 3^4 \equiv 1^{166} \times 3^4 = 3^4 \pmod{7}\).
Spočítáme \(3^4\) modulo \(7\):
\(3^2 = 9 \equiv 2 \pmod{7}\)
\(3^4 = (3^2)^2 = 2^2 = 4 \pmod{7}\).
Výsledkem je \(3^{1000} \equiv 4 \pmod{7}\).
10. Určete počet řešení kongruence \(x^2 \equiv 1 \pmod{15}\).
Řešení příkladu:
Máme kongruenci \(x^2 \equiv 1 \pmod{15}\).
Protože \(15 = 3 \times 5\), použijeme Čínskou větu o zbytcích.
Najdeme řešení pro každou modulovou kongruenci zvlášť:
\(x^2 \equiv 1 \pmod{3}\) a \(x^2 \equiv 1 \pmod{5}\).
Kongruence modulo \(3\) má řešení \(x \equiv 1 \pmod{3}\) a \(x \equiv 2 \pmod{3}\), tedy \(2\) řešení.
Kongruence modulo \(5\) má řešení \(x \equiv 1 \pmod{5}\) a \(x \equiv 4 \pmod{5}\), tedy \(2\) řešení.
Podle Čínské věty o zbytcích se počet řešení soustavy rovná součinu počtu řešení jednotlivých kongruencí:
\(2 \times 2 = 4\).
Řešení jsou tedy \(4 (\)modulo \(15)\).
11. Vyřešte kongruenci \(14x \equiv 30 \pmod{100}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(14, 100)\).
\(\gcd(14, 100) = 2\).
Podmínka existence řešení: \(2\) musí dělit \(30\), což platí.
Podělíme kongruenci \(2\):
\(7x \equiv 15 \pmod{50}\).
Protože \(\gcd(7, 50) = 1\), inverze \(7\) modulo \(50\) existuje. Najdeme ji:
Hledáme \(y\), aby \(7y \equiv 1 \pmod{50}\).
Zkoušíme hodnoty: \(7 \times 43 = 301 \equiv 1 \pmod{50}\), takže inverze je \(43\).
Vynásobíme obě strany rovnice \(43\):
\(x \equiv 15 \times 43 = 645 \equiv 45 \pmod{50}\).
Protože jsme modulus dělili \(2\), máme \(2\) řešení mod \(100\):
\(x \equiv 45 + 50k, k = 0, 1\).
Řešení jsou tedy \(x \equiv 45, 95 \pmod{100}\).
12. Určete všechny řešení kongruence \(x^3 \equiv 8 \pmod{13}\).
Řešení příkladu:
Chceme najít všechna \(x\), pro která platí \(x^3 \equiv 8 \pmod{13}\).
Protože 13 je prvočíslo, můžeme zkoušet všechny hodnoty \(x = 0, 1, \dots, 12\).
Vypočítáme \(x^3 \pmod{13}\):
\(0^3 = 0\),
\(1^3 = 1\),
\(2^3 = 8\) – shoda, \(x=2\) je řešení.
\(3^3 = 27 \equiv 1\),
\(4^3 = 64 \equiv 12\),
\(5^3 = 125 \equiv 8\) – další řešení \(x=5\).
\(6^3 = 216 \equiv 8\) – další řešení \(x=6\).
\(7^3 = 343 \equiv 5\),
\(8^3 = 512 \equiv 5\),
\(9^3 = 729 \equiv 1\),
\(10^3 = 1000 \equiv 12\),
\(11^3 = 1331 \equiv 5\),
\(12^3 = 1728 \equiv 12\).
Řešení jsou tedy \(x \equiv 2, 5, 6 \pmod{13}\).
13. Najděte inverzní prvek k \(17\) modulo \(43\).
Řešení příkladu:
Chceme najít \(y\) takové, že \(17y \equiv 1 \pmod{43}\).
Použijeme rozšířený Euklidův algoritmus pro nalezení \(\gcd(17, 43)\) a koeficientů.
\(43 = 17 \times 2 + 9\)
\(17 = 9 \times 1 + 8\)
\(9 = 8 \times 1 + 1\)
\(8 = 1 \times 8 + 0\)
Zpětně:
\(1 = 9 – 8 \times 1\)
\(8 = 17 – 9 \times 1\)
\(1 = 9 – (17 – 9 \times 1) = 2 \times 9 – 17\)
\(9 = 43 – 17 \times 2\)
\(1 = 2 \times (43 – 17 \times 2) – 17 = 2 \times 43 – 5 \times 17\)
To znamená \(1 \equiv -5 \times 17 \pmod{43}\), tedy \(y \equiv -5 \equiv 38 \pmod{43}\).
Inverze k \(17\) modulo \(43\) je tedy \(38\).
14. Vyřešte soustavu kongruencí:
\(x \equiv 2 \pmod{3}\),
\(x \equiv 3 \pmod{5}\),
\(x \equiv 2 \pmod{7}\).
Řešení příkladu:
Součet modulů je \(3 \times 5 \times 7 = 105\).
Nejprve vyřešíme dvě první kongruence:
Najdeme číslo \(x\), které splňuje \(x \equiv 2 \pmod{3}\) a \(x \equiv 3 \pmod{5}\).
Zapišme \(x = 3 + 5k\), hledáme \(k\), aby \(3 + 5k \equiv 2 \pmod{3}\).
\(3 + 5k \equiv 2 \pmod{3} \Rightarrow 5k \equiv -1 \equiv 2 \pmod{3}\).
Protože \(5 \equiv 2 \pmod{3}\), máme \(2k \equiv 2 \pmod{3}\).
Vynásobíme inverzi 2 modulo \(3\), která je \(2\):
\(k \equiv 2 \times 2 = 4 \equiv 1 \pmod{3}\).
Nejmenší řešení je \(k=1\), tedy \(x = 3 + 5 \times 1 = 8\).
Takže \(x \equiv 8 \pmod{15}\).
Teď vyřešíme:
\(x \equiv 8 \pmod{15}\),
\(x \equiv 2 \pmod{7}\).
Zapišme \(x = 8 + 15m\), hledáme \(m\), aby \(8 + 15m \equiv 2 \pmod{7}\).
\(15m \equiv 2 – 8 = -6 \equiv 1 \pmod{7}\), protože \(-6 \equiv 1 \pmod{7}\).
Proto \(15m \equiv 1 \pmod{7}\).
Vzhledem k tomu, že \(15 \equiv 1 \pmod{7}\), máme \(m \equiv 1 \pmod{7}\).
Nejmenší řešení je \(m=1\), tedy \(x = 8 + 15 \times 1 = 23\).
Řešení celé soustavy je tedy \(x \equiv 23 \pmod{105}\).
15. Najděte všechny řešení kongruence \(x^2 + x + 1 \equiv 0 \pmod{7}\).
Řešení příkladu:
Hledáme \(x\), které splňuje \(x^2 + x + 1 \equiv 0 \pmod{7}\).
Zkoušíme hodnoty \(x = 0, 1, \dots, 6\):
\(0^2 + 0 + 1 = 1 \neq 0\)
\(1 + 1 + 1 = 3 \neq 0\)
\(4 + 2 + 1 = 7 \equiv 0\), takže \(x=2\) je řešení.
\(9 + 3 + 1 = 13 \equiv 6 \neq 0\) pro \(x=3\)
\(16 + 4 + 1 = 21 \equiv 0\), takže \(x=4\) je řešení.
\(25 + 5 + 1 = 31 \equiv 3 \neq 0\)
\(36 + 6 + 1 = 43 \equiv 1 \neq 0\)
\(49 + 7 + 1 = 57 \equiv 1 \neq 0\)
Řešení jsou tedy \(x \equiv 2, 4 \pmod{7}\).
16. Vyřešte kongruenci \(4x \equiv 3 \pmod{9}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(4, 9) = 1\), proto existuje inverze \(4\) modulo \(9\).
Najdeme \(y\), že \(4y \equiv 1 \pmod{9}\).
Zkoušíme hodnoty:
\(4 \times 7 = 28 \equiv 1 \pmod{9}\), inverze je tedy \(7\).
Vynásobíme kongruenci \(7\):
\(x \equiv 3 \times 7 = 21 \equiv 3 \pmod{9}\).
Řešení je tedy \(x \equiv 3 \pmod{9}\).
17. Určete počet řešení kongruence \(x^2 \equiv 16 \pmod{35}\).
Řešení příkladu:
Protože \(35 = 5 \times 7\), použijeme Čínskou větu o zbytcích.
Najdeme řešení pro \(x^2 \equiv 16 \pmod{5}\) a \(x^2 \equiv 16 \pmod{7}\).
Kongruence modulo \(5\):
\(16 \equiv 1 \pmod{5}\), hledáme \(x\), že \(x^2 \equiv 1 \pmod{5}\).
Řešení: \(x \equiv 1, 4 \pmod{5}\) \((2\) řešení\()\).
Kongruence modulo \(7\):
\(16 \equiv 2 \pmod{7}\), hledáme \(x\), že \(x^2 \equiv 2 \pmod{7}\).
Zkoušíme hodnoty \(x = 0,1,…,6\):
\(1^2=1\),
\(3^2=9 \equiv 2\),
\(4^2=16 \equiv 2\), takže řešení jsou \(x \equiv 3, 4 \pmod{7}\) \((2\) řešení\()\).
Celkový počet řešení je \(2 \times 2 = 4\).
18. Najděte všechna řešení kongruence \(5x \equiv 1 \pmod{26}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(5, 26) = 1\), tedy inverze \(5\) modulo \(26\) existuje.
Najdeme \(y\), že \(5y \equiv 1 \pmod{26}\).
Zkoušíme hodnoty:
\(5 \times 21 = 105 \equiv 1 \pmod{26}\), takže inverze je \(21\).
Tedy řešení je \(x \equiv 21 \pmod{26}\).
19. Vyřešte kongruenci \(2x \equiv 3 \pmod{7}\).
Řešení příkladu:
Protože \(\gcd(2,7) = 1\), inverze \(2\) modulo \(7\) existuje.
Najdeme \(y\), že \(2y \equiv 1 \pmod{7}\).
Zkoušíme hodnoty:
\(2 \times 4 = 8 \equiv 1 \pmod{7}\), inverze je \(4\).
Vynásobíme kongruenci \(4\):
\(x \equiv 3 \times 4 = 12 \equiv 5 \pmod{7}\).
Řešení je tedy \(x \equiv 5 \pmod{7}\).
20. Určete všechna řešení kongruence \(x^2 \equiv 9 \pmod{20}\).
Řešení příkladu:
Protože \(20 = 4 \times 5\), použijeme Čínskou větu o zbytcích.
Najdeme řešení pro \(x^2 \equiv 9 \pmod{4}\) a \(x^2 \equiv 9 \pmod{5}\).
Kongruence modulo \(4\):
\(9 \equiv 1 \pmod{4}\), hledáme \(x\), že \(x^2 \equiv 1 \pmod{4}\).
Řešení: \(x \equiv 1, 3 \pmod{4}\) \((2\) řešení\()\).
Kongruence modulo \(5\):
\(9 \equiv 4 \pmod{5}\), hledáme \(x\), že \(x^2 \equiv 4 \pmod{5}\).
Řešení: \(x \equiv 2, 3 \pmod{5}\) \((2\) řešení\()\).
Celkový počet řešení je \(2 \times 2 = 4\).
Vyjmenujme je použitím Čínské věty o zbytcích.
Například pro \(x \equiv 1 \pmod{4}\), \(x \equiv 2 \pmod{5}\):
Vyjádříme \(x = 1 + 4k\), najdeme \(k\), aby \(1 + 4k \equiv 2 \pmod{5}\).
\(4k \equiv 1 \pmod{5}\).
Protože \(4 \equiv -1 \pmod{5}\), máme \(-k \equiv 1 \pmod{5} \Rightarrow k \equiv -1 \equiv 4 \pmod{5}\).
Nejmenší řešení je \(k=4\), tedy \(x=1+4 \times 4=17\).
Podobně najdeme ostatní 3 řešení: \(x \equiv 3, 7, 13, 17 \pmod{20}\).
21. Vyřešte kongruenci \(42x \equiv 30 \pmod{70}\).
Řešení příkladu:
Zjistíme \(\gcd(42, 70)\).
\(\gcd(42, 70) = 14\).
Podmínka existence řešení: \(14\) musí dělit \(30\), což neplatí, takže kongruence nemá řešení.
22. Vyřešte kongruenci \(56x \equiv 12 \pmod{84}\).
Řešení příkladu:
Zjistíme \(\gcd(56, 84)\).
\(\gcd(56, 84) = 28\).
Podmínka existence řešení: \(28\) musí dělit \(12\), což neplatí, takže kongruence nemá řešení.
23. Vyřešte kongruenci \(35x \equiv 20 \pmod{100}\).
Řešení příkladu:
Zjistíme \(\gcd(35, 100) = 5\).
Podmínka existence řešení: \(5\) musí dělit \(20\), což platí.
Podělíme kongruenci \(5\):
\(7x \equiv 4 \pmod{20}\).
Protože \(\gcd(7, 20) = 1\), inverze \(7\) modulo \(20\) existuje.
Hledáme \(y\), aby \(7y \equiv 1 \pmod{20}\).
Zkoušíme hodnoty: \(7 \times 3 = 21 \equiv 1 \pmod{20}\), takže inverze je \(3\).
Vynásobíme obě strany rovnice \(3\):
\(x \equiv 4 \times 3 = 12 \pmod{20}\).
Protože jsme modulus dělili \(5\), máme \(5\) řešení mod \(100\):
\(x \equiv 12 + 20k, k = 0, 1, 2, 3, 4\).
Řešení jsou tedy \(x \equiv 12, 32, 52, 72, 92 \pmod{100}\).
24. Vyřešte soustavu kongruencí:
\(x \equiv 3 \pmod{7}\),
\(x \equiv 4 \pmod{9}\).
Řešení příkladu:
Moduly \(7\) a \(9\) jsou nesoudělné, použijeme Čínskou větu o zbytcích.
Napišme \(x = 3 + 7k\).
Dosadíme do druhé kongruence:
\(3 + 7k \equiv 4 \pmod{9}\).
\(7k \equiv 1 \pmod{9}\).
Hledáme inverzi \(7\) modulo \(9\):
\(7 \times 4 = 28 \equiv 1 \pmod{9}\), tedy inverze je \(4\).
Vynásobíme rovnici \(4\):
\(k \equiv 4 \pmod{9}\).
Nejmenší řešení pro \(k\) je \(4\), tedy \(x = 3 + 7 \times 4 = 31\).
Obecné řešení modulo \(7 \times 9 = 63\) je:
\(x \equiv 31 \pmod{63}\).
25. Vyřešte kongruenci \(15x^2 \equiv 5 \pmod{35}\).
Řešení příkladu:
Nejprve zkusíme zjednodušit kongruenci. Zjistíme \(\gcd(15, 35) = 5\).
Podmínka existence řešení: \(5\) musí dělit \(5\), což platí.
Podělíme kongruenci \(5\):
\(3x^2 \equiv 1 \pmod{7}\).
Nyní hledáme \(x\), které splňuje \(3x^2 \equiv 1 \pmod{7}\).
Protože \(\gcd(3,7) = 1\), existuje inverze \(3\) modulo \(7\).
Najdeme ji: \(3 \times 5 = 15 \equiv 1 \pmod{7}\), tedy inverze je \(5\).
Vynásobíme obě strany rovnice \(5\):
\(x^2 \equiv 5 \pmod{7}\).
Nyní zkoušíme všechny zbylé hodnoty \(x = 0, 1, \ldots, 6\):
\(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4\), \(3^2 = 9 \equiv 2\), \(4^2 = 16 \equiv 2\), \(5^2 = 25 \equiv 4\), \(6^2 = 36 \equiv 1\).
Žádné \(x\) nemá druhou mocninu rovnou \(5\) modulo \(7\), tedy kongruence nemá řešení.
26. Vyřešte soustavu kongruencí:
\(x \equiv 2 \pmod{5}\),
\(x \equiv 3 \pmod{11}\).
Řešení příkladu:
Moduly \(5\) a \(11\) jsou nesoudělné, použijeme Čínskou větu o zbytcích.
Napišme \(x = 2 + 5k\).
Dosadíme do druhé kongruence:
\(2 + 5k \equiv 3 \pmod{11}\).
\(5k \equiv 1 \pmod{11}\).
Hledáme inverzi \(5\) modulo \(11\):
\(5 \times 9 = 45 \equiv 1 \pmod{11}\), tedy inverze je \(9\).
Vynásobíme rovnici \(9\):
\(k \equiv 9 \pmod{11}\).
Nejmenší řešení pro \(k\) je \(9\), tedy \(x = 2 + 5 \times 9 = 47\).
Obecné řešení modulo \(5 \times 11 = 55\) je:
\(x \equiv 47 \pmod{55}\).
27. Vyřešte kongruenci \(11x \equiv 7 \pmod{33}\).
Řešení příkladu:
Zjistíme \(\gcd(11, 33) = 11\).
Podmínka existence řešení: \(11\) musí dělit \(7\), což neplatí, tudíž kongruence nemá řešení.
28. Vyřešte kongruenci \(9x \equiv 6 \pmod{15}\).
Řešení příkladu:
Zjistíme \(\gcd(9, 15) = 3\).
Podmínka existence řešení: \(3\) musí dělit \(6\), což platí.
Podělíme kongruenci \(3\):
\(3x \equiv 2 \pmod{5}\).
Protože \(\gcd(3,5) = 1\), inverze \(3\) modulo \(5\) existuje.
Najdeme ji: \(3 \times 2 = 6 \equiv 1 \pmod{5}\), tedy inverze je \(2\).
Vynásobíme obě strany rovnice \(2\):
\(x \equiv 2 \times 2 = 4 \pmod{5}\).
Protože jsme modulus dělili \(3\), máme \(3\) řešení mod \(15\):
\(x \equiv 4 + 5k, k = 0, 1, 2\).
Řešení jsou tedy \(x \equiv 4, 9, 14 \pmod{15}\).
29. Vyřešte kongruenci \(7x^2 \equiv 14 \pmod{21}\).
Řešení příkladu:
Zjistíme \(\gcd(7, 21) = 7\).
Podmínka existence řešení: \(7\) musí dělit \(14\), což platí.
Podělíme kongruenci \(7\):
\(x^2 \equiv 2 \pmod{3}\).
Vyzkoušíme hodnoty \(x = 0, 1, 2\) modulo \(3\):
\(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4 \equiv 1 \pmod{3}\).
Není \(x\), který by splňoval \(x^2 \equiv 2 \pmod{3}\), tudíž kongruence nemá řešení.
30. Vyřešte kongruenci \(8x \equiv 12 \pmod{28}\).
Řešení příkladu:
Zjistíme \(\gcd(8, 28) = 4\).
Podmínka existence řešení: \(4\) musí dělit \(12\), což platí.
Podělíme kongruenci \(4\):
\(2x \equiv 3 \pmod{7}\).
Protože \(\gcd(2, 7) = 1\), inverze \(2\) modulo \(7\) existuje.
Najdeme ji: \(2 \times 4 = 8 \equiv 1 \pmod{7}\), tedy inverze je \(4\).
Vynásobíme obě strany rovnice \(4\):
\(x \equiv 3 \times 4 = 12 \equiv 5 \pmod{7}\).
Protože jsme modulus dělili \(4\), máme \(4\) řešení mod \(28\):
\(x \equiv 5 + 7k, k = 0, 1, 2, 3\).
Řešení jsou tedy \(x \equiv 5, 12, 19, 26 \pmod{28}\).
31. Vyřešte kongruenci \(18x \equiv 24 \pmod{30}\).
Řešení příkladu:
Zjistíme \(\gcd(18, 30) = 6\).
Podmínka existence řešení: \(6\) musí dělit \(24\), což platí.
Podělíme kongruenci \(6\):
\(3x \equiv 4 \pmod{5}\).
Protože \(\gcd(3,5) = 1\), inverze \(3\) modulo \(5\) existuje.
Najdeme ji: \(3 \times 2 = 6 \equiv 1 \pmod{5}\), tedy inverze je \(2\).
Vynásobíme obě strany rovnice \(2\):
\(x \equiv 4 \times 2 = 8 \equiv 3 \pmod{5}\).
Protože jsme modulus dělili \(6\), máme \(6\) řešení mod \(30\):
\(x \equiv 3 + 5k, k = 0, 1, 2, 3, 4, 5\).
Řešení jsou tedy \(x \equiv 3, 8, 13, 18, 23, 28 \pmod{30}\).
32. Vyřešte kongruenci \(13x \equiv 1 \pmod{27}\).
Řešení příkladu:
Zjistíme \(\gcd(13, 27) = 1\), tedy inverze \(13\) modulo \(27\) existuje.
Najdeme inverzi pomocí rozšířeného Eukleidova algoritmu.
Vyjádříme \(1\) jako kombinaci \(13\) a \(27\):
\(27 = 13 \times 2 + 1\)
\(\Rightarrow 1 = 27 – 13 \times 2\)
Inverze \(13\) modulo \(27\) je tedy \(-2 \equiv 25 \pmod{27}\).
Vynásobíme kongruenci inverzí:
\(x \equiv 1 \times 25 = 25 \pmod{27}\).
33. Vyřešte kongruenci \(24x \equiv 16 \pmod{40}\).
Řešení příkladu:
Zjistíme \(\gcd(24, 40) = 8\).
Podmínka existence řešení: \(8\) musí dělit \(16\), což platí.
Podělíme kongruenci \(8\):
\(3x \equiv 2 \pmod{5}\).
Protože \(\gcd(3,5) = 1\), inverze \(3\) modulo \(5\) existuje.
Najdeme ji: \(3 \times 2 = 6 \equiv 1 \pmod{5}\), inverze je \(2\).
Vynásobíme obě strany rovnice \(2\):
\(x \equiv 2 \times 2 = 4 \pmod{5}\).
Protože jsme modulus dělili \(8\), máme \(8\) řešení mod \(40\):
\(x \equiv 4 + 5k, k = 0, 1, 2, 3, 4, 5, 6, 7\).
Řešení jsou tedy \(x \equiv 4, 9, 14, 19, 24, 29, 34, 39 \pmod{40}\).
34. Vyřešte kongruenci \(7x \equiv 14 \pmod{49}\).
Řešení příkladu:
Zjistíme \(\gcd(7, 49) = 7\).
Podmínka existence řešení: \(7\) musí dělit \(14\), což platí.
Podělíme kongruenci 7:
\(x \equiv 2 \pmod{7}\).
Protože jsme modulus dělili \(7\), máme \(7\) řešení mod \(49\):
\(x \equiv 2 + 7k, k = 0, 1, \ldots, 6\).
Řešení jsou tedy \(x \equiv 2, 9, 16, 23, 30, 37, 44 \pmod{49}\).
35. Vyřešte kongruenci \(x^2 \equiv 10 \pmod{13}\).
Řešení příkladu:
Zkoušíme hodnoty \(x = 0, 1, \ldots, 12\) modulo \(13\):
\(0^2=0\), \(1^2=1\), \(2^2=4\), \(3^2=9\), \(4^2=16 \equiv 3\), \(5^2=25 \equiv 12\), \(6^2=36 \equiv 10\).
Vidíme, že \(6^2 \equiv 10 \pmod{13}\), řešení existuje.
Symetricky platí, že pokud \(x\) je řešení, pak \(13 – x\) je také řešení:
\(13 – 6 = 7\), ověříme \(7^2 = 49 \equiv 10 \pmod{13}\).
Řešení jsou tedy \(x \equiv 6, 7 \pmod{13}\).
36. Vyřešte soustavu kongruencí:
\(x \equiv 1 \pmod{4}\),
\(x \equiv 3 \pmod{5}\),
\(x \equiv 2 \pmod{7}\).
Řešení příkladu:
Moduly jsou vzájemně nesoudělné, použijeme Čínskou větu o zbytcích.
Napišme \(x = 1 + 4a\).
Dosadíme do druhé kongruence:
\(1 + 4a \equiv 3 \pmod{5}\).
\(4a \equiv 2 \pmod{5}\).
Inverze \(4\) modulo \(5\) je \(4\), protože \(4 \times 4 = 16 \equiv 1 \pmod{5}\).
Vynásobíme obě strany \(4\):
\(a \equiv 8 \equiv 3 \pmod{5}\).
Napišme \(a = 3 + 5b\).
Dosadíme do třetí kongruence:
\(x = 1 + 4(3 + 5b) = 1 + 12 + 20b = 13 + 20b\).
\(13 + 20b \equiv 2 \pmod{7}\).
\(20b + 13 \equiv 2 \pmod{7} \Rightarrow 20b \equiv -11 \equiv 3 \pmod{7}\).
\(20 \equiv 6 \pmod{7}\), tedy:
\(6b \equiv 3 \pmod{7}\).
Inverze \(6\) modulo \(7\) je \(6\), protože \(6 \times 6 = 36 \equiv 1 \pmod{7}\).
Vynásobíme obě strany \(6\):
\(b \equiv 18 \equiv 4 \pmod{7}\).
Nejmenší řešení je pro \(b = 4\):
\(x = 13 + 20 \times 4 = 13 + 80 = 93\).
Celkové řešení je tedy:
\(x \equiv 93 \pmod{140}\) (protože \(4 \times 5 \times 7 = 140\)).
37. Vyřešte kongruenci \(15x \equiv 1 \pmod{26}\).
Řešení příkladu:
Zjistíme \(\gcd(15, 26) = 1\), inverze existuje.
Použijeme rozšířený Eukleidův algoritmus:
\(26 = 15 × 1 + 11\)
\(15 = 11 × 1 + 4\)
\(11 = 4 × 2 + 3\)
\(4 = 3 × 1 + 1\)
\(3 = 1 × 3 + 0\)
Zpětně:
\(1 = 4 – 3 × 1\)
\(3 = 11 – 4 × 2\)
\(1 = 4 – (11 – 4 × 2) × 1 = 4 × 3 – 11 × 1\)
\(4 = 15 – 11 × 1\)
\(1 = (15 – 11 × 1) × 3 – 11 × 1 = 15 × 3 – 11 × 4\)
\(11 = 26 – 15 × 1\)
\(1 = 15 × 3 – (26 – 15 × 1) × 4 = 15 × 7 – 26 × 4\)
Inverze \(15\) modulo \(26\) je tedy \(7\).
Vynásobíme kongruenci inverzí:
\(x \equiv 7 \pmod{26}\).
38. Vyřešte kongruenci \(x^3 \equiv 1 \pmod{7}\).
Řešení příkladu:
Vyzkoušíme hodnoty \(x = 0, 1, \ldots, 6\) modulo \(7\):
\(0^3=0\), \(1^3=1\), \(2^3=8 \equiv 1\), \(3^3=27 \equiv 6\), \(4^3=64 \equiv 1\), \(5^3=125 \equiv 6\), \(6^3=216 \equiv 6\).
Řešení jsou tedy \(x \equiv 1, 2, 4 \pmod{7}\).
39. Vyřešte kongruenci \(35x \equiv 10 \pmod{50}\).
Řešení příkladu:
Zjistíme \(\gcd(35, 50) = 5\).
Podmínka existence řešení: \(5\) musí dělit \(10\), což platí.
Podělíme kongruenci \(5\):
\(7x \equiv 2 \pmod{10}\).
Protože \(\gcd(7, 10) = 1\), inverze \(7\) modulo \(10\) existuje.
Najdeme ji: \(7 \times 3 = 21 \equiv 1 \pmod{10}\), inverze je \(3\).
Vynásobíme obě strany rovnice \(3\):
\(x \equiv 2 \times 3 = 6 \pmod{10}\).
Protože jsme modulus dělili \(5\), máme \(5\) řešení mod \(50\):
\(x \equiv 6 + 10k, k = 0, 1, 2, 3, 4\).
Řešení jsou tedy \(x \equiv 6, 16, 26, 36, 46 \pmod{50}\).
40. Vyřešte kongruenci \(\,2x + 3 \equiv 5x + 1 \pmod{11}\,\).
Řešení příkladu:
Upravíme rovnici:
\(\,2x + 3 \equiv 5x + 1 \pmod{11}\,\)
\(\,2x – 5x \equiv 1 – 3 \pmod{11}\,\)
\(\,-3x \equiv -2 \pmod{11}\,\)
Vynásobíme obě strany \(\,-1\):
\(\,3x \equiv 2 \pmod{11}\,\).
Najdeme inverzi \(\,3\) modulo \(\,11\):
\(\,3 \times 4 = 12 \equiv 1 \pmod{11}\,\), inverze je \(\,4\).
Vynásobíme obě strany \(\,4\):
\(\,x \equiv 2 \times 4 = 8 \pmod{11}\,\).
41. Vyřešte kongruenci \(\,42x \equiv 30 \pmod{70}\,\).
Řešení příkladu:
Nejprve zjistíme \(\,\gcd(42, 70)\,\).
\(\,\gcd(42, 70) = 14\,\).
Podmínka existence řešení: \(\,14\) musí dělit \(\,30\), což není pravda, protože \(\,14 \nmid 30\).
Tedy kongruence nemá žádné řešení.
42. Vyřešte kongruenci \(\,42x \equiv 28 \pmod{70}\,\).
Řešení příkladu:
Zjistíme \(\,\gcd(42, 70) = 14\,\).
Podmínka existence řešení: \(\,14\) musí dělit \(\,28\), což platí.
Podělíme kongruenci \(\,14\):
\(\,3x \equiv 2 \pmod{5}\,\).
Protože \(\,\gcd(3, 5) = 1\,\), existuje inverze \(\,3\) modulo \(\,5\).
Najdeme ji:
Hledáme \(\,y\), aby \(\,3y \equiv 1 \pmod{5}\,\).
Zkoušíme hodnoty: \(\,3 \times 2 = 6 \equiv 1 \pmod{5}\,\), inverze je \(\,2\).
Vynásobíme obě strany rovnice \(\,2\):
\(\,x \equiv 2 \times 2 = 4 \pmod{5}\,\).
Protože jsme modulus dělili \(\,14\), máme \(\,14\) řešení mod \(\,70\):
\(\,x \equiv 4 + 5k,\, k = 0, 1, \ldots, 13\,\).
Řešení jsou tedy \(\,x \equiv 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59, 64, 69 \pmod{70}\,\).
43. Vyřešte kongruenci \(\,11x^2 \equiv 4 \pmod{23}\,\).
Řešení příkladu:
Nejprve vynásobíme obě strany rovnice inverzí \(\,11\) modulo \(\,23\).
Zjistíme inverzi \(\,11\) modulo \(\,23\) pomocí rozšířeného Eukleidova algoritmu:
\(\,23 = 11 \times 2 + 1\,\)
\(\,\Rightarrow 1 = 23 – 11 \times 2\,\)
Inverze \(\,11\) modulo \(\,23\) je tedy \(\,-2 \equiv 21 \pmod{23}\,\).
Vynásobíme kongruenci \(\,21\):
\(\,x^2 \equiv 4 \times 21 = 84 \equiv 84 – 69 = 15 \pmod{23}\,\).
Musíme najít \(\,x\) tak, aby \(\,x^2 \equiv 15 \pmod{23}\,\).
Vyzkoušíme \(\,x = 0, 1, \ldots, 22\):
\(\,0^2=0\), \(\,1^2=1\), \(\,2^2=4\), \(\,3^2=9\), \(\,4^2=16\), \(\,5^2=25 \equiv 2\), \(\,6^2=36 \equiv 13\), \(\,7^2=49 \equiv 3\), \(\,8^2=64 \equiv 18\), \(\,9^2=81 \equiv 12\), \(\,10^2=100 \equiv 8\), \(\,11^2=121 \equiv 6\), \(\,12^2=144 \equiv 6\), \(\,13^2=169 \equiv 8\), \(\,14^2=196 \equiv 12\), \(\,15^2=225 \equiv 18\), \(\,16^2=256 \equiv 3\), \(\,17^2=289 \equiv 13\), \(\,18^2=324 \equiv 2\), \(\,19^2=361 \equiv 16\), \(\,20^2=400 \equiv 9\), \(\,21^2=441 \equiv 4\), \(\,22^2=484 \equiv 1\).
Žádné \(\,x\) nemá čtverec \(\,15\) modulo \(\,23\).
Tedy kongruence nemá řešení.
44. Vyřešte soustavu kongruencí:
\(\,x \equiv 2 \pmod{3}\,\),
\(\,x \equiv 3 \pmod{4}\,\),
\(\,x \equiv 1 \pmod{5}\,\).
Řešení příkladu:
Moduly jsou vzájemně nesoudělné, použijeme Čínskou větu o zbytcích.
Napišme \(\,x = 2 + 3a\,\).
Dosadíme do druhé kongruence:
\(\,2 + 3a \equiv 3 \pmod{4}\,\).
\(\,3a \equiv 1 \pmod{4}\,\).
Protože \(\,3 \equiv -1 \pmod{4}\), rovnice je ekvivalentní
\(\,-a \equiv 1 \pmod{4} \Rightarrow a \equiv -1 \equiv 3 \pmod{4}\,\).
Napišme \(\,a = 3 + 4b\,\).
Dosadíme do třetí kongruence:
\(\,x = 2 + 3(3 + 4b) = 2 + 9 + 12b = 11 + 12b\,\).
\(\,11 + 12b \equiv 1 \pmod{5}\,\).
\(\,12b + 11 \equiv 1 \pmod{5} \Rightarrow 12b \equiv -10 \equiv 0 \pmod{5}\,\).
Protože \(\,12 \equiv 2 \pmod{5}\), máme:
\(\,2b \equiv 0 \pmod{5}\,\).
Řešením je \(\,b \equiv 0 \pmod{5}\,\).
Nejmenší řešení je tedy pro \(\,b=0\):
\(\,x = 11 + 12 \times 0 = 11\,\).
Celkové řešení:
\(\,x \equiv 11 \pmod{60}\,\) (protože \(\,3 \times 4 \times 5 = 60\)).
45. Vyřešte kongruenci \(7x + 5 \equiv 3x + 17 \pmod{20}\).
Řešení příkladu:
Upravíme rovnici:
\(7x + 5 \equiv 3x + 17 \pmod{20}\)
\(7x – 3x \equiv 17 – 5 \pmod{20}\)
\(4x \equiv 12 \pmod{20}\)
Zjistíme \(\gcd(4, 20) = 4\).
Podmínka existence řešení: \(4\) musí dělit \(12\), což platí.
Podělíme kongruenci \(4\):
\(x \equiv 3 \pmod{5}\)
Protože jsme modulus dělili \(4\), máme \(4\) řešení mod \(20\):
\(x \equiv 3 + 5k, \; k = 0, 1, 2, 3\)
Řešení jsou tedy \(x \equiv 3, 8, 13, 18 \pmod{20}\).
46. Najděte všechna řešení kongruence \(x^2 + x + 1 \equiv 0 \pmod{7}\).
Řešení příkladu:
Pro \(x \in \{0, 1, 2, 3, 4, 5, 6\}\) spočítáme hodnotu výrazu modulo \(7\):
\(x = 0: \; 0^2 + 0 + 1 = 1 \neq 0\)
\(x = 1: \; 1 + 1 + 1 = 3 \neq 0\)
\(x = 2: \; 4 + 2 + 1 = 7 \equiv 0 \pmod{7}\) – řešení
\(x = 3: \; 9 + 3 + 1 = 13 \equiv 6 \neq 0\)
\(x = 4: \; 16 + 4 + 1 = 21 \equiv 0 \pmod{7}\) – řešení
\(x = 5: \; 25 + 5 + 1 = 31 \equiv 3 \neq 0\)
\(x = 6: \; 36 + 6 + 1 = 43 \equiv 1 \neq 0\)
Řešení jsou tedy \(x \equiv 2, 4 \pmod{7}\).
47. Vyřešte kongruenci \(15x \equiv 25 \pmod{40}\).
Řešení příkladu:
Zjistíme \(\gcd(15, 40) = 5\).
Podmínka existence řešení: \(5\) musí dělit \(25\), což platí.
Podělíme kongruenci \(5\):
\(3x \equiv 5 \pmod{8}\)
Protože \(\gcd(3, 8) = 1\), existuje inverze \(3\) modulo \(8\).
Najdeme ji:
Hledáme \(y\), aby \(3y \equiv 1 \pmod{8}\).
Zkoušíme hodnoty: \(3 \times 3 = 9 \equiv 1 \pmod{8}\), inverze je \(3\).
Vynásobíme obě strany rovnice \(3\):
\(x \equiv 5 \times 3 = 15 \equiv 7 \pmod{8}\)
Protože jsme modulus dělili \(5\), máme \(5\) řešení mod \(40\):
\(x \equiv 7 + 8k, \; k = 0, 1, 2, 3, 4\)
Řešení jsou tedy \(x \equiv 7, 15, 23, 31, 39 \pmod{40}\).
48. Vyřešte kongruenci \(x^3 \equiv 2 \pmod{11}\).
Řešení příkladu:
Budeme zkoušet \(x = 0, 1, \ldots, 10\), zda splňují \(x^3 \equiv 2 \pmod{11}\).
\(0^3 = 0 \neq 2\)
\(1^3 = 1 \neq 2\)
\(2^3 = 8 \neq 2\)
\(3^3 = 27 \equiv 5 \neq 2\)
\(4^3 = 64 \equiv 9 \neq 2\)
\(5^3 = 125 \equiv 4 \neq 2\)
\(6^3 = 216 \equiv 7 \neq 2\)
\(7^3 = 343 \equiv 2 \pmod{11}\) – řešení
\(8^3 = 512 \equiv 6 \neq 2\)
\(9^3 = 729 \equiv 3 \neq 2\)
\(10^3 = 1000 \equiv 10 \neq 2\)
Jediné řešení je tedy \(x \equiv 7 \pmod{11}\).
49. Vyřešte kongruenci \(9x \equiv 15 \pmod{24}\).
Řešení příkladu:
Zjistíme \(\gcd(9, 24) = 3\).
Podmínka existence řešení: \(3\) musí dělit \(15\), což platí.
Podělíme kongruenci \(3\):
\(3x \equiv 5 \pmod{8}\)
Protože \(\gcd(3, 8) = 1\), existuje inverze \(3\) modulo \(8\).
Najdeme ji:
Hledáme \(y\), aby \(3y \equiv 1 \pmod{8}\).
Zkoušíme hodnoty: \(3 \times 3 = 9 \equiv 1 \pmod{8}\), inverze je \(3\).
Vynásobíme obě strany rovnice \(3\):
\(x \equiv 5 \times 3 = 15 \equiv 7 \pmod{8}\)
Protože jsme modulus dělili \(3\), máme \(3\) řešení mod \(24\):
\(x \equiv 7 + 8k, \; k = 0, 1, 2\)
Řešení jsou tedy \(x \equiv 7, 15, 23 \pmod{24}\).
50. Vyřešte kongruenci \(2x \equiv 5 \pmod{7}\).
Řešení příkladu:
Protože \(\gcd(2,7) = 1\), inverze \(2\) modulo \(7\) existuje.
Najdeme ji:
Hledáme \(y\), aby \(2y \equiv 1 \pmod{7}\).
Zkoušíme hodnoty: \(2 \times 4 = 8 \equiv 1 \pmod{7}\), inverze je \(4\).
Vynásobíme obě strany rovnice \(4\):
\(x \equiv 5 \times 4 = 20 \equiv 6 \pmod{7}\).
Řešení je tedy \(x \equiv 6 \pmod{7}\).
51. Vyřešte kongruenci \(x^2 \equiv 16 \pmod{21}\).
Řešení příkladu:
Protože \(21 = 3 \times 7\), použijeme Čínskou větu o zbytcích.
Řešíme soustavu:
\(x^2 \equiv 16 \pmod{3}\),
\(x^2 \equiv 16 \pmod{7}\).
Modulo \(3\):
Protože \(16 \equiv 1 \pmod{3}\), máme \(x^2 \equiv 1 \pmod{3}\).
Řešení jsou \(x \equiv 1, 2 \pmod{3}\).
Modulo \(7\):
\(16 \equiv 2 \pmod{7}\), tedy \(x^2 \equiv 2 \pmod{7}\).
Zkoušíme \(x=0,\ldots,6\):
\(0^2=0\), \(1^2=1\), \(2^2=4\), \(3^2=9 \equiv 2\) – řešení, \(4^2=16 \equiv 2\) – řešení, \(5^2=25 \equiv 4\), \(6^2=36 \equiv 1\).
Řešení jsou tedy \(x \equiv 3,4 \pmod{7}\).
Soustava má čtyři možné kombinace:
1) \(x \equiv 1 \pmod{3}\) a \(x \equiv 3 \pmod{7}\),
2) \(x \equiv 1 \pmod{3}\) a \(x \equiv 4 \pmod{7}\),
3) \(x \equiv 2 \pmod{3}\) a \(x \equiv 3 \pmod{7}\),
4) \(x \equiv 2 \pmod{3}\) a \(x \equiv 4 \pmod{7}\).
Řešíme jednotlivé případy pomocí Čínské věty o zbytcích:
Pro 1): \(x = 1 + 3k\), vložíme do druhé rovnice:
\(1 + 3k \equiv 3 \pmod{7} \Rightarrow 3k \equiv 2 \pmod{7}\).
Inverze \(3\) modulo \(7\) je \(5\), tedy \(k \equiv 2 \times 5 = 10 \equiv 3 \pmod{7}\).
Nejmenší řešení: \(k=3\), tedy \(x = 1 + 3 \times 3 = 10\).
Obecně \(x \equiv 10 \pmod{21}\).
Pro 2): \(x = 1 + 3k\), vložíme do druhé rovnice:
\(1 + 3k \equiv 4 \pmod{7} \Rightarrow 3k \equiv 3 \pmod{7}\).
\(k \equiv 3 \times 5 = 15 \equiv 1 \pmod{7}\), tedy \(x = 1 + 3 \times 1 = 4\).
Obecně \(x \equiv 4 \pmod{21}\).
Pro 3): \(x = 2 + 3k\), vložíme do druhé rovnice:
\(2 + 3k \equiv 3 \pmod{7} \Rightarrow 3k \equiv 1 \pmod{7}\).
\(k \equiv 1 \times 5 = 5 \pmod{7}\), tedy \(x = 2 + 3 \times 5 = 17\).
Obecně \(x \equiv 17 \pmod{21}\).
Pro 4): \(x = 2 + 3k\), vložíme do druhé rovnice:
\(2 + 3k \equiv 4 \pmod{7} \Rightarrow 3k \equiv 2 \pmod{7}\).
\(k \equiv 2 \times 5 = 10 \equiv 3 \pmod{7}\), tedy \(x = 2 + 3 \times 3 = 11\).
Obecně \(x \equiv 11 \pmod{21}\).
Řešení jsou tedy \(x \equiv 4, 10, 11, 17 \pmod{21}\).
52. Vyřešte kongruenci \(7x + 3 \equiv 2x + 8 \pmod{15}\).
Řešení příkladu:
Převedeme všechny členy na jednu stranu:
\(7x + 3 \equiv 2x + 8 \pmod{15} \Rightarrow 7x – 2x \equiv 8 – 3 \pmod{15}\).
\(5x \equiv 5 \pmod{15}\).
Zjistíme \(\gcd(5,15) = 5\).
Podmínka existence řešení: \(5\) dělí \(5\), což platí.
Podělíme kongruenci \(5\):
\(x \equiv 1 \pmod{3}\).
Protože jsme modulus dělili \(5\), máme \(5\) řešení mod \(15\):
\(x \equiv 1 + 3k, k=0,1,2,3,4\).
Řešení jsou tedy \(x \equiv 1, 4, 7, 10, 13 \pmod{15}\).
53. Vyřešte kongruenci \(4x^2 \equiv 1 \pmod{9}\).
Řešení příkladu:
Pro \(x = 0,1,\ldots,8\) spočítáme hodnotu \(4x^2 \pmod{9}\) a zjistíme, kdy je rovna \(1\).
\(0: 4 \times 0 = 0 \neq 1\)
\(1: 4 \times 1 = 4 \neq 1\)
\(2: 4 \times 4 = 16 \equiv 7 \neq 1\)
\(3: 4 \times 9 = 36 \equiv 0 \neq 1\)
\(4: 4 \times 16 = 64 \equiv 1 \pmod{9}\) – řešení
\(5: 4 \times 25 = 100 \equiv 1 \pmod{9}\) – řešení
\(6: 4 \times 36 = 144 \equiv 0 \neq 1\)
\(7: 4 \times 49 = 196 \equiv 7 \neq 1\)
\(8: 4 \times 64 = 256 \equiv 4 \neq 1\)
Řešení jsou tedy \(x \equiv 4, 5 \pmod{9}\).
54. Vyřešte kongruenci \(x^2 + 3x + 2 \equiv 0 \pmod{13}\).
Řešení příkladu:
Rovnici lze přepsat jako:
\(x^2 + 3x + 2 \equiv 0 \pmod{13}\).
Najdeme diskriminant:
\(\Delta = 3^2 – 4 \cdot 1 \cdot 2 = 9 – 8 = 1\).
Řešení jsou:
\(x \equiv ␌ rac{-3 \pm 1}{2} \pmod{13}\).
Najdeme inverzi \(2\) modulo \(13\): \(2 \cdot 7 \equiv 1 \pmod{13}\).
\(x \equiv (-3+1) \cdot 7 = -2 \cdot 7 = -14 \equiv 12 \pmod{13}\)
\(x \equiv (-3-1) \cdot 7 = -4 \cdot 7 = -28 \equiv 11 \pmod{13}\)
Řešení jsou tedy \(x \equiv 11, 12 \pmod{13}\).
55. Vyřešte kongruenci \(12x \equiv 18 \pmod{30}\).
Řešení příkladu:
\(\gcd(12,30) = 6\), 6 dělí 18, řešení existuje.
Podělíme kongruenci 6: \(2x \equiv 3 \pmod{5}\).
Inverze 2 modulo 5 je 3: \(x \equiv 3 \cdot 3 = 9 \equiv 4 \pmod{5}\).
Protože dělený modulus 6, řešení mod 30:
\(x \equiv 4 + 5k, k=0,1,…,5\)
Řešení jsou tedy \(x \equiv 4, 9, 14, 19, 24, 29 \pmod{30}\).
56. Vyřešte kongruenci \(18x \equiv 30 \pmod{42}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(18,42)\).
\(\gcd(18,42) = 6\).
Podmínka existence řešení: \(6\) musí dělit \(30\), což platí.
Podělíme kongruenci \(6\):
\(3x \equiv 5 \pmod{7}\).
Zjistíme inverzi \(3\) modulo \(7\). Hledáme \(y\), aby \(3y \equiv 1 \pmod{7}\).
Zkoušíme: \(3 \times 5 = 15 \equiv 1 \pmod{7}\), inverze je \(5\).
Vynásobíme obě strany rovnice \(5\):
\(x \equiv 5 \times 5 = 25 \equiv 4 \pmod{7}\).
Protože jsme modulus dělili \(6\), máme \(6\) řešení mod \(42\):
\(x \equiv 4 + 7k, k = 0,1,2,3,4,5\).
Řešení jsou tedy \(x \equiv 4, 11, 18, 25, 32, 39 \pmod{42}\).
57. Najděte všechna \(x\) taková, že \(x^2 \equiv 16 \pmod{35}\).
Řešení příkladu:
Rozložíme modul na součin prvočísel: \(35 = 5 \times 7\).
Vyřešíme soustavu:
\(x^2 \equiv 16 \pmod{5}\) a \(x^2 \equiv 16 \pmod{7}\).
Nejprve modulo 5:
Protože \(16 \equiv 1 \pmod{5}\), hledáme \(x^2 \equiv 1 \pmod{5}\).
Řešení: \(x \equiv 1, 4 \pmod{5}\).
Modulo 7:
\(16 \equiv 2 \pmod{7}\), hledáme \(x^2 \equiv 2 \pmod{7}\).
Zkoušíme hodnoty \(x=0,1,\ldots,6\):
\(0^2=0\), \(1^2=1\), \(2^2=4\), \(3^2=9 \equiv 2\), \(4^2=16 \equiv 2\), \(5^2=25 \equiv 4\), \(6^2=36 \equiv 1\).
Řešení jsou \(x \equiv 3,4 \pmod{7}\).
Máme 4 soustavy kongruencí:
1) \(x \equiv 1 \pmod{5}, x \equiv 3 \pmod{7}\)
2) \(x \equiv 1 \pmod{5}, x \equiv 4 \pmod{7}\)
3) \(x \equiv 4 \pmod{5}, x \equiv 3 \pmod{7}\)
4) \(x \equiv 4 \pmod{5}, x \equiv 4 \pmod{7}\)
Řešíme první soustavu:
Nechť \(x = 1 + 5k\), dosadíme do druhé:
\(1 + 5k \equiv 3 \pmod{7} \Rightarrow 5k \equiv 2 \pmod{7}\).
Inverze \(5\) modulo \(7\) je \(3\), protože \(5 \times 3 = 15 \equiv 1\).
\(k \equiv 2 \times 3 = 6 \pmod{7}\).
Nejmenší řešení \(k=6\), tedy \(x=1 + 5 \times 6 = 31\).
Řešení mod \(35\): \(x \equiv 31\).
Druhá soustava:
\(x=1 + 5k\),
\(1 + 5k \equiv 4 \pmod{7} \Rightarrow 5k \equiv 3 \pmod{7}\).
\(k \equiv 3 \times 3 = 9 \equiv 2 \pmod{7}\).
\(x = 1 + 5 \times 2 = 11\), řešení mod \(35\): \(x \equiv 11\).
Třetí soustava:
\(x=4 + 5k\),
\(4 + 5k \equiv 3 \pmod{7} \Rightarrow 5k \equiv -1 \equiv 6 \pmod{7}\).
\(k \equiv 6 \times 3 = 18 \equiv 4 \pmod{7}\).
\(x=4 + 5 \times 4 = 24\), řešení mod \(35\): \(x \equiv 24\).
Čtvrtá soustava:
\(x=4 + 5k\),
\(4 + 5k \equiv 4 \pmod{7} \Rightarrow 5k \equiv 0 \pmod{7}\).
\(k \equiv 0 \pmod{7}\), tedy \(k=0\).
\(x = 4\), řešení mod \(35\): \(x \equiv 4\).
Celková řešení jsou tedy \(x \equiv 4, 11, 24, 31 \pmod{35}\).
58. Vyřešte kongruenci \(5^{x} \equiv 3 \pmod{11}\).
Řešení příkladu:
Budeme zkoušet postupné mocniny \(5\) modulo \(11\), abychom našli \(x\) takové, že \(5^{x} \equiv 3 \pmod{11}\).
\(5^1 = 5 \pmod{11}\)
\(5^2 = 25 \equiv 3 \pmod{11}\)
Už máme \(x=2\) jako řešení.
Zkontrolujeme řád \(5\) modulo \(11\) (tj. nejmenší kladné \(k\), pro které \(5^k \equiv 1 \pmod{11}\)):
\(5^3 = 5^2 \times 5 = 3 \times 5 = 15 \equiv 4 \pmod{11}\)
\(5^4 = 4 \times 5 = 20 \equiv 9 \pmod{11}\)
\(5^5 = 9 \times 5 = 45 \equiv 1 \pmod{11}\)
Řád je tedy \(5\).
Obecná řešení jsou \(x \equiv 2 \pmod{5}\), tedy \(x = 2 + 5k, k \in \mathbb{Z}\).
59. Vyřešte kongruenci \(12x + 5 \equiv 8 \pmod{17}\).
Řešení příkladu:
Převedeme všechny členy na jednu stranu:
\(12x + 5 \equiv 8 \pmod{17} \Rightarrow 12x \equiv 3 \pmod{17}\).
Zjistíme inverzi \(12\) modulo \(17\). Hledáme \(y\), aby \(12y \equiv 1 \pmod{17}\).
Zkusíme hodnoty:
\(12 \times 3 = 36 \equiv 2\),
\(12 \times 8 = 96 \equiv 11\),
\(12 \times 10 = 120 \equiv 1\).
Inverze 12 modulo 17 je tedy 10.
Vynásobíme obě strany rovnice 10:
\(x \equiv 3 \times 10 = 30 \equiv 13 \pmod{17}\).
Řešení je \(x \equiv 13 \pmod{17}\).
60. Vyřešte kongruenci \(x^3 \equiv 2 \pmod{7}\).
Řešení příkladu:
Zkoušíme všechny hodnoty \(x = 0,1,…,6\):
\(0^3 \equiv 0\), \(1^3 \equiv 1\), \(2^3 \equiv 1\), \(3^3 \equiv 6\), \(4^3 \equiv 1\), \(5^3 \equiv 6\), \(6^3 \equiv 6\)
Žádné \(x^3 \equiv 2 \pmod{7}\).
Řešení neexistuje.
61. Vyřešte kongruenci \(7x^2 + 5x + 6 \equiv 0 \pmod{13}\).
Řešení příkladu:
Rovnice má tvar \(7x^2 + 5x + 6 \equiv 0 \pmod{13}\).
Najdeme diskriminant:
\(\Delta = 5^2 – 4 \times 7 \times 6 = 25 – 168 = -143 \equiv -143 + 13 \times 11 = -143 + 143 = 0 \pmod{13}\).
Protože \(\Delta \equiv 0 \pmod{13}\), rovnice má jedno dvojnásobné řešení.
Inverze \(2 \times 7 = 14 \equiv 1 \pmod{13}\), takže inverze je \(1\).
Řešení je:
\(x \equiv \frac{-5}{2 \times 7} \equiv \frac{-5}{1} \equiv -5 \equiv 8 \pmod{13}\).
Řešení je tedy \(x \equiv 8 \pmod{13}\).
62. Najděte všechny \(x\) takové, že \(3^x \equiv 4 \pmod{13}\).
Řešení příkladu:
Zkoušíme mocniny 3 modulo 13:
\(3^1 \equiv 3\), \(3^2 \equiv 9\), \(3^3 \equiv 1\), \(3^4 \equiv 3\), \(3^5 \equiv 9\), \(3^6 \equiv 1\) …
Hodnota 4 nenastane, žádné řešení neexistuje.
63. Vyřešte kongruenci \(14x \equiv 7 \pmod{35}\).
Řešení příkladu:
Zjistíme \(\gcd(14, 35) = 7\).
Podmínka existence řešení: \(7\) musí dělit \(7\), což platí.
Podělíme kongruenci \(7\):
\(2x \equiv 1 \pmod{5}\).
Najdeme inverzi \(2\) modulo \(5\). Hledáme \(y\), že \(2y \equiv 1 \pmod{5}\).
\(2 \times 3 = 6 \equiv 1\), inverze je \(3\).
Vynásobíme obě strany 3:
\(x \equiv 3 \pmod{5}\).
Protože jsme modulus dělili \(7\), máme \(7\) řešení mod \(35\):
\(x \equiv 3 + 5k, k = 0,1,\ldots,6\).
Řešení jsou tedy \(x \equiv 3, 8, 13, 18, 23, 28, 33 \pmod{35}\).
64. Vyřešte soustavu kongruencí:
\(x \equiv 2 \pmod{3}\),
\(x \equiv 3 \pmod{4}\),
\(x \equiv 1 \pmod{5}\).
Řešení příkladu:
Moduly jsou navzájem nesoudělné, použijeme Čínskou větu o zbytcích.
Nejprve sloučíme dvě první kongruence.
\(x = 2 + 3k\).
Dosadíme do druhé:
\(2 + 3k \equiv 3 \pmod{4} \Rightarrow 3k \equiv 1 \pmod{4}\).
Inverze 3 modulo 4 je 3, protože \(3 \times 3 = 9 \equiv 1\).
\(k \equiv 3 \times 1 = 3 \pmod{4}\).
Nejmenší řešení \(k=3\), tedy \(x = 2 + 3 \times 3 = 11\).
Řešení této části je \(x \equiv 11 \pmod{12}\).
Nyní řešíme:
\(x \equiv 11 \pmod{12}\), \(x \equiv 1 \pmod{5}\).
Nechť \(x = 11 + 12t\).
\(11 + 12t \equiv 1 \pmod{5} \Rightarrow 12t \equiv -10 \equiv 0 \pmod{5}\).
\(12 \equiv 2 \pmod{5}\), takže \(2t \equiv 0 \pmod{5}\).
Protože \(\gcd(2,5)=1\), dostáváme \(t \equiv 0 \pmod{5}\).
Nejmenší řešení je \(t=0\), tedy \(x=11\).
Obecná řešení jsou \(x \equiv 11 \pmod{60}\) (protože \(12 \times 5 = 60\)).
65. Vyřešte kongruenci \(9x \equiv 27 \pmod{18}\).
Řešení příkladu:
\(\gcd(9,18)=9\), 9 dělí 27, řešení existuje.
Podělíme 9: \(x \equiv 3 \pmod{2}\).
Protože modulus byl dělen 9, máme 9 řešení mod 18:
\(x \equiv 3 + 2k, k=0,…,8\)
Řešení: \(x \equiv 3, 5, 7, 9, 11, 13, 15, 17, 1 \pmod{18}\).
66. Vyřešte kongruenci \(42x \equiv 30 \pmod{66}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(42, 66)\).
\(\gcd(42, 66) = 6\).
Podmínka existence řešení: \(6\) musí dělit \(30\), což platí.
Podělíme kongruenci \(6\):
\(7x \equiv 5 \pmod{11}\).
Protože \(\gcd(7, 11) = 1\), inverze \(7\) modulo \(11\) existuje. Najdeme ji:
Hledáme \(y\), aby \(7y \equiv 1 \pmod{11}\).
Zkoušíme hodnoty: \(7 \times 8 = 56 \equiv 1 \pmod{11}\), inverze je tedy \(8\).
Vynásobíme obě strany rovnice \(8\):
\(x \equiv 5 \times 8 = 40 \equiv 7 \pmod{11}\).
Protože jsme modulus dělili \(6\), máme \(6\) řešení mod \(66\):
\(x \equiv 7 + 11k, k = 0, 1, 2, 3, 4, 5\).
Řešení jsou tedy \(x \equiv 7, 18, 29, 40, 51, 62 \pmod{66}\).
67. Vyřešte kongruenci \(15x^2 \equiv 10 \pmod{25}\).
Řešení příkladu:
Zkoumáme kongruenci \(15x^2 \equiv 10 \pmod{25}\).
Nejprve určíme \(\gcd(15, 25) = 5\).
Podmínka existence řešení: \(5\) musí dělit \(10\), což platí.
Podělíme kongruenci \(5\):
\(3x^2 \equiv 2 \pmod{5}\).
Modul je nyní \(5\), zkoušíme všechna \(x = 0, 1, 2, 3, 4\) modulo \(5\):
\(x=0: 3 \times 0 = 0 \not\equiv 2\)
\(x=1: 3 \times 1 = 3 \not\equiv 2\)
\(x=2: 3 \times 4 = 12 \equiv 2 \pmod{5}\) správně (protože \(2^2=4\))
\(x=3: 3 \times 9 = 27 \equiv 2 \pmod{5}\) také platí (protože \(3^2=9\))
\(x=4: 3 \times 16 = 48 \equiv 3 \neq 2\)
Řešení jsou tedy \(x \equiv 2 \pmod{5}\) a \(x \equiv 3 \pmod{5}\).
Protože původní modulus je \(25\) a dělili jsme \(5\), výsledné řešení mod \(25\) jsou hodnoty tvaru:
\(x \equiv 2 + 5k, k=0,1,2,3,4\) a \(x \equiv 3 + 5k, k=0,1,2,3,4\).
68. Vyřešte kongruenci \(28x \equiv 14 \pmod{70}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(28, 70)\).
\(\gcd(28, 70) = 14\).
Podmínka existence řešení: \(14\) musí dělit \(14\), což platí.
Podělíme kongruenci \(14\):
\(2x \equiv 1 \pmod{5}\).
Protože \(\gcd(2, 5) = 1\), inverze \(2\) modulo \(5\) existuje. Najdeme ji:
Hledáme \(y\), aby \(2y \equiv 1 \pmod{5}\).
Zkoušíme hodnoty: \(2 \times 3 = 6 \equiv 1 \pmod{5}\), inverze je tedy \(3\).
Vynásobíme obě strany rovnice \(3\):
\(x \equiv 3 \times 1 = 3 \pmod{5}\).
Protože jsme modulus dělili \(14\), máme \(14\) řešení mod \(70\):
\(x \equiv 3 + 5k, k = 0, 1, …, 13\).
Řešení jsou tedy \(x \equiv 3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58, 63, 68 \pmod{70}\).
69. Vyřešte kongruenci \(x^2 \equiv 4 \pmod{21}\).
Řešení příkladu:
Kongruence je \(x^2 \equiv 4 \pmod{21}\).
Protože \(21 = 3 \times 7\), použijeme Čínskou větu o zbytcích.
Nejprve vyřešíme \(x^2 \equiv 4 \pmod{3}\).
Mod 3 jsou možné zbytky \(0, 1, 2\).
Zkoušíme:
\(0^2 \equiv 0 \neq 4 \equiv 1 \pmod{3}\), protože \(4 \equiv 1\)
\(1^2 = 1 \equiv 1\)
\(2^2 = 4 \equiv 1\)
Řešení mod 3 jsou tedy \(x \equiv 1, 2\).
Teď řešíme \(x^2 \equiv 4 \pmod{7}\).
Mod 7 jsou zbytky \(0, …, 6\), hledáme takové \(x\), že \(x^2 \equiv 4\).
Zkoušíme:
\(2^2 = 4\), \(5^2 = 25 \equiv 4 \pmod{7}\).
Řešení mod \(7\) jsou tedy \(x \equiv 2, 5\).
Nyní sestavíme všechny kombinace z Čínské věty:
Možnosti pro \(x \pmod{3}\): 1, 2
Možnosti pro \(x \pmod{7}\): 2, 5
Řešení mod \(21\) jsou všechny \(x\) splňující současně jednu ze čtyř kombinací:
\(x \equiv 1 \pmod{3}, x \equiv 2 \pmod{7}\)
\(x \equiv 1 \pmod{3}, x \equiv 5 \pmod{7}\)
\(x \equiv 2 \pmod{3}, x \equiv 2 \pmod{7}\)
\(x \equiv 2 \pmod{3}, x \equiv 5 \pmod{7}\)
Řešíme jednotlivé systémy (použijeme metodu dosazení nebo rozšířený Euklidův algoritmus):
1) \(x \equiv 1 \pmod{3}\) a \(x \equiv 2 \pmod{7}\)
Hledáme \(x = 1 + 3k\), aby \(x \equiv 2 \pmod{7}\).
\(1 + 3k \equiv 2 \pmod{7} \Rightarrow 3k \equiv 1 \pmod{7}\).
Inverze \(3\) mod \(7\) je \(5\), protože \(3 \times 5 = 15 \equiv 1 \pmod{7}\).
Tedy \(k \equiv 5 \times 1 = 5 \pmod{7}\).
Nejmenší řešení je \(k=5\), tedy \(x=1 + 3 \times 5 = 16\).
Řešení první kombinace je \(x \equiv 16 \pmod{21}\).
2) \(x \equiv 1 \pmod{3}\) a \(x \equiv 5 \pmod{7}\)
\(1 + 3k \equiv 5 \pmod{7} \Rightarrow 3k \equiv 4 \pmod{7}\).
Inverze \(3\) je \(5\), tedy \(k \equiv 5 \times 4 = 20 \equiv 6 \pmod{7}\).
Nejmenší řešení \(k=6\), tedy \(x = 1 + 3 \times 6 = 19\).
Řešení druhé kombinace je \(x \equiv 19 \pmod{21}\).
3) \(x \equiv 2 \pmod{3}\) a \(x \equiv 2 \pmod{7}\)
\(2 + 3k \equiv 2 \pmod{7} \Rightarrow 3k \equiv 0 \pmod{7}\).
To znamená \(k \equiv 0 \pmod{7}\).
Nejmenší řešení \(k=0\), tedy \(x=2\).
Řešení třetí kombinace je \(x \equiv 2 \pmod{21}\).
4) \(x \equiv 2 \pmod{3}\) a \(x \equiv 5 \pmod{7}\)
\(2 + 3k \equiv 5 \pmod{7} \Rightarrow 3k \equiv 3 \pmod{7}\).
Inverze \(3\) je \(5\), tedy \(k \equiv 5 \times 3 = 15 \equiv 1 \pmod{7}\).
Nejmenší řešení \(k=1\), tedy \(x=2 + 3 \times 1 = 5\).
Řešení čtvrté kombinace je \(x \equiv 5 \pmod{21}\).
Celkem tedy máme řešení:
\(x \equiv 2, 5, 16, 19 \pmod{21}\).
70. Vyřešte kongruenci \(17x \equiv 1 \pmod{3120}\), kde \(3120 = \varphi(53 \times 59)\).
Řešení příkladu:
Kongruence je \(17x \equiv 1 \pmod{3120}\), hledáme inverzi \(17\) modulo \(3120\).
Použijeme rozšířený Euklidův algoritmus pro výpočet \(\gcd(17, 3120)\) a inverze:
1) \(3120 = 17 \times 183 + 9\)
2) \(17 = 9 \times 1 + 8\)
3) \(9 = 8 \times 1 + 1\)
4) \(8 = 1 \times 8 + 0\)
Zpětně vyjádříme \(1\):
1 = 9 – 8 \times 1
8 = 17 – 9 \times 1 \Rightarrow 1 = 9 – (17 – 9 \times 1) = 2 \times 9 – 17
9 = 3120 – 17 \times 183 \Rightarrow 1 = 2 \times (3120 – 17 \times 183) – 17 = 2 \times 3120 – 17 \times 367
Tedy \(1 \equiv -17 \times 367 \pmod{3120}\).
Inverze \(17\) modulo \(3120\) je tedy \(x \equiv -367 \equiv 3120 – 367 = 2753 \pmod{3120}\).
Řešení je \(x \equiv 2753 \pmod{3120}\).
71. Vyřešte kongruenci \(x^3 \equiv 1 \pmod{7}\).
Řešení příkladu:
Zkoušíme všechna \(x = 0, 1, …, 6\) mod \(7\):
\(0^3 = 0 \neq 1\)
\(1^3 = 1\)
\(2^3 = 8 \equiv 1 \pmod{7}\)
\(3^3 = 27 \equiv 6 \neq 1\)
\(4^3 = 64 \equiv 1 \pmod{7}\)
\(5^3 = 125 \equiv 6 \neq 1\)
\(6^3 = 216 \equiv 6 \neq 1\)
Řešení jsou tedy \(x \equiv 1, 2, 4 \pmod{7}\).
72. Vyřešte kongruenci \(9x + 4 \equiv 7 \pmod{13}\).
Řešení příkladu:
Přesuneme 4 na pravou stranu:
\(9x \equiv 7 – 4 = 3 \pmod{13}\).
Najdeme inverzi \(9\) mod \(13\):
\(\gcd(9, 13) = 1\), inverze existuje.
Zkoušíme \(9 \times y \equiv 1 \pmod{13}\):
\(9 \times 3 = 27 \equiv 1 \pmod{13}\), inverze je \(3\).
Vynásobíme obě strany 3:
\(x \equiv 3 \times 3 = 9 \pmod{13}\).
73. Vyřešte kongruenci \(2^{x} \equiv 8 \pmod{17}\).
Řešení příkladu:
Máme \(2^x \equiv 8 \pmod{17}\).
Zkusíme zjistit, pro jaké \(x\) platí \(2^x \equiv 8\).
Vypočítáme mocniny dvojky modulo \(17\):
\(2^1 = 2\)
\(2^2 = 4\)
\(2^3 = 8\)
Již nalezeno, \(x = 3\).
Řešení: \(x \equiv 3 \pmod{16}\), protože \(\varphi(17) = 16\).
74. Vyřešte soustavu kongruencí:
\(x \equiv 3 \pmod{4}\)
\(x \equiv 5 \pmod{9}\)
Řešení příkladu:
Máme soustavu:
\(x \equiv 3 \pmod{4}\)
\(x \equiv 5 \pmod{9}\)
Vypíšeme řešení první kongruence:
\(x = 3 + 4k\).
Dosadíme do druhé:
\(3 + 4k \equiv 5 \pmod{9}\)
\(4k \equiv 2 \pmod{9}\)
Najdeme inverzi 4 mod 9:
\(4 \times 7 = 28 \equiv 1 \pmod{9}\), inverze je \(7\).
\(k \equiv 2 \times 7 = 14 \equiv 5 \pmod{9}\).
Nejmenší řešení je \(k=5\), tedy
\(x = 3 + 4 \times 5 = 23\).
Obecné řešení je \(x \equiv 23 \pmod{36}\), protože \(\text{nsd}(4,9) = 1\) a modulus je \(4 \times 9 = 36\).
75. Vyřešte kongruenci \(x^2 + x + 1 \equiv 0 \pmod{5}\).
Řešení příkladu:
Kongruence je \(x^2 + x + 1 \equiv 0 \pmod{5}\).
Zkoušíme hodnoty \(x = 0, 1, 2, 3, 4\) modulo 5:
\(0^2 + 0 + 1 = 1 \neq 0\)
\(1 + 1 + 1 = 3 \neq 0\)
\(4 + 2 + 1 = 7 \equiv 2 \neq 0\)
\(9 + 3 + 1 = 13 \equiv 3 \neq 0\)
\(16 + 4 + 1 = 21 \equiv 1 \neq 0\)
Žádné přímé řešení neexistuje.
Pokud bychom chtěli řešit obecně, použili bychom kvadratický vzorec v mod \(5\):
Diskriminant je \(\Delta = 1^2 – 4 \times 1 \times 1 = 1 – 4 = -3 \equiv 2 \pmod{5}\).
Protože \(2\) není kvadratický zbytek mod \(5\) \((\)kvadratické zbytky jsou \(0,1,4)\), neexistují žádná řešení.
76. Vyřešte kongruenci \(14x \equiv 30 \pmod{100}\).
Řešení příkladu:
Nejprve zjistíme \(\gcd(14, 100)\).
\(\gcd(14, 100) = 2\).
Podmínka existence řešení: \(2\) musí dělit \(30\), což platí.
Podělíme kongruenci \(2\):
\(7x \equiv 15 \pmod{50}\).
Protože \(\gcd(7, 50) = 1\), inverze \(7\) modulo \(50\) existuje. Najdeme ji:
Hledáme \(y\), aby \(7y \equiv 1 \pmod{50}\).
Zkoušíme: \(7 \times 43 = 301 \equiv 1 \pmod{50}\), takže inverze je \(43\).
Vynásobíme obě strany rovnice 43:
\(x \equiv 15 \times 43 = 645 \equiv 45 \pmod{50}\).
Protože jsme modulus dělili \(2\), máme \(2\) řešení mod \(100\):
\(x \equiv 45 + 50k, k=0,1\).
Řešení jsou tedy \(x \equiv 45, 95 \pmod{100}\).
77. Vyřešte kongruenci \(5x^2 \equiv 20 \pmod{35}\).
Řešení příkladu:
Máme kongruenci \(5x^2 \equiv 20 \pmod{35}\).
Zkontrolujeme \(\gcd(5, 35) = 5\), a zda \(5\) dělí pravou stranu \(20\) — dělí.
Podělíme kongruenci \(5\):
\(x^2 \equiv 4 \pmod{7}\).
Nyní hledáme \(x\), pro která \(x^2 \equiv 4 \pmod{7}\).
Zkoušíme hodnoty \(x = 0, 1, …, 6\):
\(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4\), \(3^2 = 9 \equiv 2\), \(4^2 = 16 \equiv 2\), \(5^2 = 25 \equiv 4\), \(6^2 = 36 \equiv 1\).
Řešení jsou tedy \(x \equiv 2, 5 \pmod{7}\).
Vrátíme se k původnímu modulu \(35\) a vyjádříme řešení jako soustavu:
\(x \equiv 2 \pmod{7}\), \(x \equiv a \pmod{5}\) libovolné \(a = 0, 1, 2, 3, 4\), protože \(5\) je faktor modulu.
Stejně pro \(x \equiv 5 \pmod{7}\).
Pro každý z těchto dvou zbytků mod \(7\) existuje \(5\) možností mod \(5\), celkem \(10\) řešení mod \(35\).
78. Vyřešte kongruenci \(3^{x} \equiv 12 \pmod{17}\).
Řešení příkladu:
Hledáme \(x\) tak, aby \(3^x \equiv 12 \pmod{17}\).
Vypočítáme mocniny 3 modulo 17:
\(3^1 = 3\), \(3^2 = 9\), \(3^3 = 27 \equiv 10\), \(3^4 = 30 \equiv 13\), \(3^5 = 39 \equiv 5\),
\(3^6 = 15\), \(3^7 = 11\), \(3^8 = 16\), \(3^9 = 14\), \(3^{10} = 8\), \(3^{11} = 7\), \(3^{12} = 4\), \(3^{13} = 12\).
Našli jsme \(x = 13\).
Protože \(\varphi(17) = 16\), obecné řešení je:
\(x \equiv 13 \pmod{16}\).
79. Vyřešte soustavu kongruencí:
\(x \equiv 2 \pmod{5}\)
\(x \equiv 3 \pmod{11}\)
Řešení příkladu:
Máme soustavu:
\(x \equiv 2 \pmod{5}\)
\(x \equiv 3 \pmod{11}\)
Vyjádříme první kongruenci:
\(x = 2 + 5k\).
Dosadíme do druhé kongruence:
\(2 + 5k \equiv 3 \pmod{11}\)
\(5k \equiv 1 \pmod{11}\).
Najdeme inverzi 5 modulo 11:
\(5 \times 9 = 45 \equiv 1 \pmod{11}\), inverze je \(9\).
Vynásobíme obě strany \(9\):
\(k \equiv 9 \times 1 = 9 \pmod{11}\).
Nejmenší řešení je \(k=9\), tedy
\(x = 2 + 5 \times 9 = 47\).
Obecné řešení je \(x \equiv 47 \pmod{55}\), protože \(\text{nsd}(5, 11) = 1\).
80. Vyřešte kongruenci \(x^3 \equiv 8 \pmod{19}\).
Řešení příkladu:
Hledáme \(x\), tak že \(x^3 \equiv 8 \pmod{19}\).
Zkoušíme hodnoty \(x = 0, 1, \ldots, 18\):
\(0^3=0 \equiv 0 \pmod{19}\), \(1^3=1 \equiv 1 \pmod{19}\), \(2^3=8 \equiv 8 \pmod{19}\) → našli jsme řešení \(x \equiv 2 \pmod{19}\), \(3^3=27 \equiv 8 \pmod{19}\) (protože \(27-19=8\)) → další řešení \(x \equiv 3 \pmod{19}\), \(4^3=64 \equiv 7 \pmod{19}\), \(5^3=125 \equiv 11 \pmod{19}\), \(6^3=216 \equiv 7 \pmod{19}\), \(7^3=343 \equiv 1 \pmod{19}\), \(8^3=512 \equiv 18 \pmod{19}\), \(9^3=729 \equiv 7 \pmod{19}\), \(10^3=1000 \equiv 12 \pmod{19}\), \(11^3=1331 \equiv 1 \pmod{19}\), \(12^3=1728 \equiv 14 \pmod{19}\), \(13^3=2197 \equiv 16 \pmod{19}\), \(14^3=2744 \equiv 8 \pmod{19}\) → další řešení \(x \equiv 14 \pmod{19}\), \(15^3=3375 \equiv 11 \pmod{19}\), \(16^3=4096 \equiv 18 \pmod{19}\), \(17^3=4913 \equiv 1 \pmod{19}\), \(18^3=5832 \equiv 18 \pmod{19}\)
Takže všechna řešení jsou \(x \equiv 2, 3, 14 \pmod{19}\).
81. Vyřešte kongruenci \(4x \equiv 1 \pmod{15}\).
Řešení příkladu:
Máme \(4x \equiv 1 \pmod{15}\).
Zkontrolujeme \(\gcd(4,15) = 1\), inverze \(4\) existuje.
Hledáme \(y\), že \(4y \equiv 1 \pmod{15}\).
Zkoušíme: \(4 \times 4 = 16 \equiv 1 \pmod{15}\), takže inverze je \(4\).
Vynásobíme obě strany \(4\):
\(x \equiv 4 \times 1 = 4 \pmod{15}\).
Řešení je tedy \(x \equiv 4 \pmod{15}\).
82. Vyřešte kongruenci \(x^2 + 3x + 2 \equiv 0 \pmod{13}\).
Řešení příkladu:
Máme kvadratickou kongruenci \(x^2 + 3x + 2 \equiv 0 \pmod{13}\).
Diskriminant je \(\Delta = 3^2 – 4 \times 1 \times 2 = 9 – 8 = 1\).
Protože \(\Delta = 1\) je kvadratický zbytek modulo \(13\), řešení existují.
Najdeme odmocniny diskriminantu: \(\sqrt{1} \equiv \pm 1 \pmod{13}\).
Řešení jsou podle vzorce:
\(x \equiv \frac{-3 \pm 1}{2} \pmod{13}\).
Vypočteme inverzi \(2\) modulo \(13\):
\(2 \times 7 = 14 \equiv 1 \pmod{13}\), inverze je \(7\).
Pro \(+\): \(x \equiv (-3 + 1) \times 7 = (-2) \times 7 = -14 \equiv 12 \pmod{13}\).
Pro \(-\): \(x \equiv (-3 – 1) \times 7 = (-4) \times 7 = -28 \equiv 11 \pmod{13}\).
Řešení jsou tedy \(x \equiv 11, 12 \pmod{13}\).
83. Vyřešte kongruenci \(7x + 3 \equiv 2x + 8 \pmod{25}\).
Řešení příkladu:
Převedeme vše na jednu stranu:
\(7x – 2x \equiv 8 – 3 \pmod{25}\)
\(5x \equiv 5 \pmod{25}\).
Zkontrolujeme \(\gcd(5, 25) = 5\).
Podmínka existence řešení: \(5\) dělí \(5\), platí.
Podělíme kongruenci \(5\):
\(x \equiv 1 \pmod{5}\).
Protože jsme dělili modulo \(5\), řešení je:
\(x \equiv 1 + 5k, k = 0, 1, 2, 3, 4\) modulo \(25\).
Řešení jsou tedy \(x \equiv 1, 6, 11, 16, 21 \pmod{25}\).
84. Vyřešte kongruenci \(2x^2 + 3x + 1 \equiv 0 \pmod{7}\).
Řešení příkladu:
Máme kvadratickou kongruenci \(2x^2 + 3x + 1 \equiv 0 \pmod{7}\).
Diskriminant je \(\Delta = 3^2 – 4 \times 2 \times 1 = 9 – 8 = 1\).
Protože \(\Delta = 1\) je kvadratický zbytek modulo 7, existují řešení.
Najdeme odmocniny diskriminantu: \(\sqrt{1} \equiv \pm 1 \pmod{7}\).
Inverzi \(2 \times 2 = 4\) modulo \(7\) potřebujeme k dělení \(4\):
Vypočítáme inverzi \(4\) mod \(7\):
\(4 \times 2 = 8 \equiv 1 \pmod{7}\), inverze je \(2\).
Řešení jsou podle vzorce:
\(x \equiv (-3 \pm 1) \times 2 \pmod{7}\).
Pro \(+\): \(x \equiv (-3 + 1) \times 2 = (-2) \times 2 = -4 \equiv 3 \pmod{7}\).
Pro \(-\): \(x \equiv (-3 – 1) \times 2 = (-4) \times 2 = -8 \equiv 6 \pmod{7}\).
Řešení jsou tedy \(x \equiv 3, 6 \pmod{7}\).
85. Vyřešte kongruenci \(x^{4} \equiv 1 \pmod{15}\).
Řešení příkladu:
Máme kongruenci \(x^4 \equiv 1 \pmod{15}\).
Protože \(15 = 3 \cdot 5\), řešíme soustavu:
\(x^4 \equiv 1 \pmod{3}\)
\(x^4 \equiv 1 \pmod{5}\)
Modulo 3: možné zbytky jsou \(0,1,2\):
\(0^4 = 0 \equiv 0\), \(1^4 = 1 \equiv 1\), \(2^4 = 16 \equiv 1\)
Řešení mod \(3\) jsou \(x \equiv 1, 2\).
Modulo 5: možné zbytky jsou \(0,1,2,3,4\):
\(0^4=0\), \(1^4=1\), \(2^4=16 \equiv 1\), \(3^4=81 \equiv 1\), \(4^4=256 \equiv 1\)
Řešení mod \(5\) jsou \(x \equiv 1, 2, 3, 4\).
Soustava je tedy:
\(x \equiv \{1,2\} \pmod{3}\)
\(x \equiv \{1,2,3,4\} \pmod{5}\)
Pomocí čínské zbytkové věty spočítáme všechny kombinace (celkem \(8\) řešení mod \(15\)):
Pro \(x \equiv 1 \pmod{3}\):
\(x \equiv 1 \pmod{5} \Rightarrow x \equiv 1 \pmod{15}\)
\(x \equiv 2 \pmod{5} \Rightarrow x \equiv 11 \pmod{15}\)
\(x \equiv 3 \pmod{5} \Rightarrow x \equiv 6 \pmod{15}\)
\(x \equiv 4 \pmod{5} \Rightarrow x \equiv 16 \equiv 1 \pmod{15}\) (opakování)
Pro \(x \equiv 2 \pmod{3}\):
\(x \equiv 1 \pmod{5} \Rightarrow x \equiv 7 \pmod{15}\)
\(x \equiv 2 \pmod{5} \Rightarrow x \equiv 2 \pmod{15}\)
\(x \equiv 3 \pmod{5} \Rightarrow x \equiv 12 \pmod{15}\)
\(x \equiv 4 \pmod{5} \Rightarrow x \equiv 14 \pmod{15}\)
Řešení mod \(15\) jsou tedy:
\(x \equiv 1, 2, 6, 7, 11, 12, 14 \pmod{15}\)
86. Vyřešte kongruenci \(24x \equiv 18 \pmod{90}\).
Řešení příkladu:
Zjistíme \(\gcd(24, 90)\).
\(\gcd(24, 90) = 6\).
Podmínka existence řešení: \(6\) musí dělit \(18\), což platí.
Podělíme kongruenci \(6\):
\(4x \equiv 3 \pmod{15}\).
Nyní zjistíme, zda existuje inverze \(4\) modulo \(15\).
\(\gcd(4, 15) = 1\), inverze existuje.
Hledáme \(y\), aby \(4y \equiv 1 \pmod{15}\).
Zkoušíme: \(4 \times 4 = 16 \equiv 1 \pmod{15}\), tedy inverze je \(4\).
Vynásobíme obě strany rovnice \(4\):
\(x \equiv 3 \times 4 = 12 \pmod{15}\).
Protože jsme modulus původně dělili \(6\), máme \(6\) řešení modulo \(90\):
\(x \equiv 12 + 15k, k = 0, 1, 2, 3, 4, 5\).
Řešení jsou tedy \(x \equiv 12, 27, 42, 57, 72, 87 \pmod{90}\).
87. Najděte všechny řešení kongruence \(x^2 \equiv 16 \pmod{35}\).
Řešení příkladu:
Rozložíme modul: \(35 = 5 \times 7\).
Řešíme \(x^2 \equiv 16 \pmod{5}\): \(16 \equiv 1 \pmod{5}\), takže \(x \equiv 1,4 \pmod{5}\).
Řešíme \(x^2 \equiv 16 \pmod{7}\): \(16 \equiv 2 \pmod{7}\), zkoušíme \(x = 0,1,2,3,4,5,6\):
\(0^2=0,1^2=1,2^2=4,3^2=2,4^2=2,5^2=4,6^2=1\)
Řešení mod 7: \(x \equiv 3,4\).
Kombinujeme pomocí Čínské zbytkové věty:
1) \(x \equiv 1 \pmod{5}\) a \(x \equiv 3 \pmod{7} \Rightarrow x = 31\)
2) \(x \equiv 1 \pmod{5}\) a \(x \equiv 4 \pmod{7} \Rightarrow x = 4\)
3) \(x \equiv 4 \pmod{5}\) a \(x \equiv 3 \pmod{7} \Rightarrow x = 24\)
4) \(x \equiv 4 \pmod{5}\) a \(x \equiv 4 \pmod{7} \Rightarrow x = 9\)
Řešení jsou \(x \equiv 4, 9, 24, 31 \pmod{35}\).
88. Vyřešte kongruenci \(17x \equiv 1 \pmod{3120}\), kde \(3120\) je Eulerova funkce \(\varphi(65537)\).
Řešení příkladu:
Jde o nalezení inverze čísla \(17\) modulo \(3120\).
Použijeme rozšířený Eukleidův algoritmus k řešení rovnice:
\(17x + 3120y = 1\).
Vypočteme:
3120 = 17 × 183 + 9
17 = 9 × 1 + 8
9 = 8 × 1 + 1
8 = 1 × 8 + 0
Zpětně dosazujeme:
1 = 9 – 8 × 1
8 = 17 – 9 × 1 \Rightarrow 1 = 9 – (17 – 9) = 2 × 9 – 17
9 = 3120 – 17 × 183 \Rightarrow 1 = 2(3120 – 17 × 183) – 17 = 2 × 3120 – 17 × 366 – 17 = 2 × 3120 – 17 × 367
Tedy:
\(17 \times (-367) + 3120 \times 2 = 1\).
Inverze 17 modulo 3120 je tedy \(-367\), což modulo \(3120\) odpovídá:
\(3120 – 367 = 2753\).
Řešení kongruence je tedy:
\(x \equiv 2753 \pmod{3120}\).
89. Určete všechny řešení kongruence \(5x \equiv 7 \pmod{15}\).
Řešení příkladu:
Nejdříve zjistíme \(\gcd(5, 15) = 5\).
Podmínka existence řešení je, že 5 musí dělit \(7\).
Protože \(5\) nedělí \(7\), kongruence nemá žádné řešení.
Odpověď: Kongruence nemá řešení.
90. Najděte všechna řešení kongruence \(x^3 \equiv 2 \pmod{7}\).
Řešení příkladu:
Zkoušíme \(x = 0,1,2,3,4,5,6\) a počítáme \(x^3 \pmod{7}\):
\(0^3 = 0\), \(1^3=1\), \(2^3=8 \equiv 1\), \(3^3=27 \equiv 6\), \(4^3=64 \equiv 1\), \(5^3=125 \equiv 6\), \(6^3=216 \equiv 6\).
Vidíme, že \(x^3\) nabývá hodnot \(0,1,6\) mod \(7\).
Hodnota \(2\) není mezi nimi, tudíž kongruence nemá řešení.
91. Vyřešte kongruenci \(3x \equiv 12 \pmod{18}\).
Řešení příkladu:
Zjistíme \(\gcd(3, 18) = 3\).
Podmínka existence řešení: \(3\) musí dělit \(12\), což platí.
Podělíme kongruenci 3:
\(x \equiv 4 \pmod{6}\).
Protože jsme modulus dělili \(3\), máme \(3\) řešení modulo \(18\):
\(x \equiv 4 + 6k, k = 0,1,2\).
Řešení jsou tedy \(x \equiv 4, 10, 16 \pmod{18}\).
92. Najděte všechna řešení kongruence \(x^2 + x + 1 \equiv 0 \pmod{11}\).
Řešení příkladu:
Pro \(x = 0,1,2,…,10\) spočítáme hodnotu \(x^2 + x + 1 \pmod{11}\):
\(0^2 + 0 + 1 = 1\),
\(1 + 1 + 1 = 3\),
\(4 + 2 + 1 = 7\),
\(9 + 3 + 1 = 13 \equiv 2\),
\(16 + 4 + 1 = 21 \equiv 10\),
\(25 + 5 + 1 = 31 \equiv 9\),
\(36 + 6 + 1 = 43 \equiv 10\),
\(49 + 7 + 1 = 57 \equiv 2\),
\(64 + 8 + 1 = 73 \equiv 7\),
\(81 + 9 + 1 = 91 \equiv 3\),
\(100 + 10 + 1 = 111 \equiv 1\).
Žádné \(x\) nevyhovuje kongruenci, tedy řešení neexistuje.
93. Vyřešte soustavu kongruencí: \[ \begin{cases} x \equiv 2 \pmod{5} \\ x \equiv 3 \pmod{7} \\ x \equiv 1 \pmod{9} \end{cases} \]
Řešení příkladu:
Moduly jsou navzájem nesoudělné, použijeme Čínskou zbytkovou větu.
Celkový modul je \(N = 5 \times 7 \times 9 = 315\).
Vypočítáme \(N_i = \frac{N}{n_i}\):
\(N_1 = \frac{315}{5} = 63\), \(N_2 = \frac{315}{7} = 45\), \(N_3 = \frac{315}{9} = 35\).
Najdeme inverze \(M_i\), že \(N_i M_i \equiv 1 \pmod{n_i}\):
Pro \(N_1 = 63 \pmod{5}\): \(63 \equiv 3 \pmod{5}\).
Hledáme \(M_1\), aby \(3M_1 \equiv 1 \pmod{5}\).
Zkoušíme: \(3 \times 2 = 6 \equiv 1\), tedy \(M_1=2\).
Pro \(N_2 = 45 \pmod{7}\): \(45 \equiv 3 \pmod{7}\).
Hledáme \(M_2\), aby \(3M_2 \equiv 1 \pmod{7}\).
Zkoušíme: \(3 \times 5 = 15 \equiv 1\), tedy \(M_2=5\).
Pro \(N_3 = 35 \pmod{9}\): \(35 \equiv 8 \pmod{9}\).
Hledáme \(M_3\), aby \(8M_3 \equiv 1 \pmod{9}\).
Zkoušíme: \(8 \times 8 = 64 \equiv 1\), tedy \(M_3=8\).
Podle Čínské zbytkové věty:
\(x \equiv a_1 N_1 M_1 + a_2 N_2 M_2 + a_3 N_3 M_3 \pmod{315}\), kde \(a_i\) jsou zbytky.
\(x \equiv 2 \times 63 \times 2 + 3 \times 45 \times 5 + 1 \times 35 \times 8 \pmod{315}\).
\(x \equiv 252 + 675 + 280 = 1207 \pmod{315}\).
Po vydělení:
\(1207 = 315 \times 3 + 262\), tedy
\(x \equiv 262 \pmod{315}\).
Řešení je \(x \equiv 262 \pmod{315}\).
94. Najděte všechna řešení kongruence \(x^4 \equiv 1 \pmod{15}\).
Řešení příkladu:
Protože \(15 = 3 \times 5\), řešíme moduly \(3\) a \(5\) zvlášť.
Modulo 3: zkoušíme \(x=0,1,2\).
\(0^4=0\), \(1^4=1\), \(2^4=(2^2)^2 = 4^2 = 1^2=1\) mod \(3\).
Řešení mod \(3\): \(x \equiv 1, 2\).
Modulo \(5\): zkoušíme \(x=0,1,2,3,4\).
\(0^4=0\), \(1^4=1\), \(2^4=16 \equiv 1\), \(3^4=81 \equiv 1\), \(4^4=256 \equiv 1\).
Řešení mod \(5\): \(x \equiv 1, 2, 3, 4\).
Kombinujeme pomocí Čínské zbytkové věty všechny možné dvojice řešení:
Mod \(3: 1\) nebo \(2\), mod \(5\): \(1,2,3,4\).
Celkem 8 řešení modulo 15.
Například:
\(x \equiv 1 \pmod{3}\) a \(x \equiv 1 \pmod{5} \Rightarrow x \equiv 1 \pmod{15}\).
\(x \equiv 1 \pmod{3}\) a \(x \equiv 2 \pmod{5}\), hledáme \(x\) tak, že:
\(x=1+3k\), hledáme \(k\) pro \(1+3k \equiv 2 \pmod{5}\).
\(3k \equiv 1 \pmod{5}\), protože \(3 \times 2 = 6 \equiv 1\), tedy \(k \equiv 2\).
\(x=1 + 3 \times 2 = 7\), tedy \(x \equiv 7 \pmod{15}\).
Podobně spočítáme ostatní řešení, která jsou:
\(x \equiv 1, 7, 10, 13, 2, 8, 11, 14 \pmod{15}\).
95. Najděte inverzi čísla \(11\) modulo \(37\).
Řešení příkladu:
Hledáme \(x\), aby platilo:
\(11x \equiv 1 \pmod{37}\).
Použijeme rozšířený Eukleidův algoritmus pro rovnost \(11x + 37y = 1\).
37 = 11 × 3 + 4
11 = 4 × 2 + 3
4 = 3 × 1 + 1
3 = 1 × 3 + 0
Zpětně dosazujeme:
1 = 4 – 3 × 1
3 = 11 – 4 × 2 \Rightarrow 1 = 4 – (11 – 4 \times 2) = 3 \times 4 – 11
4 = 37 – 11 × 3 \Rightarrow 1 = 3 \times (37 – 11 \times 3) – 11 = 3 \times 37 – 9 \times 11 – 11 = 3 \times 37 – 10 \times 11
Tedy:
\(11 \times (-10) + 37 \times 3 = 1\).
Inverze \(11\) modulo \(37\) je tedy \(-10\), což modulo \(37\) odpovídá:
\(37 – 10 = 27\).
Řešení je:
\(x \equiv 27 \pmod{37}\).
96. Vyřešte kongruenci \(56x \equiv 42 \pmod{98}\).
Řešení příkladu:
Zjistíme \(\gcd(56, 98) = 14\).
Podmínka existence řešení: \(14 \mid 42\), což platí.
Podělíme kongruenci 14: \(4x \equiv 3 \pmod{7}\).
Najdeme inverzi 4 modulo 7: \(4 \times 2 = 8 \equiv 1 \pmod{7}\).
Vynásobíme obě strany 2: \(x \equiv 3 \times 2 = 6 \pmod{7}\).
Počet řešení je \(\gcd(56,98) = 14\), tedy \(x \equiv 6 + 7k, k=0,1,…,13\).
Řešení jsou \(x \equiv 6, 13, 20, 27, 34, 41, 48, 55, 62, 69, 76, 83, 90, 97 \pmod{98}\).
97. Najděte všechny řešení kongruence \(x^2 \equiv 16 \pmod{35}\).
Řešení příkladu:
Modul \(35\) rozložíme na prvočísla \(35 = 5 \times 7\).
Podmínka: \(x^2 \equiv 16 \pmod{35} \Rightarrow\) zároveň
\(x^2 \equiv 16 \pmod{5}\) a \(x^2 \equiv 16 \pmod{7}\).
Nejprve modulo \(5\):
Protože \(16 \equiv 1 \pmod{5}\), hledáme \(x\) tak, že \(x^2 \equiv 1 \pmod{5}\).
Řešení jsou \(x \equiv 1 \pmod{5}\) nebo \(x \equiv 4 \pmod{5}\).
Modulo \(7\):
\(16 \equiv 2 \pmod{7}\), hledáme \(x\) tak, že \(x^2 \equiv 2 \pmod{7}\).
Zkoušíme hodnoty \(x = 0, 1, 2, …, 6\):
\(0^2=0, 1^2=1, 2^2=4, 3^2=9 \equiv 2, 4^2=16 \equiv 2, 5^2=25 \equiv 4, 6^2=36 \equiv 1\).
Řešení jsou tedy \(x \equiv 3 \pmod{7}\) a \(x \equiv 4 \pmod{7}\).
Nyní kombinujeme pomocí Čínské zbytkové věty:
1) \(x \equiv 1 \pmod{5}\) a \(x \equiv 3 \pmod{7}\)
Nechť \(x = 1 + 5k\). Potom \(1 + 5k \equiv 3 \pmod{7}\).
\(5k \equiv 2 \pmod{7}\).
Inverze \(5\) modulo \(7\) je \(3\) (protože \(5 \times 3 = 15 \equiv 1\)).
\(k \equiv 2 \times 3 = 6 \pmod{7}\).
Tedy \(k = 6 + 7m\), pro \(m \in \mathbb{Z}\).
\(x = 1 + 5 \times 6 = 31 \pmod{35}\).
2) \(x \equiv 1 \pmod{5}\) a \(x \equiv 4 \pmod{7}\)
\(1 + 5k \equiv 4 \pmod{7} \Rightarrow 5k \equiv 3 \pmod{7}\).
\(k \equiv 3 \times 3 = 9 \equiv 2 \pmod{7}\).
\(x = 1 + 5 \times 2 = 11 \pmod{35}\).
3) \(x \equiv 4 \pmod{5}\) a \(x \equiv 3 \pmod{7}\)
\(x = 4 + 5k\), \(4 + 5k \equiv 3 \pmod{7}\),
\(5k \equiv -1 \equiv 6 \pmod{7}\),
\(k \equiv 6 \times 3 = 18 \equiv 4 \pmod{7}\).
\(x = 4 + 5 \times 4 = 24 \pmod{35}\).
4) \(x \equiv 4 \pmod{5}\) a \(x \equiv 4 \pmod{7}\)
\(4 + 5k \equiv 4 \pmod{7} \Rightarrow 5k \equiv 0 \pmod{7}\),
\(k \equiv 0 \pmod{7}\).
\(x = 4 \pmod{35}\).
Řešení jsou tedy \(x \equiv 4, 11, 24, 31 \pmod{35}\).
98. Najděte inverzi čísla \(17\) modulo \(3120\).
Řešení příkladu:
Hledáme \(x\), aby platilo:
\(17x \equiv 1 \pmod{3120}\).
Použijeme rozšířený Eukleidův algoritmus pro rovnost \(17x + 3120y = 1\).
Nejprve dělení:
\(3120 = 17 × 183 + 9\)
\(17 = 9 × 1 + 8\)
\(9 = 8 × 1 + 1\)
\(8 = 1 × 8 + 0\)
Zpětné dosazování:
\(1 = 9 – 8 × 1\)
\(8 = 17 – 9 × 1 \Rightarrow 1 = 9 – (17 – 9) = 2 \times 9 – 17\)
\(9 = 3120 – 17 \times 183 \Rightarrow 1 = 2 \times (3120 – 17 \times 183) – 17 = 2 \times 3120 – 17 \times 366 – 17 = 2 \times 3120 – 17 \times 367\)
Tedy:
\(17 \times (-367) + 3120 \times 2 = 1\).
Inverze \(17\) modulo \(3120\) je tedy \(-367\), což modulo \(3120\) odpovídá:
\(3120 – 367 = 2753\).
Řešení je \(x \equiv 2753 \pmod{3120}\).
99. Vyřešte soustavu kongruencí:
\(x \equiv 2 \pmod{3}\),
\(x \equiv 3 \pmod{4}\),
\(x \equiv 1 \pmod{5}\).
Řešení příkladu:
Máme soustavu:
\(x \equiv 2 \pmod{3}\),
\(x \equiv 3 \pmod{4}\),
\(x \equiv 1 \pmod{5}\).
Nejprve řešíme první dvě kongruence:
Nechť \(x = 2 + 3k\).
\(2 + 3k \equiv 3 \pmod{4}\).
\(3k \equiv 1 \pmod{4}\).
Protože \(3 \equiv -1 \pmod{4}\),
\(-k \equiv 1 \pmod{4} \Rightarrow k \equiv -1 \equiv 3 \pmod{4}\).
Tedy \(k = 3 + 4m\).
\(x = 2 + 3(3 + 4m) = 2 + 9 + 12m = 11 + 12m\).
Nyní dosadíme do třetí kongruence:
\(11 + 12m \equiv 1 \pmod{5}\).
\(12m \equiv -10 \equiv 0 \pmod{5}\).
Protože \(12 \equiv 2 \pmod{5}\), máme:
\(2m \equiv 0 \pmod{5}\).
Řešením je \(m \equiv 0 \pmod{5}\).
Celkové řešení je tedy:
\(x = 11 + 12 \times 5n = 11 + 60n\), \(n \in \mathbb{Z}\).
100. Vyřešte kongruenci \(3^{x} \equiv 13 \pmod{17}\).
Řešení příkladu:
Hledáme \(x\), pro které platí \(3^x \equiv 13 \pmod{17}\).
Vyzkoušíme postupně mocniny \(3\) modulo \(17\):
\(3^1 = 3\),
\(3^2 = 9\),
\(3^3 = 27 \equiv 10\),
\(3^4 = 30 \equiv 13\).
Tedy \(x = 4\) je řešení.
Protože \(17\) je prvočíslo, řád je \(16\), takže obecné řešení je:
\(x \equiv 4 \pmod{16}\).