Redukovaný zvyškový systém, inverzné prvky a Eulerova veta

1. Násobenie modulo \( m \) a potreba redukovaného zvyškového systému

Poznámka

Pri sčítaní modulo \( m \) tvorí množina všetkých zvyškov

\[ Z_m = \{0, 1, 2, \ldots, m - 1\} \]

grupu. Pri násobení je situácia iná. Nie každý zvyšok má totiž násobkový inverzný prvok.

Dôležité

To je dôležitý moment. Pri sčítaní vieme ku každému prvku nájsť opačný prvok. Pri násobení modulo \( m \) to už nemusí platiť. Preto sa nemôžeme automaticky pozerať na celú množinu \( Z_m \) a tvrdiť, že pri násobení tvorí grupu.

Príklad

Typický príklad je modulo \( 9 \). Množina všetkých zvyškov je

\[ Z_9 = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}. \]

Ak na nej uvažujeme násobenie modulo \( 9 \), rýchlo zistíme, že niektoré prvky nemajú inverzný prvok. Napríklad číslo \( 3 \) nemôže mať inverz modulo \( 9 \), pretože všetky násobky čísla \( 3 \) sú deliteľné \( 3 \), a teda nikdy nedajú zvyšok \( 1 \) po delení \( 9 \). Podobne je na tom aj číslo \( 6 \). Navyše platí napríklad

\[ 3 \cdot 3 = 9 \equiv 0 \pmod{9}, \]

takže tu vzniká nulový deliteľ. To je ďalší znak toho, že pri násobení modulo \( 9 \) nie je vhodné ponechať všetky prvky.

Poznámka

Ukazuje sa, že pri násobení modulo \( m \) treba vybrať len tie zvyšky, ktoré sú s číslom \( m \) nesúdeliteľné.

Definícia

Pojem „nesúdeliteľné“ znamená, že dve čísla nemajú spoločného deliteľa väčšieho ako \( 1 \). Zápis

\[ (a, m) = 1 \]

znamená, že najväčší spoločný deliteľ čísel \( a \) a \( m \) je \( 1 \).

Poznámka

Práve tieto prvky sú dôležité preto, že iba pri nich možno očakávať existenciu násobkového inverzu modulo \( m \).

Príklad

Pre modulo \( 9 \) teda z celej množiny \( Z_9 \) vyberieme len tie prvky, ktoré sú s \( 9 \) nesúdeliteľné:

\[ Z_9^{*} = \{1, 2, 4, 5, 7, 8\}. \]

Na tejto množine už násobenie modulo \( 9 \) funguje oveľa lepšie. Neutrálnym prvkom je \( 1 \) a každý prvok má svoj inverz. Preto práve táto vybraná množina vedie ku grupe.

Poznámka

Tým sa prirodzene dostávame k pojmu redukovaného zvyškového systému.

2. Úplný a redukovaný zvyškový systém

Definícia

Množina

\[ Z_m = \{0, 1, 2, \ldots, m - 1\} \]

sa nazýva úplný zvyškový systém modulo \( m \). Obsahuje všetky možné zvyšky po delení číslom \( m \).

Definícia

Pri násobení však z celej tejto množiny vyberáme iba tie prvky, ktoré sú s \( m \) nesúdeliteľné. Tým vzniká množina

\[ Z_m^{*} = \{k \text{ z množiny } \{1, 2, \ldots, m - 1\} ;\ (k, m) = 1\}. \]

Táto množina sa nazýva redukovaný zvyškový systém modulo \( m \).

Poznámka

Je dôležité pochopiť rozdiel medzi týmito dvoma množinami.

• Úplný zvyškový systém obsahuje všetky zvyšky.
• Redukovaný zvyškový systém obsahuje len tie zvyšky, ktoré sú použiteľné pri násobení z hľadiska existencie inverzu.

Príklad

Pre \( m = 12 \) platí

\[ Z_{12}^{*} = \{1, 5, 7, 11\}, \]

