Druhý týždeň

Z predpokladu \( \gcd(a, m) = 1 \) vieme podľa Bézoutovej vety, že existujú celé čísla \( x \) a \( y \) tak, že

To je veľmi silný vzťah. Hovorí, že číslo \( 1 \) vieme vyjadriť ako lineárnu kombináciu čísel \( a \) a \( m \).

Teraz číslo \( x \) vydelíme číslom \( m \) so zvyškom. Teda napíšeme

kde \( b \) je zvyšok po delení \( x \) číslom \( m \). Preto platí

Dosadíme tento tvar za \( x \) do rovnosti \( ax + my = 1 \):

Roztvorme zátvorku:

Vyberieme \( m \) pred zátvorku z členov, ktoré ho obsahujú:

Teraz prenesme pozornosť na člen \( ab \). Rovnosť hovorí, že rozdiel \( 1 - ab \) je násobkom čísla \( m \). To znamená, že číslo \( m \) delí rozdiel \( ab - 1 \). Teda

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

Ešte si všimnime, že \( b \) nemôže byť \( 0 \). Keby bolo \( b = 0 \), dostali by sme

čo nemôže byť rovné \( 1 \) modulo \( m \). Preto naozaj platí

Tým je veta dokázaná.

Treba overiť vlastnosti grupy jednu po druhej.

Asociativita

Asociativita násobenia modulo \( m \) vyplýva z asociativity obyčajného násobenia celých čísel. Keď násobíme tri prvky a potom berieme zvyšok modulo \( m \), nezáleží na tom, ako zátvorky rozložíme.

Teda pre všetky \( a, b, c \) platí

Komutatívnosť

Násobenie celých čísel je komutatívne, teda

Po prechode na zvyšky modulo \( m \) zostáva táto vlastnosť zachovaná:

Neutrálny prvok

Neutrálnym prvkom je číslo \( 1 \), pretože pre každý prvok \( a \) z množiny \( \mathbb{Z}_m^{*} \) platí

Zároveň číslo \( 1 \) patrí do \( \mathbb{Z}_m^{*} \), lebo \( \gcd(1, m) = 1 \).

Inverzný prvok

Nech \( a \in \mathbb{Z}_m^{*} \). To znamená, že \( \gcd(a, m) = 1 \).

Podľa predchádzajúcej vety potom existuje \( b \) také, že

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

Navyše z rovnosti

pre nejaké celé číslo \( t \) vidíme, že každý spoločný deliteľ čísel \( b \) a \( m \) by musel deliť aj pravú stranu, teda číslo \( 1 \). Preto

čiže aj \( b \) patrí do \( \mathbb{Z}_m^{*} \).

Tým je ukázané, že každý prvok má inverzný prvok v tej istej množine.

Všetky podmienky grupy sú splnené, a preto \( (\mathbb{Z}_m^{*}, \cdot) \) tvorí komutatívnu grupu.

Nech

To znamená, že \( a_1, a_2, \dots, a_{\varphi(m)} \) sú všetky zvyšky modulo \( m \), ktoré sú s \( m \) nesúdeliteľné.

Teraz vezmime pevné číslo \( a \) také, že

Pozrime sa na prvky

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

Najprv ukážeme, že tieto nové prvky sú navzájom rôzne. Predpokladajme, že pre nejaké indexy \( i \) a \( j \) platí

Keďže \( \gcd(a, m) = 1 \), číslo \( a \) má modulo \( m \) inverzný prvok. Označme ho \( a^{-1} \).

Vynásobme obe strany kongruencie zľava týmto inverzným prvkom:

Použijeme asociativitu:

Keďže \( a^{-1}a \equiv 1 \pmod{m} \), dostaneme

teda

Ale prvky \( a_1, a_2, \dots, a_{\varphi(m)} \) boli všetky rôzne. Preto z toho vyplýva, že aj prvky

sú všetky navzájom rôzne modulo \( m \).

Ďalej si všimnime, že každý prvok \( aa_i \) je opäť nesúdeliteľný s \( m \), lebo súčin dvoch čísel nesúdeliteľných s \( m \) je opäť nesúdeliteľný s \( m \).

Máme teda \( \varphi(m) \) rôznych prvkov, ktoré všetky patria do \( \mathbb{Z}_m^{*} \).

Ale \( \mathbb{Z}_m^{*} \) má práve \( \varphi(m) \) prvkov. Preto množina

musí byť tá istá množina ako

len v inom poradí.

Keďže ide o tie isté prvky v inom poradí, ich súčin je modulo \( m \) rovnaký. Teda

Na ľavej strane sa číslo \( a \) vyskytuje \( \varphi(m) \)-krát, takže môžeme napísať

Označme si

Potom dostaneme

Teraz ukážeme, prečo môžeme faktor \( A \) skrátiť. Každý prvok \( a_i \) je nesúdeliteľný s \( m \). Preto aj ich súčin \( A \) je nesúdeliteľný s \( m \). To znamená, že \( A \) má modulo \( m \) inverzný prvok.

Môžeme teda obe strany kongruencie vynásobiť inverzným prvkom k \( A \) a dostaneme

Tým je Eulerova veta dokázaná.

Počet čísel z \( \{0, 1, \dots, m - 1\} \), ktoré sú deliteľné \( p_1 \), je

Počet čísel deliteľných \( p_2 \) je

Čísla deliteľné oboma prvočíslami sú deliteľné súčinom \( p_1p_2 \), a tých je

Preto počet čísel, ktoré nie sú nesúdeliteľné s \( m \), je

Počet čísel nesúdeliteľných s \( m \) teda dostaneme odčítaním od celkového počtu \( m \):

Vytkneme \( m \):

Tento výraz sa rozkladá na

Tým je dôkaz hotový.

