Diskrétní matematika pro modulární grupy

Prerekvizita k tomuto článku – modulo.

Modulární grupy, už byly sice probrány zde, ale daný článek obsahoval hodně různých konceptů najednou – v tomto jsou pro větší přehlednost jen věty, které jsou (a budou dále) pro modulární grupy důležité.

Jako první mějme následující větu

Věta o zbytku po dělení: Pro \(a > 0, a \in \mathbb N, b \geq 0\, b \in \mathbb N\) existuje právě jedna dvojice \(q \geq 0, q \in \mathbb N\) a \(0 \leq r < a, r \in \mathbb N\) taková, že \(b = a\cdot q + r\).

Přestože tato věta může vypadat děsivě, říká něco, co velmi pravděpodovně víte. Mějme pro příklad čísla \(a = 7, b = 12\). Potom \(12 = 7 \cdot 1 + 5\).

Defacto totiž provádíme dělení se zbytkem (na základní škole bychom psali, že \(12:7 = 1\) a zbytek je \(5\) ). Je intuitivní, že \(1\) a \(5\) je jediná dvojice splňující tuto rovnost. Tuto větu zde tedy ponecháme bez důkazu.

Eukleidův algoritmus

Dělitel nějakého celého čísla \(k\) je takové číslo, které dělí \(k\) beze zbytku. Důležitou schopností je umět najít největší společný dělitel dvou čísel. Např. čísla \(10\) a \(20\) jsou obě dělitelná čísly \(1, 2, 5, 10\). Největší z těchto čísel je \(10\), takže píšeme \(\gcd(10,20) = 10\) (\(\gcd\) je z anglického greatest common divisor neboli největší společný dělitel).

Co kdybychom ale chtěli najít největší společný dělitel čísel \(8748425498\) a \(111234\)? Mohli bychom si vypsat všechny dělitele obou čísel, pak se podívat na shody a potom vybrat tu největší z nich.

My ale použijeme něco rychlejšího – Eukleidův algoritmus!

Věta: Mějme kladná přirozená čísla \(a,b\) a postupně provádějme dělení se zbytkem (analogicky předešlé větě).
\(a = b \cdot q_0 + r_0\)
\(b = r_0 \cdot q_1 + r_1\)
\(r_0 = r_1 \cdot q_2 + r_2\)
\(.\)
\(.\)
\(.\)
\(r_i = r_{i+1} \cdot q_{i+2}+r_{i+2}\)
\(.\)
\(.\)
\(.\)
\(r_{n-3} = r_{n-2} \cdot q_{n-1}+r_{n-1}\)
\(r_{n-2} = r_{n-1} \cdot q_{n}+r_{n}\)
\(r_{n-1} = r_{n} \cdot q_{n+1}\)

Potom je \(r_n\) největší společný dělitel \(a, b\).

Před důkazem si to zkusme na nějakém příkladu. Mějme čísla \(a = 91\) a \(b = 14\).

Dostáváme \(91 = 14 \cdot 6 +7\). Kde \(q_0 = 6\) a \(r_0 = 7\). Z toho dostáváme \(14 = 7 \cdot 2 + 0 = 7 \cdot 2\). Tedy naše \(r_0\) bylo rovnou největším společným dělitelem, tedy \(\gcd(91,14) = 7\).

Důkaz
První dokažme, že \(r_n\) dělí \(r_{n-1}, r_{n-2},…, r_0, b, a\). Z posledního řádku v Eukleidově algoritmu vidíme, že \(r_n\) dělí pravou stranu, to ale znamená, že musí dělit i levou stranu, tedy musí dělit \(r_{n-1}\).

Podíváme-li se ale na pravou stranu řádku nad tím, vidíme, že jde o součet nějakého násobku \(r_{n-1}\) a \(r_n\), ale obojí je dělitelné \(r_n\), takže i součet je dělitelný \(r_n\), tedy \(r_{n-2}\) je dělitelné \(r_n\).