pretože práve tieto čísla z množiny \( \{1, 2, \ldots, 11\} \) sú s číslom \( 12 \) nesúdeliteľné.

Príklad

Pre \( m = 18 \) platí

\[ Z_{18}^{*} = \{1, 5, 7, 11, 13, 17\}. \]

Poznámka

Ak je \( p \) prvočíslo, situácia je ešte jednoduchšia. Každé číslo

\[ 1, 2, \ldots, p - 1 \]

je s prvočíslom \( p \) nesúdeliteľné, pretože žiadne z týchto čísel nie je násobkom \( p \). Preto

\[ Z_p^{*} = \{1, 2, \ldots, p - 1\}. \]

To je veľmi dôležitá a často používaná situácia.

3. Existencia inverzného prvku modulo \( m \)

Poznámka

Teraz prichádza základná veta, ktorá vysvetľuje, prečo sa vôbec zameriavame na prvky nesúdeliteľné s \( m \).

Veta

Nech \( m \) je prirodzené číslo a nech \( a \) je celé číslo také, že

\[ (a, m) = 1. \]

Potom existuje číslo \( b \) z množiny \( \{1, 2, \ldots, m - 1\} \) také, že

\[ a \cdot b \equiv 1 \pmod{m}. \]

Inými slovami: ak je číslo \( a \) nesúdeliteľné s modulom \( m \), potom má modulo \( m \) násobkový inverzný prvok.

Poznámka

Táto veta hovorí presne to, čo potrebujeme pre grupu pri násobení. Ak chceme, aby každý prvok mal inverz, nestačí sa pozerať na ľubovoľné zvyšky. Musíme sa obmedziť na tie, ktoré sú s modulom nesúdeliteľné.

Poznámka

Práve preto je redukovaný zvyškový systém prirodzenou množinou pre násobenie modulo \( m \).

Dôkaz

Predpokladáme, že

\[ (a, m) = 1. \]

To znamená, že čísla \( a \) a \( m \) sú nesúdeliteľné. Zo známej vlastnosti o najväčšom spoločnom deliteľovi vyplýva, že existujú celé čísla \( x \) a \( y \) také, že

\[ a \cdot x + m \cdot y = 1. \]

Tento vzťah je veľmi dôležitý. Hovorí, že číslo \( 1 \) vieme zapísať ako celočíselnú kombináciu čísel \( a \) a \( m \).

Teraz číslo \( x \) vydelíme číslom \( m \) so zvyškom. Teda existujú celé čísla \( q \) a \( b \) tak, že

\[ x = q \cdot m + b, \]

pričom \( b \) patrí do množiny \( \{0, 1, \ldots, m - 1\} \).

Dosadíme tento zápis do rovnice

\[ a \cdot x + m \cdot y = 1. \]

Dostaneme

\[ a(qm + b) + my = 1. \]

Po roznásobení:

\[ aqm + ab + my = 1. \]

Členy obsahujúce \( m \) spojíme:

\[ ab + m(aq + y) = 1. \]

To znamená, že rozdiel medzi číslom \( ab \) a číslom \( 1 \) je násobkom \( m \). Inak povedané,

\[ ab \equiv 1 \pmod{m}. \]

Tým sme našli číslo \( b \), ktoré je inverzným prvkom k \( a \) modulo \( m \).

Dôkaz je hotový.

4. Grupa \( (Z_m^{*}, \cdot) \)

Poznámka

Predchádzajúca veta ukázala, že každý prvok redukovaného zvyškového systému má inverz. Teraz možno sformulovať hlavný výsledok.

Veta

Pre každé prirodzené číslo \( m \) tvorí dvojica

\[ (Z_m^{*}, \cdot) \]

komutatívnu grupu vzhľadom na násobenie modulo \( m \).

Poznámka

Takáto komutatívna grupa sa nazýva aj Abelova grupa.

Poznámka

Tvrdenie hovorí, že na množine všetkých zvyškov nesúdeliteľných s \( m \) vieme násobiť modulo \( m \) tak, že sú splnené všetky grupové axiómy:

