Dělitelnost
•  Nechť a, b G Z. Řekneme, že a dělí b, jestliže existuje q G Z takové, že b = a ■ q. Značíme a\b.
•  Nechť a, 6, m G Z, d G N. Řekneme, že m je společný dělitel čísel a a b, jestliže m\a A m\b. Řekneme, že d je největší společný dělitel a ab, jestliže je d společným dělitelem a ab a zároveň, je-li m libovolným společným dělitelem čísel a, b, pak m\d. Značíme D(a, b) = d.
•  Zbytkový tvar čísla: a, b, q, r G Z
a = b ■ q + r, 0 <r < |fe|.
•  Bezoutova rovnost: a, 6 G Z  =>  3 a;, y G Z;
D(a,b) = a ■ x + b ■ y
•  Nesoudělná čísla a, 6 G Z jsou taková čísla, pro která platí D(a, 6) = 1.
•  Prvočíslo je takové číslo, které je dělitelné pouze číslem 1 a sebou samým.
•  Každé přirozené číslo lze rozložit na součin pročísel a to jednoznačně až na pořadí činitelů. Zápis n = Pi1---p'^k, kde Pi,P2, ■ ■ ■ ,Pk jsou navzájem různá prvočísla, čni, CK2,..., CKfc G No se nazývá kanonický rozklad čísla n.
•  ip : N —> N je tzv. Eulerova funkce; Vn G N; <p(ri) udává počet přirozených čísel menších nebo rovných n, která jsou s n nesoudělná. Klademe ip(l) = 1.
1.  Jsou-li m,n nesoudělná přirozená čísla, pak ip(mn) = <p(m)<p(ri), tj. Eulerova funkce je multiplikativní.
2.  Je-li p prvočíslo, pak
<P(P) =P-1-
3.  Je-li p prvočíslo a k kladné celé číslo, pak
<p(pk)=pk-1(p-l).
4.  Je-li n > 1 přirozené číslo a n = p"1 ■ ■ -p^ jeho kanonický rozklad, pak
<p(n) = pT~\pi - 1)pT~1(P2 - 1)'' -pT\Pk - 1),
resp.
<p(n) = {pT -pT'^ÍpT -P?-1)---^ -P?"1)-
•  Euklidův algoritmus pro hledání největšího společného dělitele čísel a, b:
a = bq\ + r\                            =>     r\ = 0 => b\a, a tedy D(a, b) = b
r\ / 0     =>     6 = ri(?2 + ?"2     ^     ^2 = 0,                  pak D(a, b) = r\
r2 / 0     ^     n = r2(?3 + ^3
rľn—2 — fn—lQn   <   Tn
rn-i = rnqn+i + 0,                                  pak D{a, b) = rn.
1. Euklidovým algoritmem určete největší společný dělitel čísel 1128 a 291. Určete koeficienty x,y
1
v Bezoutově nerovnosti. Kongruence
a, b G Z, m G N, pak řekneme, že a je kongruentní s b modulo m, píšeme a = b (mod m), jestliže a i b dávají po dělení m stejný zbytek.
a = b (mod m)  <ř» a = b + m ■ q, g G Z <^m\(a — b)
Relace kongruence je na množině Z reflexivní, symetrická a tranzitivní (je to relace ekvivalence) . Dále platí:
a = b (mod m) c = d (mod m)
ara = bn (mod m)          a + km = b (mod m)
ka = kb (mod fem)                 a = b + ml (mod m)
fca = kb (mod m)         a + fem = b + ml (mod m)
afc = bk (mod m)  A -D(fc, m) = 1     =>          a = 6 (mod m)                    fc, Z G Z
Eulerova věta: Nechť a, m G Z, m > 1; D(a, m) = 1. Pak
av("») = i (mod m).
a + c = 6 + d (mod m)
a — c = b — d (mod m)
a ■ c = b ■ d (mod m)
2.  Určete zbytek po dělení čísla 250 + 350 + 450 číslem 17.
3.  Určete zbytek po dělení čísla Í44  + 55  J číslem 17.
4.  Je číslo 260 + 730 dělitelné číslem 13?
5.  Určete poslední cifru v dekadickém zápisu čísla 77 .
ii9
6.  Určete poslední cifru v dekadickém zápisu čísla 1713
7.  Určete všechna řešení lineární kongruence
4x = 1 (mod 15)
Zbytkové třídy
Značí se Zra = {[0]ra, [l]n, [2}n,... ,[n — l]n}, kde [k]n značí množinu čísel, které po dělení číslem n dávají zbytek k.
[a]n + [b]n = [a + b]n [a]n ■ [b]n = [a ■ b]n
(Zra, +) je abelovská grupa, (Zra, •) je komutativní pologrupa s neutrálním prvkem [l]ra. Je-li n prvočíslo, pak (Z*n, •) je abelovská grupa. Pokud n není prvočíslo, pak (Z*, •), kde Z^ je množina invertibilních prvků, je abelovská grupa.
8. Určete [17]^.
2
Permutace
•  bijektivní zobrazení A na A, kde A uvažujeme neprázdnou konečnou podmnožinu N.
•  n G N; množina všech permutací tvoří grupu, která je pro n > 3 nekomutativní; má rú prvků.
•  Libovolnou permutaci můžeme rozložit na součin nezávislých cyklů.
•   Cyklus délky 2 = transpozice.
•  Každou permutaci můžeme rozložit na součin transpozic. Pokud je počet transpozic lichý, pak mluvíme o liché permutaci, pokud je sudý, pak o sudé perumutaci.
•  Inverze - dvojice prvků a, b tak, že
a <b A i:(a) > 7r(6)
•  Parita = znaménko permutace sgn(-7r) = (—l)ra; n udává počet inverzí. Pro dvě permutace platí
sgn(-7T o 7r') = sgn("7r) • sgn-zr').
Je-li permutace tt součinem nezávislých cyklů tt = n\ o tt2 o • • • o 7rra, délka cyklu ■Kí = ki + 1:
m
sgn(vr) = JJ(—1)** = (-l)E^ifci í=i
9. Jsou dány permutace sat:
_ íl    234567 8\     (l    234567 8\ SV4 132856 7J'       ^ V5 4 2 3 7 18 6J
(a)  Rozložte s a í na součin nezávislých cyklů.
(b)   Spočtěte součiny soíaíos.
(c)  Určete inverzní prvky s_1,í_1.
(d)   Spočtěte permutaci (s120 o i-3)17.
(e)  Permuteace s, t rozložte na součin transpozic a určete jejich paritu.
Symeetrie logotypů (obrazců)
Ta - translace o vektror a; Ry, - otočení o úhel <p; Z\ - zrcadlení vůči přímce l procházej		ící počátkem.					
Symetrie tvoří grupu.							
Dihedrální grupy řádu 2k pravidelných fc-ůhelníků Ü2k-	- grupy	symetrií s k	různými	rotacemi	a K	zrcadleními.	U
10. Popište grupu symetrií čtverce.
3