Analogicky dostáváme, že i všechny řádky nad tím jsou dělitelné \(r_n\), tedy i \(a\) a \(b\) jsou dělitelné \(r_n\). Tím jsme tedy zjistili, že \(r_n\) je nějaký společný dělitel (což znamená, že je menší nebo roven největšímu společnému dělitelli). Pojďme teď ukázat, že jde nutně o největší společný dělitel.

Předpokládejme nyní, že nějaké \(c\) je společný dělitel \(a\) a \(b\). To znamená, že \(a = m \cdot c\) pro nějaké přirozené \(m\) a \(b = n \cdot c\) pro nějaké přirozené \(n\).

To můžeme dosadit do naší první rovnice a dostáváme, že \(m \cdot c = n \cdot c \cdot q_0 + r_0\), odkud \(r_0 = m \cdot c – n \cdot c \cdot q_0 = c \cdot (m – n \cdot q_0)\), tedy to, že i \(r_0\) je dělitelné \(c\), tedy \(r_0 = o \cdot c\) pro nějaké celé \(c\).

To můžeme dosadit do další rovnice a zjistit, že i \(r_1\) je dělitelné \(c\) a tak dále analogicky, až dostáváme, že \(r_n\) je dělitelné \(c\). Z toho ale plyne, že libovolný společný dělitel čísel \(a, b\) (i největší) musí dělit \(r_n\), tedy \(\gcd(a,b) \leq r_n\).

Dohromady tedy dostáváme, že \(\gcd (a,b) \leq r_n \leq \gcd(a,b)\), ale to platí jen tehdy, když je \(r_n = \gcd(a,b)\). Tím je důkaz hotov.

Poznámka: Pokud je největší společný dělitel dvou čísel roven \(1\), pak těmto číslům říkáme čísla nesoudělná.

Bezoutova rovnost

Věta: Pro libovolná přirozená čísla \(a, b\) existují celá \(u, v\) taková, že \(a \cdot u + b \cdot v = \gcd(a,b)\).

Důkaz
Důkaz je relativně triviální. Z předposlední rovnosti z Eukleidova algoritmu můžeme vyjádřit největší společný dělitel čísel \(a,b\) (což víme, že je \(r_n\) ) a dostáváme \(r_n = r_{n-2}-r_{n-1}q_n\). Za \(r_{n-1}\) ale můžeme dosadit z předešlé rovnice, za \(r_{n-2}\) z rovnice před tím a takhle budeme postupně dosazovat, až budeme mít \(r_n = a \cdot u + b \cdot v\). Tím je důkaz hotov.

Tato rovnost se nám bude hodit hlavně pro řešení modulárních rovnic, tj. např. hledejme \(d\) takové, že \(11d \equiv 1 (\bmod 24)\) (tedy poučený čtenář vidí, že hledáme multiplikativní inverzi k \(11\) v \(\mathbb Z_{24}\) ).

Tuto rovnost můžeme přepsat na \(11d – 1 = 24k\), odkud \(11d-24k = 1\). \(k\) ale může být i záporné, takže můžeme klidně řešit rovnici \(11d + 24k = 1\), resp. hledat, pro jaké celočíselné \(d\) platí (s tím, že \(k\) musí být také celočíselné).

Všimněme si, že je přesně ve tvaru Bezoutovy rovnosti (neboť největší společný dělitel \(24\) a \(11\) je opravdu jedna).

Zkusme použít Eukleidův algoritmus na hledání největšího společného dělitele \(24\) a \(11\) a pak použijeme postup analogický tomu v důkazu Bezoutovy rovnosti.

\(24 = 11 \cdot 2 + 2\)
\(11 = 2 \cdot 5 + 1\)
\(2 = 2 \cdot 1\)

Z druhé rovnosti můžeme vyjádřit \(1 = 11-2 \cdot 5\). Máme tedy rovnost podobnou \(11d+24k = 1\), ale ještě tam nějak musíme dostat \(24\). Vyjádřeme dvojku z první rovnosti a dosaďme, dostáváme \(1 = 11-(24-11 \cdot 2) \cdot 5 = 11-24 \cdot 5 + 10 \cdot 11 = 11 \cdot 11 – 24 \cdot 5\), tedy naše hledané \(d = 11\). Neboli multiplikativní inverzí k \(11\) v \(Z_{24}\) je právě \(11\).