• operácia je uzavretá,
• je asociatívna,
• existuje neutrálny prvok,
• každý prvok má inverzný prvok,
• a navyše operácia je komutatívna.

Poznámka

To je veľmi silný výsledok. Znamená totiž, že redukovaný zvyškový systém nie je len náhodná množina čísel, ale plnohodnotná algebraická štruktúra.

Dôkaz

Treba overiť jednotlivé vlastnosti.

1. Asociativita

Násobenie celých čísel je asociatívne. Ak teda násobíme zvyšky modulo \( m \), asociativita sa zachováva. Pre prvky \( a, b, c \) platí

$$ (a \cdot b) \cdot c \equiv a \cdot (b \cdot c) \pmod{m}. $$

Táto vlastnosť je prevzatá z obyčajného násobenia.

1. Komutatívnosť

Rovnako aj komutatívnosť sa dedí z obyčajného násobenia celých čísel. Platí

$$ a \cdot b \equiv b \cdot a \pmod{m}. $$

1. Neutrálny prvok

Neutrálnym prvkom je číslo \( 1 \), pretože pre každý prvok \( a \) zo \( Z_m^{*} \) platí

$$ a \cdot 1 \equiv 1 \cdot a \equiv a \pmod{m}. $$

Zároveň číslo \( 1 \) patrí do \( Z_m^{*} \), lebo

$$ (1, m) = 1. $$

1. Inverzný prvok

Ak \( a \) patrí do \( Z_m^{*} \), potom podľa predchádzajúcej vety existuje prvok \( b \) taký, že

$$ a \cdot b \equiv 1 \pmod{m}. $$

Prvok \( b \) je teda inverzný prvok k prvku \( a \).

Tým sú splnené všetky potrebné podmienky.

Dvojica \( (Z_m^{*}, \cdot) \) je teda komutatívna grupa.

5. Inverzné prvky v konkrétnych moduloch

Dôležité

Pojem inverzu modulo \( m \) sa často zapisuje aj tvarom „\( 1/a \) modulo \( m \)“. Tento zápis však neznamená obyčajné delenie. Znamená číslo \( b \), pre ktoré platí

\[ a \cdot b \equiv 1 \pmod{m}. \]

Príklad

V modulo \( 8 \) platí

\[ \frac{1}{3} \equiv 3 \pmod{8}, \]

pretože

\[ 3 \cdot 3 = 9 \equiv 1 \pmod{8}. \]

Príklad

Rovnako

\[ \frac{1}{5} \equiv 5 \pmod{8}, \]

pretože

\[ 5 \cdot 5 = 25 \equiv 1 \pmod{8}. \]

Príklad

V modulo \( 9 \), kde

\[ Z_9^{*} = \{1, 2, 4, 5, 7, 8\}, \]

platí napríklad

\[ \frac{1}{4} \equiv 7 \pmod{9}, \]

pretože

\[ 4 \cdot 7 = 28 \equiv 1 \pmod{9}. \]

Príklad

A tiež

\[ \frac{1}{5} \equiv 2 \pmod{9}, \]

pretože

\[ 5 \cdot 2 = 10 \equiv 1 \pmod{9}. \]

Poznámka

Takéto výpočty ukazujú, že inverz v modularnej aritmetike sa správa podobne ako prevrátená hodnota pri obyčajnom násobení, len sa všetko deje modulo \( m \).

6. Eulerova funkcia \( \varphi(m) \)

Poznámka

Keďže množina \( Z_m^{*} \) tvorí grupu, je prirodzené pýtať sa, koľko prvkov táto grupa obsahuje.

Definícia

Počet prvkov množiny \( Z_m^{*} \) sa označuje symbolom

\[ |Z_m^{*}| = \varphi(m). \]

Funkcia \( \varphi \) sa nazýva Eulerova funkcia.

Poznámka

Eulerova funkcia \( \varphi(m) \) udáva počet tých čísel z množiny