Z predpokladu \( \gcd(a, m) = 1 \) vieme podľa Bézoutovej vety, že existujú celé čísla \( x \) a \( y \) tak, že

To je veľmi silný vzťah. Hovorí, že číslo \( 1 \) vieme vyjadriť ako lineárnu kombináciu čísel \( a \) a \( m \).

Teraz číslo \( x \) vydelíme číslom \( m \) so zvyškom. Teda napíšeme

kde \( b \) je zvyšok po delení \( x \) číslom \( m \). Preto platí

Dosadíme tento tvar za \( x \) do rovnosti \( ax + my = 1 \):

Roztvorme zátvorku:

Vyberieme \( m \) pred zátvorku z členov, ktoré ho obsahujú:

Teraz prenesme pozornosť na člen \( ab \). Rovnosť hovorí, že rozdiel \( 1 - ab \) je násobkom čísla \( m \). To znamená, že číslo \( m \) delí rozdiel \( ab - 1 \). Teda

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

Ešte si všimnime, že \( b \) nemôže byť \( 0 \). Keby bolo \( b = 0 \), dostali by sme

čo nemôže byť rovné \( 1 \) modulo \( m \). Preto naozaj platí

Tým je veta dokázaná.

Treba overiť vlastnosti grupy jednu po druhej.

Asociativita

Asociativita násobenia modulo \( m \) vyplýva z asociativity obyčajného násobenia celých čísel. Keď násobíme tri prvky a potom berieme zvyšok modulo \( m \), nezáleží na tom, ako zátvorky rozložíme.

Teda pre všetky \( a, b, c \) platí

Komutatívnosť

Násobenie celých čísel je komutatívne, teda

Po prechode na zvyšky modulo \( m \) zostáva táto vlastnosť zachovaná:

Neutrálny prvok

Neutrálnym prvkom je číslo \( 1 \), pretože pre každý prvok \( a \) z množiny \( \mathbb{Z}_m^{*} \) platí

Zároveň číslo \( 1 \) patrí do \( \mathbb{Z}_m^{*} \), lebo \( \gcd(1, m) = 1 \).

Inverzný prvok

Nech \( a \in \mathbb{Z}_m^{*} \). To znamená, že \( \gcd(a, m) = 1 \).

Podľa predchádzajúcej vety potom existuje \( b \) také, že

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

Navyše z rovnosti

pre nejaké celé číslo \( t \) vidíme, že každý spoločný deliteľ čísel \( b \) a \( m \) by musel deliť aj pravú stranu, teda číslo \( 1 \). Preto

čiže aj \( b \) patrí do \( \mathbb{Z}_m^{*} \).

Tým je ukázané, že každý prvok má inverzný prvok v tej istej množine.

Všetky podmienky grupy sú splnené, a preto \( (\mathbb{Z}_m^{*}, \cdot) \) tvorí komutatívnu grupu.

Nech

To znamená, že \( a_1, a_2, \dots, a_{\varphi(m)} \) sú všetky zvyšky modulo \( m \), ktoré sú s \( m \) nesúdeliteľné.

Teraz vezmime pevné číslo \( a \) také, že

Pozrime sa na prvky

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

Najprv ukážeme, že tieto nové prvky sú navzájom rôzne. Predpokladajme, že pre nejaké indexy \( i \) a \( j \) platí

Keďže \( \gcd(a, m) = 1 \), číslo \( a \) má modulo \( m \) inverzný prvok. Označme ho \( a^{-1} \).

Vynásobme obe strany kongruencie zľava týmto inverzným prvkom:

Použijeme asociativitu:

Keďže \( a^{-1}a \equiv 1 \pmod{m} \), dostaneme

teda

Ale prvky \( a_1, a_2, \dots, a_{\varphi(m)} \) boli všetky rôzne. Preto z toho vyplýva, že aj prvky

sú všetky navzájom rôzne modulo \( m \).

Ďalej si všimnime, že každý prvok \( aa_i \) je opäť nesúdeliteľný s \( m \), lebo súčin dvoch čísel nesúdeliteľných s \( m \) je opäť nesúdeliteľný s \( m \).

Máme teda \( \varphi(m) \) rôznych prvkov, ktoré všetky patria do \( \mathbb{Z}_m^{*} \).

Ale \( \mathbb{Z}_m^{*} \) má práve \( \varphi(m) \) prvkov. Preto množina

musí byť tá istá množina ako

len v inom poradí.

Keďže ide o tie isté prvky v inom poradí, ich súčin je modulo \( m \) rovnaký. Teda

Na ľavej strane sa číslo \( a \) vyskytuje \( \varphi(m) \)-krát, takže môžeme napísať

Označme si

Potom dostaneme

Teraz ukážeme, prečo môžeme faktor \( A \) skrátiť. Každý prvok \( a_i \) je nesúdeliteľný s \( m \). Preto aj ich súčin \( A \) je nesúdeliteľný s \( m \). To znamená, že \( A \) má modulo \( m \) inverzný prvok.

Môžeme teda obe strany kongruencie vynásobiť inverzným prvkom k \( A \) a dostaneme

Tým je Eulerova veta dokázaná.

Počet čísel z \( \{0, 1, \dots, m - 1\} \), ktoré sú deliteľné \( p_1 \), je

Počet čísel deliteľných \( p_2 \) je

Čísla deliteľné oboma prvočíslami sú deliteľné súčinom \( p_1p_2 \), a tých je

Preto počet čísel, ktoré nie sú nesúdeliteľné s \( m \), je

Počet čísel nesúdeliteľných s \( m \) teda dostaneme odčítaním od celkového počtu \( m \):

Vytkneme \( m \):

Tento výraz sa rozkladá na

Tým je dôkaz hotový.