Než se posuneme dál, dokažme si malé lemma

Lemma: Nechť \(a,b,c\) jsou kladná přirozená čísla. Pak je \(c\) nesoudělné s \(a \cdot b\) právě tehdy, když je \(c\) nesoudělné s \(a\) i s \(b\).

Důkaz
Nejprve dokážeme implikaci doprava.
Důkaz provedeme sporem, tedy předpokládejme, že \(c\) je nesoudělné s \(a \cdot b\) a zároveň je soudělné s \(a\) (pokud by bylo soudělné s \(b\), důkaz povedeme naprosto analogicky).

Proto, že je \(c\) soudělné s \(a\), můžeme psát \(a = kl, c = ml\) pro nějaká přirozená \(k, l, m\) a \(l > 1\). To by ale znamenalo, že i \(ab\), i \(c\) by bylo dělitelné číslem \(l\), což je spor.

Nyní pro implikaci doleva, tedy předpokládejme, že \(c\) je nesoudělné s \(a\) i s \(b\). Opět postupujme sporem, tedy k tomu předpokládejme, že je soudělné s \(ab\). To ale znamená, že \(c = kl, ab = ml\) pro nějaká celá \(k, l, m\), kde \(l\) je prvočíslo.
Z \(ab = ml\) ale plyne, že \(l\) dělí \(a\) nebo \(b\) (zde ponecháno bez důkazu) a odtud (neboť \(c = kl\) ), že i \(c\) je soudělné s \(a\) nebo s \(b\). To je ovšem spor.

Eulerova funkce

Posledním konceptem probraným v tomto článku bude Eulerova funkce

Def: Nechť \(n\) je přirozené kladné číslo. Symbolem \(\varphi(n)\) označujeme počet takových menších přirozených kladných čísel než \(n\), která jsou s \(n\) nesoudělná.

Pro příklad si spočtěme, kolik je \(\varphi(10)\). To znamená najít taková čísla, která jsou s \(10\) nesoudělná. To jsou čísla \(\{1, 3, 7, 9\}\), tedy dostáváme \(4\) čísla, tedy dostáváme \(\varphi(10) = 4\).

Věta: Nechť je \(p\) prvočíslo. Potom \(\varphi(p) = p-1\).

Důkaz
Důkaz je celkem zřejmý. Protože \(p\) je prvočíslo, musí být nesoudělné se všemi předešlými přirozenými čísly (kdyby bylo s nějakým soudělné, potom se dá nějakým číslem větším než \(1\) beze zbytku vydělit, ale to by znamenalo, že nejde o prvočíslo). Ale kladných přirozených čísel před číslem \(p\) je právě \(p-1\).

Věta: Nechť jsou \(a,b\) nesoudělná přirozená čísla. Potom \(\varphi(a\cdot b) = \varphi(a) \cdot \varphi(b)\).


V tomto případě už důkaz nebude tak jednoduchý, takže jej nejprveme projděme na nějakých konkrétních číslech. Mějme \(a = 8, b = 3\). Tvrdím, že \(\varphi(8 \cdot 3) = \varphi(24) = \varphi(8) \varphi(3) = 4 \cdot 2 = 8\).

Napišme si takovouto tabulku:


\[ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \end{array} \]

V prvním řádku je právě \(\varphi(8)\) čísel nesoudělných s číslem \(a = 8\). Uvědomme si dále dvě důležité věci. Pod sebou jsou vždy čísla od sebe vzdálena právě od \(8\). A také platí, že je-li nějaké číslo nesoudělné s \(8\), pak ať k němu přičtu, kolik osmiček chci, bude stále nesoudělné s číslem \(8\). Takže ten sloupec, který začíná číslem nesoudělným s \(8\), obsahuje jen čísla nesoudělná s \(8\).

Napišme si tedy do tabulky jen tyto čtyři sloupce (v ostatních sloupcích jsou čísla soudělná s osmičkou, tedy i s číslem \(24\) ):

\[ \begin{array}{cccc} 1 & 3 & 5 & 7 \\ 9 & 11 & 13 & 15 \\ 17 & 19 & 21 & 23 \end{array} \]