\[ \{1, 2, \ldots, m - 1\}, \]

ktoré sú s číslom \( m \) nesúdeliteľné.

Poznámka

Inými slovami: \( \varphi(m) \) je počet prvkov redukovaného zvyškového systému modulo \( m \).

Príklad

Pre prvočíslo \( 7 \) platí

\[ \varphi(7) = 6, \]

pretože všetky čísla \( 1, 2, 3, 4, 5, 6 \) sú so \( 7 \) nesúdeliteľné.

Príklad

Pre číslo \( 12 \) platí

\[ \varphi(12) = 4, \]

pretože s číslom \( 12 \) sú nesúdeliteľné len čísla

\[ 1, 5, 7, 11. \]

7. Vzorec pre Eulerovu funkciu

Poznámka

Na výpočet Eulerovej funkcie existuje veľmi užitočný vzorec.

Veta

Ak má číslo \( m \) prvočíselný rozklad

\[ m = p_1^{h_1} \cdot p_2^{h_2} \cdot \ldots \cdot p_k^{h_k}, \]

kde \( p_1, p_2, \ldots, p_k \) sú navzájom rôzne prvočísla, potom platí

\[ \varphi(m) = m \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right). \]

Poznámka

Treba si všimnúť, že vo vzorci vystupujú len rôzne prvočíselné delitele čísla \( m \). Exponenty \( h_1, h_2, \ldots, h_k \) určujú samotné číslo \( m \), ale do súčinového tvaru vstupujú iba prvočísla \( p_1, p_2, \ldots, p_k \).

Prečo to funguje

Aby bolo číslo z intervalu \( 1 \) až \( m - 1 \) nesúdeliteľné s \( m \), nesmie byť deliteľné žiadnym z prvočísel, ktoré delia \( m \).

Najprv zo všetkých \( m \) čísel odstránime násobky \( p_1 \). Tým zostane podiel

\[ 1 - \frac{1}{p_1}. \]

Potom zvyšok obmedzíme o násobky \( p_2 \), a tak ďalej. Výsledkom je práve uvedený súčin.

Poznámka

Ak

\[ m = p_1^{h_1} \cdot p_2^{h_2}, \]

potom

\[ \varphi(m) = m \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right). \]

Prečo to funguje

Tento vzorec možno vidieť aj priamo počítaním:

• z \( m \) čísel je \( \frac{m}{p_1} \) deliteľných číslom \( p_1 \),
• z \( m \) čísel je \( \frac{m}{p_2} \) deliteľných číslom \( p_2 \),
• čísla deliteľné oboma prvočíslami sme odpočítali dvakrát, preto ich raz pripočítame späť; takých je \( \frac{m}{p_1 p_2} \).

Preto

\[ \varphi(m) = m - \frac{m}{p_1} - \frac{m}{p_2} + \frac{m}{p_1 p_2}, \]

čo sa po úprave rovná

\[ m \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right). \]

Príklad

Pre číslo \( 100 = 2^2 \cdot 5^2 \) dostaneme

\[ \varphi(100) = 100 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) \]

\[ = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} \]

\[ = 40. \]

Príklad

Pre číslo \( 1000 = 2^3 \cdot 5^3 \) dostaneme

\[ \varphi(1000) = 1000 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) \]

\[ = 1000 \cdot \frac{1}{2} \cdot \frac{4}{5} \]

\[ = 400. \]

Príklad

Pre číslo \( 99 = 3^2 \cdot 11 \) dostaneme

\[ \varphi(99) = 99 \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{11}\right) \]

\[ = 99 \cdot \frac{2}{3} \cdot \frac{10}{11} \]

\[ = 60. \]

8. Eulerova veta

Poznámka

Keď už vieme, že \( Z_m^{*} \) tvorí grupu a poznáme počet jej prvkov, môžeme formulovať jednu z najdôležitejších viet tejto kapitoly.

Veta

Nech \( m \) je prirodzené číslo a nech \( a \) je celé číslo také, že

\[ (a, m) = 1. \]

Potom platí

\[ a^{\varphi(m)} \equiv 1 \pmod{m}. \]

Táto veta sa nazýva Eulerova veta.

Poznámka

Ak je číslo \( a \) nesúdeliteľné s \( m \), potom po umocnení na exponent \( \varphi(m) \) dostaneme pri delení \( m \) zvyšok \( 1 \).

Poznámka

Je to veľmi dôležitý výsledok, pretože umožňuje nahrádzať veľké mocniny jednoduchším tvarom a zároveň z nej vyplýva praktický vzorec na výpočet inverzu modulo \( m \).

9. Dôkaz Eulerovej vety

Poznámka

Dôkaz je založený na práci s redukovaným zvyškovým systémom.

Dôkaz

Označme

\[ Z_m^{*} = \{a_1, a_2, \ldots, a_{\varphi(m)}\}. \]

To znamená, že \( a_1, a_2, \ldots, a_{\varphi(m)} \) sú všetky prvky redukovaného zvyškového systému modulo \( m \).

Keďže predpokladáme, že

\[ (a, m) = 1, \]

patrí aj číslo \( a \) do grupy \( Z_m^{*} \).

Teraz uvažujme množinu prvkov

\[ a \cdot a_1,\ a \cdot a_2,\ \ldots,\ a \cdot a_{\varphi(m)}, \]

pričom všetko chápeme modulo \( m \).

Chceme ukázať dve veci:

• každý z týchto prvkov patrí do \( Z_m^{*} \),

• žiadne dva z nich nie sú rovnaké modulo \( m \).

• Krok 1: nové prvky opäť patria do \( Z_m^{*} \)

Keďže \( Z_m^{*} \) je grupa vzhľadom na násobenie modulo \( m \), súčin dvoch jej prvkov opäť patrí do \( Z_m^{*} \). Preto každý prvok

$$ a \cdot a_i $$

patrí do \( Z_m^{*} \).

1. Krok 2: tieto prvky sú navzájom rôzne

Predpokladajme, že pre nejaké \( i \) a \( j \) platí

$$ a \cdot a_i \equiv a \cdot a_j \pmod{m}. $$

Keďže \( a \) má v grupe inverzný prvok \( a^{-1} \), môžeme obe strany vynásobiť zľava prvkom \( a^{-1} \). Dostaneme

$$ a^{-1} \cdot (a \cdot a_i) \equiv a^{-1} \cdot (a \cdot a_j) \pmod{m}. $$

Podľa asociativity:

$$ (a^{-1} \cdot a) \cdot a_i \equiv (a^{-1} \cdot a) \cdot a_j \pmod{m}. $$

Keďže

$$ a^{-1} \cdot a \equiv 1 \pmod{m}, $$

dostaneme

$$ 1 \cdot a_i \equiv 1 \cdot a_j \pmod{m}, $$

teda

$$ a_i \equiv a_j \pmod{m}. $$

Ale prvky redukovaného zvyškového systému sú navzájom rôzne, preto musí platiť

$$ i = j. $$

To znamená, že prvky

$$ a \cdot a_1,\ a \cdot a_2,\ \ldots,\ a \cdot a_{\varphi(m)} $$

tvoria len inú permutáciu tej istej množiny \( Z_m^{*} \).

1. Krok 3: vynásobíme všetky prvky

Keďže ide o tú istú množinu len v inom poradí, súčin všetkých prvkov sa nezmení. Teda

$$ (a \cdot a_1)(a \cdot a_2)\ldots(a \cdot a_{\varphi(m)}) \equiv a_1 a_2 \ldots a_{\varphi(m)} \pmod{m}. $$

Na ľavej strane môžeme vyňať všetky faktory \( a \):

$$ a^{\varphi(m)} \cdot (a_1 a_2 \ldots a_{\varphi(m)}) \equiv a_1 a_2 \ldots a_{\varphi(m)} \pmod{m}. $$

Označme

$$ A = a_1 a_2 \ldots a_{\varphi(m)}. $$

Potom máme

$$ a^{\varphi(m)} \cdot A \equiv A \pmod{m}. $$

Teraz prichádza dôležitý krok. Každý prvok \( a_i \) je nesúdeliteľný s \( m \), takže aj ich súčin \( A \) je nesúdeliteľný s \( m \). Preto má \( A \) inverzný prvok modulo \( m \).

Obe strany kongruencie teda môžeme vynásobiť inverzom k \( A \) a dostaneme

$$ a^{\varphi(m)} \equiv 1 \pmod{m}. $$

Tým je Eulerova veta dokázaná.

10. Dôsledok pre výpočet inverzného prvku

Poznámka

Z Eulerovej vety okamžite dostaneme veľmi užitočný dôsledok.

Dôsledok

Ak

\[ (a, m) = 1, \]

potom

\[ \frac{1}{a} \equiv a^{\varphi(m) - 1} \pmod{m}. \]

Prečo to platí

Z Eulerovej vety vieme, že

\[ a^{\varphi(m)} \equiv 1 \pmod{m}. \]

Výraz

\[ a^{\varphi(m)} \]

môžeme napísať ako

\[ a \cdot a^{\varphi(m) - 1}. \]

Teda

\[ a \cdot a^{\varphi(m) - 1} \equiv 1 \pmod{m}. \]

To však presne znamená, že

\[ a^{\varphi(m) - 1} \]

je inverzný prvok k \( a \) modulo \( m \).

Prečo to funguje

Tento dôsledok je veľmi praktický, pretože prevádza hľadanie inverzu na výpočet mocniny modulo \( m \).

11. Výpočet inverzných prvkov pomocou Eulerovej vety

Príklad 1: inverz čísla 11 modulo 100

Chceme vypočítať

\[ \frac{1}{11} \pmod{100}. \]

Najprv zistíme Eulerovu funkciu:

\[ 100 = 2^2 \cdot 5^2, \]

preto

\[ \varphi(100) = 100 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) = 40. \]

Podľa dôsledku Eulerovej vety platí

\[ \frac{1}{11} \equiv 11^{39} \pmod{100}. \]

Teraz počítame po modulo \( 100 \):

\[ 11^2 \equiv 21, \]

\[ 11^4 \equiv 21^2 = 441 \equiv 41, \]

\[ 11^8 \equiv 41^2 = 1681 \equiv 81, \]

\[ 11^{16} \equiv 81^2 = 6561 \equiv 61, \]

\[ 11^{32} \equiv 61^2 = 3721 \equiv 21. \]

Keďže

\[ 39 = 32 + 4 + 2 + 1, \]

dostaneme

\[ 11^{39} \equiv 11^{32} \cdot 11^4 \cdot 11^2 \cdot 11 \]

\[ \equiv 21 \cdot 41 \cdot 21 \cdot 11 \]

\[ \equiv 61 \cdot 21 \cdot 11 \]

\[ \equiv 81 \cdot 11 \]

\[ \equiv 91 \pmod{100}. \]

Preto

\[ \frac{1}{11} \equiv 91 \pmod{100}. \]

Kontrola:

\[ 11 \cdot 91 = 1001 \equiv 1 \pmod{100}. \]

Príklad 2: inverz čísla 17 modulo 100

Chceme vypočítať

\[ \frac{1}{17} \pmod{100}. \]

Opäť platí

\[ \varphi(100) = 40, \]

preto

\[ \frac{1}{17} \equiv 17^{39} \pmod{100}. \]

Počítame mocniny:

\[ 17^2 \equiv 89, \]

\[ 17^4 \equiv 89^2 = 7921 \equiv 21, \]

\[ 17^8 \equiv 21^2 = 441 \equiv 41, \]

\[ 17^{16} \equiv 41^2 = 1681 \equiv 81, \]

\[ 17^{32} \equiv 81^2 = 6561 \equiv 61. \]

Keďže

\[ 39 = 32 + 4 + 2 + 1, \]

máme

\[ 17^{39} \equiv 17^{32} \cdot 17^4 \cdot 17^2 \cdot 17 \]

\[ \equiv 61 \cdot 21 \cdot 89 \cdot 17 \]

\[ \equiv 81 \cdot 89 \cdot 17 \]

\[ \equiv 9 \cdot 17 \]

\[ \equiv 53 \pmod{100}. \]

Teda

\[ \frac{1}{17} \equiv 53 \pmod{100}. \]

Kontrola:

\[ 17 \cdot 53 = 901 \equiv 1 \pmod{100}. \]

Príklad 3: inverz čísla 19 modulo 1000

Chceme vypočítať

\[ \frac{1}{19} \pmod{1000}. \]

Najprv určime Eulerovu funkciu:

\[ 1000 = 2^3 \cdot 5^3, \]

preto

\[ \varphi(1000) = 1000 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) = 400. \]

Dostávame

\[ \frac{1}{19} \equiv 19^{399} \pmod{1000}. \]

Použijeme opakované umocňovanie:

\[ 19^2 \equiv 361, \]

\[ 19^4 \equiv 361^2 \equiv 321, \]

\[ 19^8 \equiv 321^2 \equiv 41, \]

\[ 19^{16} \equiv 41^2 \equiv 681, \]

\[ 19^{32} \equiv 681^2 \equiv 761, \]

\[ 19^{64} \equiv 761^2 \equiv 121, \]

\[ 19^{128} \equiv 121^2 \equiv 641, \]

\[ 19^{256} \equiv 641^2 \equiv 881 \pmod{1000}. \]

Keďže

\[ 399 = 256 + 128 + 8 + 4 + 2 + 1, \]

dostaneme

\[ 19^{399} \equiv 19^{256} \cdot 19^{128} \cdot 19^8 \cdot 19^4 \cdot 19^2 \cdot 19 \]

\[ \equiv 881 \cdot 641 \cdot 41 \cdot 321 \cdot 361 \cdot 19 \]

\[ \equiv 579 \pmod{1000}. \]

Teda

\[ \frac{1}{19} \equiv 579 \pmod{1000}. \]

Kontrola:

\[ 19 \cdot 579 = 11001 \equiv 1 \pmod{1000}. \]

Príklad 4: inverz čísla 7 modulo 99

Chceme vypočítať

\[ \frac{1}{7} \pmod{99}. \]

Najprv vypočítame Eulerovu funkciu:

\[ 99 = 3^2 \cdot 11, \]

preto

\[ \varphi(99) = 99 \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{11}\right) = 60. \]

Podľa dôsledku Eulerovej vety platí

\[ \frac{1}{7} \equiv 7^{59} \pmod{99}. \]

Počítame mocniny:

\[ 7^2 \equiv 49, \]

\[ 7^4 \equiv 49^2 = 2401 \equiv 25, \]

\[ 7^8 \equiv 25^2 = 625 \equiv 31, \]

\[ 7^{16} \equiv 31^2 = 961 \equiv 70, \]

\[ 7^{32} \equiv 70^2 = 4900 \equiv 49 \pmod{99}. \]

Keďže

\[ 59 = 32 + 16 + 8 + 2 + 1, \]

dostaneme

\[ 7^{59} \equiv 7^{32} \cdot 7^{16} \cdot 7^8 \cdot 7^2 \cdot 7 \]

\[ \equiv 49 \cdot 70 \cdot 31 \cdot 49 \cdot 7 \]

\[ \equiv 64 \cdot 31 \cdot 49 \cdot 7 \]

\[ \equiv 4 \cdot 49 \cdot 7 \]

\[ \equiv 97 \cdot 7 \]

\[ \equiv 85 \pmod{99}. \]

Teda

\[ \frac{1}{7} \equiv 85 \pmod{99}. \]

Kontrola:

\[ 7 \cdot 85 = 595 \equiv 1 \pmod{99}. \]