Teď musíme vybrat jen ta čísla, pro která platí, že jsou nesoudělná i s trojkou (kdyby byla soudělná s trojkou, jsou soudělná i s číslem \(24\) ). Vidíme, že v každém sloupci jsou právě dvě čísla nesoudělná s \(3\), ale pro ilustraci ukažme, jak budeme postupovat v obecném důkazu.

Připomeňme si původní tabulku:

\[ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \end{array} \]

A nyní ukažme, že každý sloupec obsahuje právě \(\varphi(b) = \varphi(3)\) čísel nesoudělných s \(b = 3\). K tomu musíme ukázat, že dvě libovolná čísla z daného sloupce mají různý zbytek po dělení číslem \(3\). V tomto konkrétním případě to prostě můžeme provést tak, že opravdu všechna čísla v sloupci vydělíme \(3\) a podíváme se na zbytek (jak to dokázat obecně, vizte červenou část níže).

My hledáme čísla \(c\) taková, že jsou nesoudělná s \(a \cdot b = 8 \cdot 3 = 24\). Takové číslo však musí být nesoudělné jak s \(a\), tak s \(b\). Zapišme si naše \(c\) takto \(c = qb + r\), např. tedy \(11 = 3 \cdot 3 + 2\). Vidíme, že \(c\) bude nesoudělné s \(b\) právě tehdy, když bude nesoudělné i s \(r\). Takových čísel však bude v každém sloupci \(\varphi(b) = \varphi(3) = 2\).

Dohromady tedy máme, že z každého ze čtyř sloupců vybereme právě dvě čísla, tedy opravdu \(\varphi(24) = 4 \cdot 2 = 8\).

Důkaz
A nyní zkusme obecný důkaz. Mějme tedy nějaká \(a,b\) nesoudělná a napišme si obdobně tabulku:

\[ \begin{array}{ccccc} 1 & 2 & 3 & … & a \\ a +1 & a+2 & a+3 & … & 2a \\ 2a+1 & 2a + 2 & 2a+3 & … & 3a \\ . & . & . & & . \\ . & . & . & & . \\ . & . & . & & . \\ (b-1)a + 1 & (b-1)a+2 & (b-1)a + 3 & … & ab \end{array} \]

V prvním řádku je právě \(\varphi(a)\) čísel nesoudělných s \(a\). Pokud je ale nějaké číslo \(c\) nesoudělné s \(a\), tak i \(c+ka\) je nesoudělné s \(a\) – ale celý sloupec je dle konstrukce čísel vyjádřitelných právě jako \(c+ka\), takže celý sloupec je plný nesoudělných čísel s \(a\).

Nyní ukažme, že každý sloupec obsahuje právě \(\varphi(b)\) čísel nesoudělných s \(b\). Mějme tedy nějaká dvě čísla se stejným zbytkem po dělení číslem \(b\) ze stejného sloupce, \(ra + k, sa+k\), kde \(0 < k \leq a, 0 \leq r \leq s < b\) a ukažme, že musí být stejná.

Potom je číslem \(b\) dělitelné číslo \(ra+k-(sa+k) = (r-s)a\). Ale z toho, že \(a\) a \(b\) jsou nesoudělná čísla, plyne, že číslem \(b\) je dělitelné číslo \(r-s\). Podle předpokladů ale zároveň platí, že \(|r-s|<b\), tedy nutně \(|r-s| = 0\) neboli \(r = s\).

Takže v daném sloupci nikdy nemůžou mít dvě různá čísla stejný zbytek po dělení číslem \(b\). Číslo \(c \) je však nesoudělné s \(b\) v tom případě, když zbytek \(r\) po dělení čísla \(b\) číslem \(c\) je nesoudělný s \(b\), jak jsme již zdůvodnili v našem příkladu.

Pro \(\varphi(a \cdot b)\) tedy vybíráme z \(\varphi(a)\) sloupců právě \(\varphi(b)\) čísel, tedy dohromady je jich \(\varphi(a) \varphi(b)\), čímž je důkaz hotov.

 

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *