24.2.

1. Základní algebraické struktury a dělitelnost

Připomeňme, že (asociativním) okruhem (s jednotkou) rozumíme nějakou množinu R opatřenou dvojicí binárních operací + a ·, jednou unární operaci − a dvěma význačnými prvky 0 a 1, které splňují podmínky

(1) (R, +, −, 0) je komutativní grupa,

(2) operace · je asociativní a a · 1 = 1 · a = a pro všechna a ∈ R,

(3) a · (b + c) = a · b + a · c a (b + c) · a = b · a + c · a pro všechna a, b, c ∈ R. Je-li operace · komutativní, mluvíme o komutativním okruhu. Konkrétní zápis okruhu jako (univerzální) algebry není ustálen, my zvolíme například zápis (R, +, ·, −, 0, 1).

Je-li (R, +, ·, −, 0, 1) komutativní okruh, nazveme množinu I ⊆ R ideálem, jestliže (1) I je podgrupou grupy (R, +, −, 0) a

(2) i · r ∈ I pro všechna i ∈ I a r ∈ R.

Komutativní okruh (R, +, −, 0, ·, 1) nazveme oborem integrity, platí-li pro každou dvojici nenulových prvků a, b ∈ R, že a · b ≠ 0. O oboru integrity hlavních ideálů mluvíme v případě, že jsou všechny jeho ideály hlavní, tj. tvaru iR = {i · r| r ∈ R}. Dobře známými příklady oborů integrity hlavních ideálů jsou okruhy celých čísel (Z, +, −, 0, ·, 1) či polynomů o jedné neznámé nad libovolným komutativním tělesem

Buď (R, +, −, 0, ·, 1) obor integrity a a, b ∈ R. V souladu s pojmem dělitelnosti na celých číslech nebo reálných polynomech řekneme, že a dělí b (píšeme a/b), existuje-li takové c ∈ R, že b = a · c. Dále řekneme, že je a asociováno s b (píšeme a∥b), jestliže a/b a b/a.

Všimněme si, že v oboru integrity 0 dělí pouze opět 0 (a tedy s 0 je asociována jen 0), obvykle ji proto z našich úvah budeme vypouštět. V následujícívh úvahách si nejprve uvědomíme, jak vyjádřit otázky dělitelnosti pomocí ideálů.

1.1. Nechť (R, +, −, 0, ·, 1) je obor integrity a a, b ∈ R \ {0}.

(1) Dokažte, že a/b, právě když bR ⊆ aR.

(2) Dokažte, že a∥b, právě když aR = bR.

(3) Dokažte, že a∥b, právě když existuje invertibilní u ∈ R, pro které b = a · u.

(1) (⇒) Existuje-li c ∈ R, pro které b = a · c, pak b ∈ aR, a proto i b · s ∈ aR pro každé s ∈ R.

(⇐) Máme-li bR ⊆ aR, potom b = b · 1 ∈ bR ⊆ aR, tedy existuje takové c ∈ R, že b = a · c

(2) Stačí dvakrát použít (1).

(3) (⇒) Protože a/b, existuje u ∈ R, pro něž b = a·u, a protože také b/a existuje takové v ∈ R, že a = b · v, Dosadíme-li do první rovnosti, dostaneme

b = a · u = (b · v) · u = b · (v · u),

a proto b · (1 − v · u) = 0. Z definice oboru integrity je 1 − v · u = 0, tedy v · u = 1 a u je invertibilní prvek.

(⇐) Okamžitě z předpokladu b = a · u máme a/b. Protože a = b · u^{−1}, vidíme, že b/a. □

1.2. Je-li R = (R, +, ·, −, 0, 1) komutativní okruh, dokažte následující tvrzení.

(a) Jsou-li I a J dva ideály okruhu R, pak I + J = {i + j| i ∈ I, j ∈ J} je nejmenší ideál okruhu obsahující ideály I a J.

(b) Je-li I_{0}, I_{1}, … posloupnost ideálů okruhu R, pro které platí, že I_{i} ⊆ I_{i+1} , pak ⋃_{i} I_{i} je rovněž ideál.

(c) Je-li S_{0}, S_{1}, … posloupnost okruhů, pro které platí, že S_{i} je podokruh okruhu S_{i+1} , pak ⋃_{i} S_{i} je okruh s takovými operacemi, že všechny okruhy S_{i} jsou jeho podokruhy.

(a) Nejprve ukážeme, že množina I + J tvoří ideál. Předně 0 = 0 + 0 ∈ I + J. Zvolme r ∈ R a x_{1}, x_{2} ∈ I + J libovolně. Potom existuje i_{1}, i_{2} ∈ I a j_{1}, j_{2} ∈ I, pro něž x_{ν} = i_{ν} + j_{ν}, kde ν = 1, 2, a proto −x_{1} = −i_{ν} + (−j_{ν}) ∈ I + J, dále x_{1} + x_{2} = (i_{1} + i_{2}) + (j_{1} + j_{2}) ∈ I + J a x_{1} · u = a · (r_{1} · u) + b · (s_{1} · u) ∈ aR + bR.

(b) Opět vezměme r ∈ R a a, b ∈ ⋃_{i} I_{i} libovolně. Potom existuje n, pro něž a, b ∈ I_{n}, tudíž 0, −a, a · r, a + b ∈ I_{n} ⊆ ⋃_{i} I_{i}.

(c) Úvaha je obdobná jako v úloze (b), stačí si opět uvědomit, že pro každá dvojici prvků a, b ∈ ⋃_{i} S_{i} existuje n, pro které a, b ∈ S_{n}. □

Obor integrity R je noetherovský, jestliže neobsahuje žádný nekonečný ostře rostoucí řetězec ideálů. Jestliže jsou v oboru všechny ideály hlavní, mluvíme o oboru integrity hlavních ideálů.

1.3. Je-li R = (R, +, −, 0, ·, 1) obor integrity hlavních ideálů, dokažte tvrzení:

(a) Pro každé a, b ∈ R \ {0} aR + bR = cR právě tehdy, když c je NSD(a, b).

(b) R je noetherovský.

(a) (⇒) Předpokládejme, že aR+bR = cR. Potom podle 1.2 máme aR, bR ⊆ cR, a proto podle 1.1 je c/a a c/b. Vezmeme-li d ∈ R, pro něž d/a a d/b, tedy díky 1.1 aR, bR ⊆ dR. Z minimality aR + bR = cR, potom dostáváme, že cR = aR + bR ⊆ dR, tedy d/c.

(⇐) Je-li c je NSD(a, b) a vezmeme-li takové d ∈ R, že aR + bR = dR (to musí existovat, protože každý ideál (R, +, −, 0, ·, 1) je hlavní), pak i d je NSD(a, b), proto jsou podle definice NSD prvky c a d asociovány a 1.1 říká, že aR + bR = dR = cR.

(b) Předpokládejme, že obor není neoetherovský, tedy existuje nekonečný ostře rostoucí řetězec ideálů I_{0}, I_{1}, …, tj. platí, že I_{i} ⊆ I_{i+1} a I_{i} ≠ I_{i+1} . V 1.2(b) jsme dokázali, že je I = ⋃_{i} I_{i} rovněž ideál. Kdyby existovalo c ∈ R, pro něž cR = I, pak by c ∈ I_{n} pro nějaké n, proto I_{n+1} ⊆ I = cR ⊆ I_{n}, což je spor. Tedy ideál I není hlavní. □

Připomeňme, že oborem integrity hlavních ideálů je každé těleso, okruh celých čísel a okruh polynomů jedné neurčité nad tělesem. Jde tedy podle dokázaného tvrzení o noetherovské obory.

25.2.

Okruh polynomů jedné neurčité s celočíselnými koeficienty Z[x] je (například podle Hilbertovy věty o bázi) noetherovský, ovšem ideál xZ[x] + 2Z[x] by v oboru integrity hlavních ideálů musel být generován největším společným dělitelem prvků x a 2, tedy prvkem 1, což zjevně neplatí, tedy Z[x] není obor integrity hlavních ideálů.

1.4. Uvažujme podokruh R = {∑_{i} p_{i}x^{i} ∈ Q[x]| p_{0} ∈ Z} okruhu Q[x].

(a) Rozhodněte, zda R obsahuje nekonečnou posloupnost a_{i} vlastních dělitelů, tj. a_{i+1} /a_{i} a a_{i} není s a_{i+1} asociován,

(b) rozhodněte, zda je R noetherovský,

(c) rozhodněte, zda v R existují ireducibilní rozklady každého neninvertibilního nenulového prvku.

(a) Uvědomme si, že 2^{−n}x ∈ R, 2^{−n}xR ⊆ 2^{−(n+1)} xR, protože 2^{−n}x = 2 · 2^{−(n+1)} x, a 2^{−n}xR ≠ 2^{−(n+1)} xR, protože 2^{−(n+1)} x ∉ 2^{−n}xR, čímž jsme našli nekonečnou posloupnost vlastních dělitelů x/2^{−1}x/ … /2^{−n}x/2^{−(n+1)} x . . ..

(b) V (a) jsme našli rostoucí posloupnost ideálů, tedy R není noetherovský.

(c) Kdyby existoval ireducibilní rozklad x = p_{1} · · · · · p_{n}, pak by právě jeden z polynomů p_{i} = \frac{1}{c} x a součin ostatních by byl roven c, kde c ∈ Z. Ovšem polynom \frac{1}{c} x umíme napsat jako součin \frac{1}{c} x = 2 · \frac{1}{2c}x, kde 2, \frac{1}{2c}x ∈ R nejsou invertibilní, tedy \frac{1}{c} x není inreducibilní a polynom x nelze ireducibilně rozložit. □

Připomeňme, že podokruhy tělesa komplexních čísel Z[i], Z[\sqrt{2}] a Z[\sqrt{3}] jsou eukleidovské s euklidovskými normami ν_{−1}(a + bi) = a^{2} + b^{2}, ν_{2}(a + b\sqrt{2}) = |a^{2} − 2b^{2}| a ν_{3}(a + b\sqrt{2}) = |a^{2} − 2b^{2}|. Dále poznamenejme, že jsou všechny tři normy mulriplikativní, tedy platí ν_{s}(α · β) = ν_{s}(α) · ν_{s}(β) (důkaz je zcela přímočarý).

1.5. Najděte všechny invertibilní prvky okruhu Z[i] a ukažte, že okruh Z[\sqrt{2}] obsahuje nekonečně invertibilních prvků.

Protože prvek α ∈ Z[i] je invertibilní existuje-li β ∈ Z[i], pro nkteré α · β = 1, proto ν(α · β) = 1, tedy ν(α) = 1. Vidíme, že α ∈ {1, −1, i, −i}.

Všimneme si, že invertibilní je právě prvek a + b\sqrt{2} ∈ Z[\sqrt{2}], pro který μ(a + b\sqrt{2}) = 1. Jakmile a^{2} − 2b^{2} = −1, potom (a + b\sqrt{2}) · (−a + b\sqrt{2}) = 2b^{2} − a^{2} = 1, a v případě, kdy a^{2} − 2b^{2} = 1, pak (a + b\sqrt{2}) · (a − b\sqrt{2}) = a^{2} − 2b^{2} = 1. Protože μ(1 + \sqrt{2}) = 1, je i μ((1 + \sqrt{2})^{n}) = 1^{n} = 1 pro každé n, tedy prvky (1 + \sqrt{2})^{n} jsou invertibilní. Přitm 1 + \sqrt{2} > 1, proto (1 + \sqrt{2})^{n} < (1 + \sqrt{2})^{n+1} , tedy jsme našli nekonečnou množinu \{(1+\sqrt{2})^{n}| n ∈ N\} invertibilních prvků oboru (Z[\sqrt{2}], +, −, 0, ·, 1). □

1.6. Dokažte, že okruh Z[\sqrt{5}] není Gaussův.

Stačí uvážit dva rozklady čísla 4 = 2 · 2 = (\sqrt{5} + 1) · (\sqrt{5} − 1), o nichž snadno dokážeme, že jsou ireducibilní, ovšem číslo 2 zřejmě není v Z[\sqrt{5}] asociováno s číslem \sqrt{5} − 1 ani s číslem \sqrt{5} + 1 □

Všimněme si, že pomocí čísel 2, \sqrt{5} − 1, \sqrt{5} + 1 můžeme vytvořit dvojici prvků, která nemá v Z[\sqrt{5}] největší společný dělitel, konkrétně lze vzít dvojici 2(\sqrt{5} + 1)

4. To samozřejmě nutně znamená, že Z[\sqrt{5}] není obor integrity hlavních ideálů. Dále poznamenejme, že okruh Z[\sqrt{5}] je noetherovský, protože tuto vlastnost splňuje okruh Z[x] a náš obor Z[\sqrt{5}] je izomorfní faktoru Z[x]/(x^{2} − 5)Z[x].

3.3.

1.7. Je-li Q[x_{1}] ⊆ Q[x_{1}, x_{2}] ⊆ … někonečný řetězec okruhů (okruh méně neurčitých lze vždy přirozeně chápat jako podokruh okruhu více neurčitých), uvažujme množinu Q[𝕏] = ⋃_{i} Q[x_{1}, …, x_{i}], kde 𝕏 = {x_{1}, x_{2}, … }. Dokažte následující tvrzení.

(a) Q[𝕏] je obor integrity, jehož jsou všechny obory ⋃_{i} Q[x_{1}, …, x_{i}] podokruhy,

(b) Q[𝕏] není noetherovský,

(c) jestliže a ∈ Q[x_{1}, …, x_{n}] a a = b · c, kde b, c ∈ Q[𝕏] \ {0}, pak b, c ∈ Q[x_{1}, …, x_{n}],

(d) v Q[𝕏] neexistuje nekonečná posloupnost vlastních dělitelů (tj. taková, že by každý následující prvek dělil předchozí, ale nebyl by s ním asociován),

(e) v Q[𝕏] neexistuje nekonečný ostře rostoucí řetězec hlavních ideálů,

(f) existují NSD každé dvojice (nenulových a neinvertibilních prvků).

(g) Q[𝕏] je Gaussův.

(a) Plyne okamžitě z 1.2(c).

(b) Položíme I_{0} = {0} a indukcí definujme množinu I_{n+1} = I_{n} + x_{n+1} Q[𝕏]. Zřejmě I_{n+1} ⊆ I_{n}, a protože x_{n+1} ∉ I_{n} máme I_{n+1} ≠ I_{n}. Navíc I_{n} je pro každé n podle 1.2(a) ideál, tedy Q[𝕏] není noetherovský.

(c) Uvažme, že pro každé m lze na každý prvek okruhu Q[𝕏] nahlížet jako na polynom S_{m}[x_{m}], kde S_{m} je podokruh Q[𝕏], který sestává z polynomů neobsahujících (s nenulovým koeficientem) proměnnou x_{m}. Všimněme se, že je S_{m} jako podokruh oboru integrity opět oborem integity. Vezmeme-li b, c ∈ Q[𝕏] \ {0} a předpokládejme, že b ∉ Q[x_{1}, …, x_{n}], pak existuje m > n, pro které b obsahuje neznámou x_{m}, tedy b má jako polynom z oboru S_{m}[x_{m}] kladný stupeň. Tudíž i b · c má jako polynom z oboru S_{m}[x_{m}] má kladný stupeň, a proto b · c ∉ Q[x_{1}, …, x_{n}].

(d) Předpokládejme, že máme posloupnost dělitelů, tj. prvky a_{i} ∈ Q[𝕏], pro které a_{i+1} /a_{i}. Protože existuje n, pro něž a_{1} ∈ Q[x_{1}, …, x_{n}], a a_{i}/a_{1} , platí podle (c), že a_{i} ∈ Q[x_{1}, …, x_{n}] pro všechna i. Díky Gaussově větě víme, že je obor Q[x_{1}, …, x_{n}] Gaussův, proto existje takové m, že a_{i}∥a_{m} pro všechna i > m v okruhu Q[x_{1}, …, x_{n}]. Konečně z pozorování, že prvky asociované v Q[x_{1}, …, x_{n}] jsou nutně asociované i v Q[𝕏] plyne závěr.

(e) Jedná se jen o reformulaci (d) z jazyka dělitelnosti do aritmetiky ideálů (viz tvrzení úlohy 1.1).

(f) Vezmeme-li p, q ∈ Q[𝕏], existuje n, pro které p, q ∈ Q[x_{1}, …, x_{n}]. Protože je obor Q[x_{1}, …, x_{n}] Gaussův, existje v něm NSD(p, q), označme ho d. Zřejmě d dělí p i q v oboru Q[𝕏]. Vezmeme-li e, které dělí p i q v oboru Q[𝕏], potom e ∈ Q[x_{1}, …, x_{n}] podle (c). Protože d je NSD(p, q) v Q[x_{1}, …, x_{n}], nutně e/d v d v oboru Q[x_{1}, …, x_{n}], a tudíž i e/d v oboru Q[𝕏].

(g) Plyne z bodů (d) a (f). □

2. Homomorfismy cyklických grup a řády prvků

Připomeňme, že zobrazení f : G → H grupy (G, ·,^{−1} , 1) do grupy (H, ·,^{−1} , 1) se nazývá homomorfismus, jestliže pro všechna a, b ∈ G platí f(a · b) = f(a) · f(b), f(a^{−1}) = (f(a))^{−1} a f(1) = 1. a

2.1. Dokažte, že zobrazení f : G → H grupy (G, ·,^{−1} , 1) do (H, ·,^{−1} , 1), které splňuje f(a · b) = f(a) · f(b) pro všechna a, b ∈ G, je homomorfismus.

Protože f(1) = f(1 · 1) = f(1) · f(1), stačí rovnost f(1) = f(1) · f(1) přenásobit prvkem f(1)^{−1}, abychom dostali 1 = f(1) · f(1)^{−1} = f(1) · f(1) · f(1)^{−1} = f(1). Dále 1 = f(1) = f(a^{−1} · a) = f(a^{−1}) · f(a) a podobně 1 = f(a) · f(a^{−1}), proto f(a^{−1}) = (f(a))^{−1}. □

17.3.

Jsou-li G, H grupy, označme Hom(G, H) množinu všech homomorfismů G do H.

2.2. Popište všchny prvky množiny

(a) Hom(Z_{30}, Z_{49}),

(b) Hom(Z_{30}, Z_{30}),

(c) Hom(Z_{30}, Z_{600}),

(d) Hom(Z_{30}, Z_{6}),

(e) Hom(Z_{30}, Z_{800}).

Uvažujeme-li homomorfismus φ : Z_{30} → H pro libovolnou konečnou grupu H, všimneme si, že φ(Z_{30}) je podgrupa grupy H, tedy podle Lagrangeovy věty |φ(Z_{30})|/|H|. Využijeme-li 1. větu o izomorfismu, vidíme, že φ(Z_{30}) ≅ Z_{30}/Kerφ, proto opět díky Lagrangeově Větě |φ(Z_{30})| · Kerφ = |Z_{30}| = 30, tudíž |φ(Z_{30})|/30.

(a) Je-li φ : Z_{30} → Z_{49} homomorfismus, z předchozího pozorování vyplývá, že |φ(Z_{30})| dělí číslo 30 i číslo 49, tedy |φ(Z_{30})| = 1. To zamená, že Hom(Z_{30}, Z_{49}) obsahuje pouze nulový homomorfismus. Poznamenejme, že bychom dostali stejný výsledek i kdybychom uvažovali obecné grupy řádu 30 a 49.

(b) Uvažujme homomorfismus φ : Z_{30} → Z_{30}. Jestliže φ(1) = k, snadno nahlédneme, že φ(1 + 1) = φ(1) + φ(1) = (2k)mod 30, φ(2 + 1) = φ(2) + φ(1) = (3k)mod 30,…, tedy φ(a) = (ak)mod 30 pro každé a ∈ Z_{30}. Uvědomili jsme si, že homomorfismus je dán obrazem prvku 1 (nebo jiného generátoru). Naopak, definujeme-li pro libovolné k ∈ Z_{30} zobrazení φ_{k} : Z_{30} → Z_{30} předpisem φ_{k}(a) = (ak)mod 30, vidíme, že

φ_{k}(a+b) = ((a+b)k)mod 30 = ((ak)mod 30+(bk)mod 30)mod 30 = φ_{k}(a)+φ_{k}(b),

tedy jedná se o homomorfismus. Ukázali jsme , že Hom(Z_{30}, Z_{30}) = {φ_{k}| k ∈ Z_{30}}.

(c) Opět mějme homomorfismus φ : Z_{30} → Z_{600}. Všimněme si, že 30/600, tedy existuje právě jedna třicetiprvková podgrupa grupy Z_{600} řádu 30, konkrétně jde o podgrupu

⟨20⟩ = 20Z_{600} = {0, 20, 40, …, 560, 580}.

Obdobně nahlédneme, že i pro každý dělitel d čísla 30 existuje jednoznačně určená podgrupa ⟨\frac{600}{d} ⟩ řádu d, která je zřejmě obsažena v grupě ⟨20⟩. Označíme-li d = |φ(Z_{30})|, vidíme, že φ(Z_{30}) = ⟨\frac{600}{d} ⟩ ⊆ ⟨20⟩, tedy φ(1) ∈ ⟨20⟩. Naopak, zvolíme-li k ∈ Z_{30} definujeme-li zobrazení φ_{k} : Z_{30} → Z_{600} předpisem φ_{k}(a) = (20ka)mod 30, vidíme, že

φ_{k}(a+b) = (20k(a+b)mod 30)mod 600 = ((20ka)+(20kb))mod 600 = φ_{k}(a)+φ_{k}(b),

tedy i tentokrát je φ_{k} homomorfismus. Tím jsme ověřili, že Hom(Z_{30}, Z_{600}) = {φ_{k}| k ∈ Z_{30}}.

(d) Zvolme libovolně φ : Z_{30} → Z_{6}. I tentokrát je homomorfismus určen obrazem prvku 1, a protože 6/30 je zobrazení φ_{k} : Z_{30} → Z_{6} dané předpisem φ_{k}(a) = (ka)mod 6 homomorfismus, neboť

φ_{k}(a + b) = (k(a + b)mod 30)mod 6 = ((ka) + (kb))mod 6 = φ_{k}(a) + φ_{k}(b).

Dokázali jsme, že Hom(Z_{30}, Z_{6}) = {φ_{k}| k ∈ Z_{6}}.

(e) Buď φ : Z_{30} → Z_{800} homomorfismus a položme d = |φ(Z_{30})|. Z úvodního úvahy plyne, že d/NSD(30, 800) = 10, proto obdobnou úvahou jako v případě (c), dostáváme, že φ(Z_{30}) = ⟨\frac{800}{d} ⟩ ⊆ ⟨\frac{800}{10} ⟩⟨80⟩. Zároveň obvyklým argumentem nahlédneme, že je zobrazení φ_{k} : Z_{30} → Z_{800} dané předpisem φ_{k}(a) = (10ka)mod 30 pro každé k ∈ Z_{10} homomorfismus, tedy Hom(Z_{30}, Z_{800}) = {φ_{k}| k ∈ Z_{10}}. □

2.3. Které z homomorfismů uvažovaných v 2.2 jsou prosté a které jsou na?

Uvažujme opět homomorfismus φ : Z_{30} → H pro libovolnou konečnou grupu H. Snadno nahlédneme, že φ je prosté, právě když |φ(Z_{30})| = 30, a φ je na, právě když φ(1) je generátor H. V konkrérních případech to znamená, že

(a) žádný prostý ani surjektivní homomorfismusu Z_{30} do Z_{49} neexistuje;

(b) homomorfismus φ_{k} : Z_{30} → Z_{30} daný předpisem φ_{k}(a) = (ak)mod 30 je prostý, právě když je na a to nastává právě pro k ∈ Z_{30}^{∗} (takových homomorfismů je právě 8);

(c) samozřejmě žádný homomorfismus Z_{30} na Z_{600} neexistuje a homomorfismus φ_{k} : Z_{30} → Z_{600} daný předpisem φ_{k}(a) = (20ka)mod 600 je prostý, právě když k ∈ Z_{30}^{∗} (tedy opět máme 8 prostých homomorfismů);

(d) zřejmě neexistuje žádný prostý homomorfismus Z_{30} na Z_{6} a homomorfismus φ_{k} : Z_{30} → Z_{6} definovaný vztahem φ_{k}(a) = (ka)mod 6 je na Z_{6}, právě když k ∈ Z_{6}^{∗} (tedy epimorfismy jsou zobrazení φ_{1} a φ_{5});

(e) žádný monomorfismus ani epimorfismusu Z_{30} do Z_{800} neexistuje. □

2.4. Určete řád prvku 4 v grupě (Z_{3^{10}}^{∗} , ·,^{−1} , 1).

Předně připomeňme, že řád grupy Z_{3^{10}}^{∗} je φ(Z_{3^{10}}^{∗} ) = (3 − 1)3^{9}, kde φ značí Eulerovu funkci, tedy podle Lagrangeovy věty musí být řád prvku 4 tvaru 2^{α}3^{β} pro α ∈ Z_{2} a β ∈ Z_{9}. Dále poznamenejme, že 4 = 1 + 3 ∈ G = {1 + 3a| a ∈ Z_{3^{9}} } a že je G podgrupa grupy (Z_{3^{10}}^{∗} , ·,^{−1} , 1) řádu 3^{9} (zřejmě jde o prvky nesoudělné s 3, tedy invertibilní v (Z_{3^{10}} , ·, 1), dále je G uzavřená na součiny, obsahuje 1, a protože je G konečné, musí pro každé a existovat n, pro něž (1 + 3a)^{n} = 1, tedy (1 + 3a)^{−1} = (1 + 3a)^{n−1} ∈ G). To znamená, že řád 4 musí dělit řád G, a proto α = 0.

Nyní si zbývá uvědomit, že podle Tvrzení 2.9 z přednášky pro každé přirozené e ≥ 2 a každé liché prvočíslo p platí, že (1 + p)^{p^{e−2}} ≡ 1 + p^{e−1} mod p^{e}, proto 1 + 3 není řádu 3^{i} pro žádné i = 1, …, 8, tudíž je nutně řádu 3^{9}. □

24.3.

2.5. Najděte generátor cyklické grupy (Z_{3^{10}}^{∗} , ·,^{−1} , 1).

V úloze 2.4 jsme zjistili, že podgrupa ⟨4⟩ je řádu 3^{9}, proto snandno pomocí Lagrangeovy věty spočítáme, že [Z_{3^{10}}^{∗} : ⟨4⟩] = \frac{|Z_{3^{10}}^{∗} |}{|⟨4⟩|} = \frac{2·3^{9}}{3^{9}} = 2. Najdeme-li tedy prvek a ∈ Z_{3^{10}}^{∗} , pro který platí, že a ∉ ⟨4⟩ a ⟨4⟩ ⊆ ⟨a⟩, potom to už nutně musí být prvek řádu řádu 2 · 3^{9}, tedy generátor grupy Z_{3^{10}}^{∗} .

Vidíme, že 2 ∉ ⟨4⟩ = {1 + 3a| a ∈ Z_{3^{9}} } a 2^{2} = 4, proto ⟨4⟩ ⊆ ⟨2⟩. Hledaným generátorem je tedy například prvek 2. □

2.6. Rozhodněte, zda je prvek b generátorem cyklické grupy (Z_{3^{10}}^{∗} , ·,^{−1} , 1), jestliže (a) b = 2^{15},

(b) b = 2^{16},

(c) b = 2^{17},

(d) b = 13,

(e) b = 3^{10} − 2.

(a) - (c) Máme-li generátor 2 cyklické grupy (Z_{3^{10}}^{∗} , ·,^{−1} , 1), víme, že zobrazení ψ : Z_{2·3^{9}} → Z_{3^{10}}^{∗} dané předpisem ψ(k) = 2^{k} je izomorfismem grup (Z_{2·3^{9}} , +, −, 0) a (Z_{3^{10}}^{∗} , ·,^{−1} , 1). Rozhodujeme-li otázku, zda je 2^{k} generátorem multiplikativní grupy (Z_{3^{10}}^{∗} , ·,^{−1} , 1), stačí tedy abychom zjistili, zda je prvek k generátorem aditivní grupy (Z_{2·3^{9}} , +, −, 0), tedy zda je číslo k nesoudělné s číslem 2·3^{9}. To znamená, že 2^{15} ani 2^{16} generátorem nejsou, neboť NSD(15, 2 · 3^{9}) = 3 a NSD(16, 2 · 3^{9}) = 2, zatímco 2^{17} je generátorem, protože NSD(17, 2 · 3^{9}) = 1.

(d), (e) Předně vidíme, že NSD(13, 2 · 3^{9}) = 1 a NSD(3^{10} − 2, 2 · 3^{9}) = 1, proto 13, 3^{10} − 2 ∈ Z_{3^{10}}^{∗} . Protože 3^{10} − 2 = 1 + 3(3^{9} − 1) ∈ ⟨4⟩ a 13 = 1 + 3 · 4 ∈ ⟨4⟩, prvek 13 ani prvek 3^{10} − 2 negenerují grupu Z_{3^{10}}^{∗} . □

2.7. Spočítejte řády prvků 2^{15}, 2^{16} a 3^{10} − 2 grupy (Z_{3^{10}}^{∗} , ·,^{−1} , 1).

U čísel 2^{15}, 2^{16} stačí díky izomorfismu ψ určit řád prvku 15 a 16 v grupě (Z_{2·3^{9}} , +, −, 0), tedy |⟨2^{15}⟩| = \frac{2·3^{9}}{NSD (15,2·3^{9} )} = 2 · 3^{8}, a |⟨2^{16}⟩| = \frac{2·3^{9}}{NSD (16,2·3^{9} )} = 3^{9}.

Uvědomíme-li si, že (3^{10} − 2)^{2} = 4 v grupě (Z_{3^{10}}^{∗} , ·,^{−1} , 1) a že 3^{10} − 2 ∈ ⟨4⟩, vidíme, že ⟨3^{10} − 2⟩ = ⟨4⟩, tedy řád prvku 3^{10} − 2 je 3^{9}. □

2.8. Uvažujme v grupě (Z_{5^{8}}^{∗} , ·,^{−1} , 1) prvek a řádu 5^{7} a prvek b řádu 4 · 5^{β}, kde 0 ≤ β < 7. Dokažte, že a · b generuje Z_{5^{8}}^{∗}.

Z Lagrangeovy věty víme, že řád prvku a·b je 2^{α} ·5^{γ} pro nějaká α ∈ Z_{3} a γ ∈ Z_{8}. Nejprve nahlédneme, že (a · b)^{5^{7}} = a^{5^{7}} · b^{5^{7}} = b^{5^{7}} , tedy s využitím faktu, že zobrazení k → b^{k} indukuje izomorfismus cyklických grup (Z_{4·5^{β}} , +, −, 0) a (⟨b⟩, ·,^{−1} , 1), dostáváme, že b^{5^{7}} je prvek řádu 4. Protože ⟨b^{5^{7}} ⟩ ⊆ ⟨b⟩, dává nám Lagrangeova věta závěr, že 4/2^{α} · 5^{γ}, tedy α = 2. Obdobným argumentem pro grupu (⟨a · b⟩, ·,^{−1} , 1) dospějeme k pozorování, že (a · b)^{4} je prvek řádu 5^{γ}. Ukážeme, že γ = 7.

Předpokládejme, že γ < 7. Protože (a^{4} · b^{4})^{5^{β}} = a^{4·5^{β}} · b^{4·5^{β}} = a^{4·5^{β}} ≠ 1, musí γ > β, ovšem potom dostáváme, že 1 = (a^{4} · b^{4})^{5^{γ}} = a^{4·5^{γ}} · b^{4·5^{γ}} = a^{4·5^{γ}}, tudíž γ = 7. Nyní znovu využijeme Lagrangeovu větu, abychom zjistili, že řád prvku a · b je 4 · 5^{7}, tedy, že a · b generuje grupu Z_{5^{8}}^{∗}. □

2.9. Najděte generátor cyklické grupy (Z_{5^{8}}^{∗} , ·,^{−1} , 1).

Vyžijeme-li výsledek předchozí úlohy, stačí najít prvek řádu 5^{7} a prvek řádu 4·5^{β} pro β < 7.

Stejným postupem jako v úloze 2.4 (tj. v důsledku Tvrzení 2.10 ze skript) zjistíme, že 6 = 1 + 5 je prvek řádu 5^{7}. Protože 2^{2}, 2^{3} ∉ ⟨6⟩ = {1 + 5a| a ∈ Z_{5^{7}} } a 2^{4} ∈ ⟨6⟩, je rozkladová třída 2 · ⟨6⟩ generátorem čtyřprvkové faktorové grupy Z_{5^{8}}^{∗} /⟨6⟩, tedy opět díky Lagrangeově větě vidíme, že 4 dělí řád prvku 2 v grupě Z_{5^{8}}^{∗}. Nevíme ovšem, zda 2 je či není generátorem celé grupy Z_{5^{8}}^{∗}, zodpovězení této otázky odpovídá nalezení diskrétního logaritmu prvku 2^{4} o základu 6 (což je obecně obtížná úloha). Vezmeme-li ovšem prvek 2^{5}, obvyklým způsobem nahlédneme, že je řádu 4 · 5^{max (0,β−1)} , jakmile 4 · 5^{β} je řád prvku 2. Tedy podle pozorování 2.8 je prvek 2^{5} · 6 = 192 generátorem grupy Z_{5^{8}}^{∗}. □

2.10. Najděte v grupě (Z_{225}^{∗}, ·,^{−1} , 1) prvky řádu 2, 3 a 5.

Nejprve si uvědomme, že prvkem řádu 2, tedy involucí, je zřejmě 225 − 1 = 224. Podle Čínské věty o zbytcích je zobrazení f : Z_{225} → Z_{9} × Z_{25} dané předpisem

f(k) = (kmod 9, kmod 25) okruhový izomorfismus, proto indukuje izomorfismus mezi grupami invertibilních prvků f_{∗} : Z_{225}^{∗} → Z_{9}^{∗} × Z_{25}^{∗}. Tvrzení 2.10 ze skript, jehož důkazu jsme věnovali pozornost v úloze 2.4 nám dává prvek 4 řádu 3 v grupě Z_{9}^{∗} = Z_{3^{2}}^{∗} a prvek 6 řádu 5 v grupě Z_{25}^{∗} = Z_{5^{2}}^{∗}. Protože se v grupě Z_{9}^{∗} × Z_{25}^{∗} násobí po složkách, vidíme, že prvek (4, 1) je zde řádu 3 a prvek (1, 6) je řádu 5, tedy nám zbývá (obecně pomocí rozšířeného Eukleidova algoritmu, zde spíše zkusmo) najít prvky f_{∗}^{−1}((4, 1)) a f_{∗}^{−1}((1, 6)).

Tedy v prvním případě hledáme a ∈ Z_{225}, pro které

a ≡ 4(mod 9), a ≡ 1(mod 25).

Vyjádříme-li si z druhé kongruence a = 1 + 25 · b pro vhodné b ∈ Z_{9} a dosadíme do první kongruence, dostáváme

1 + 25 · b ≡ 4 (mod 9),
7 · b ≡ 3 (mod 9),
b ≡ 3 (mod 9).

Tedy a = 1 + 25 · 3 = 76 je prvek grupy (Z_{225}^{∗}, ·,^{−1} , 1) řádu 3.

Podobně v druhém případě hledáme a ∈ Z_{225}, pro něž

a ≡ 1(mod 9), a ≡ 6(mod 25).

Upravujme obdobně jako výše: a = 6 + 25 · b pro b ∈ Z_{9} a

6 + 25 · b ≡ 1 (mod 9),
7 · b ≡ 4 (mod 9),
b ≡ 7 (mod 9).

Spočítali jsme, že a = 1 + 25 · 7 = 176 je prvek řádu 5. □

31.3.

2.11. Určete pro každé přirozené k, kolik je v grupě (Z_{231}^{∗}, ·,^{−1} , 1) prvků řádu k.

Nejprve si rozmyslíme, pro která k v grupě (Z_{231}^{∗}, ·,^{−1} , 1) existuje nějaký prvek řádu k. Využijeme několikrát Čínskou větu o zbytcích. Nejprve spočítáme prvočíselný rozklad 231 = 3 · 7 · 11 a nahlédneme, že jsou izomorfní okruhy Z_{231} a Z_{3}×Z_{7}×Z_{11}, tedy jsou izomorfní i grupy invertibilních prvků Z_{231}^{∗} a Z_{3}^{∗}×Z_{7}^{∗}×Z_{11}^{∗}. Protože jsou grupy (Z_{p}^{∗}, ·,^{−1} , 1) pro všechna prvočísla p cyklické, dostáváme izomorfismus

(Z_{3}^{∗} × Z_{7}^{∗} × Z_{11}^{∗}, ·,^{−1} , (1, 1, 1)) ≅ (Z_{2} × Z_{6} × Z_{10}, +, −, (0, 0, 0))

a využijeme-li Čínskou větu o zbytcích pro aditivní grupy Z_{6} a Z_{10} máme

Z_{2} × Z_{6} × Z_{10} ≅ Z_{2} × (Z_{2} × Z_{3}) × (Z_{2} × Z_{5}) ≅ Z_{2}^{3} × Z_{3} × Z_{5}.

Protože je grupa (Z_{231}^{∗}, ·,^{−1} , 1) izomorfní grupě (Z_{2}^{3} ×Z_{3} ×Z_{5}, +, −, ((0, 0, 0), 0, 0)), můžeme otázku řádu prvků v multiplikativní grupě Z_{231}^{∗} zodpovědět v aditivní grupě Z_{2}^{3} × Z_{3} × Z_{5}. Označíme-li o(g) řád prvku g a zvolíme a ∈ Z_{2}^{3}, b ∈ Z_{3} a c ∈ Z_{5}, vidíme, že o((a, b, c)) = nsn(o(a), o(b), o(c)), přičemž v grupě Z_{2}^{3} nacházíme 1 prvek řádu 1 a 7 prvků řádu 2, v grupě Z_{3} máme 1 prvek řádu 1 a 2 prvky řádu 3 a konečně grupa Z_{5} obsahuje právě 1 prvek řádu 1 a 4 prvky řádu 5. To znamená, že grupa Z_{2}^{3} × Z_{3} × Z_{5}, a proto i grupa Z_{231}^{∗} obsahuje prvky řádu 2^{α}3^{β}5^{γ} pro α, β, γ ∈ {0, 1}.

Nyní už snando určíme počty prvků daného řádu:

k=1 V každé grupě máme zřejmě právě 1 prvek řádu 1.

k=2 Počítáme počet prvků množiny

{(a, b, c) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| nsn(o(a), o(b), o(c)) = 2} =
= {(a, b, c) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| o(a) = 2, o(b) = 1, o(c) = 1} =
= {(a, 0, 0) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| a ≠ (0, 0, 0)},

tedy máme 7 prvků řádu 2. k=3 Počítáme počet prvků množiny

{(a, b, c) ∈ Z_{2}^{3}×Z_{3}×Z_{5}| nsn(o(a), o(b), o(c)) = 3} = {(0, b, 0) ∈ Z_{2}^{3}×Z_{3}×Z_{5}| b ≠ 0},

tedy máme 2 prvky řádu 3. k=5 Tentokrát pracujeme s množinou

{(a, b, c) ∈ Z_{2}^{3}×Z_{3}×Z_{5}| nsn(o(a), o(b), o(c)) = 5} = {(0, 0, c) ∈ Z_{2}^{3}×Z_{3}×Z_{5}| c ≠ 0},

která obsahuje všechny 4 prvky řádu 5. k=6 Nyní spočítáme |{(a, b, c) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| nsn(o(a), o(b), o(c)) = 6}| =

= |{(a, b, 0) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| a ≠ (0, 0, 0), b ≠ 0}| = 14 prvků řádu 6. k=10 Počítáme

|{(a, 0, c) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| a ≠ (0, 0, 0), c ≠ 0}|,

tudíž máme 28 prvků řádu 10. k=15 Tentokrát dostáváme právě |{(0, b, c) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| b ≠ 0, c ≠ 0}| = 8

prvků řádu 15. k=30 Konečně |{(a, b, c) ∈ Z_{2}^{3} × Z_{3} × Z_{5}| a ≠ (0, 0, 0), b ≠ 0, c ≠ 0}| = 56 je počet

prvků řádu 30.

□

2.12. Najděte v grupě (Z_{231}^{∗}, ·,^{−1} , 1) tři involuce a jeden prvek řádu 30.

Označme f : Z_{231}^{∗} → Z_{3}^{∗} × Z_{7}^{∗} × Z_{11}^{∗} izomorfismus daný předpisem f(k) = ((k)mod 3, (k)mod 7, (k)mod 11) a postupujeme stejně jako v 2.10.

Nejprve snadno nahlédneme, že 230 = 231 − 1 je involuce. Všimněme si, že f(230) = (2, 6, 10). Nyní potřebujeme najít další prvky řádu 2 v grupě Z_{3}^{∗}×Z_{7}^{∗}×Z_{11}^{∗}, zvolíme například (2, 1, 1) a (2, 1, 10) a hledáme a, b ∈ Z_{231}^{∗}, aby f(a) = (2, 1, 1) a f(b) = (2, 1, 10), tedy řešíme kongruence:

a ≡ 2(mod 3), a ≡ 1(mod 7), a ≡ 1(mod 11),
b ≡ 2(mod 3), b ≡ 1(mod 7), b ≡ 10(mod 11),

Vyjádříme a = 2 + 3c_{1} a upravujme jako v 2.10:

2 + 3 · c_{1} ≡ 1 (mod 7),
3 · c_{1} ≡ 6 (mod 7),
c_{1} ≡ 2 (mod 7),

tedy a = 2 + 3 · 2 + 21c_{2} = 8 + 21c_{2} a stejným způsobem pokračujeme

8 + 21 · c_{2} ≡ 1 (mod 11),
10 · c_{2} ≡ 4 (mod 11),
c_{2} ≡ 7 (mod 11),

proto a = 8 + 21 · 7 = 155.

První krok druhého výpočtu proběhne stejně, tedy vyjádříme b = 8 + 21d a dosadíme

8 + 21 · d ≡ 10 (mod 11),
10 · d ≡ 2 (mod 11),
d ≡ 9 (mod 11),

tudíž b = 8 + 21 · 9 = 197.

Pro nalezení prvku řádu 30 v grupě (Z_{231}^{∗}, ·,^{−1} , 1) nejprve najdeme prvek řádu 10 v (Z_{11}^{∗}, ·,^{−1} , 1) a prvek řádu 3 v grupě (Z_{7}^{∗}, ·,^{−1} , 1). V prvním případě tedy hledáme generátor Z_{11}^{∗} jímž je například prvek 2, neboť 2^{2} ≢ 1 ≢ 2^{5}(mod 11). V druhé grupě snadno nahlédneme, že 4 je řádu 3, proto tentokrát počítáme soustavu kongruencí

x ≡ 1(mod 3), x ≡ 4(mod 7), x ≡ 2(mod 11),

kterou standardním postupem vyřešíme: položíme x = 2 + 11c_{1} a upravujme

2 + 11 · c_{1} ≡ 4 (mod 7),
4 · c_{1} ≡ 2 (mod 7),
c_{1} ≡ 4 (mod 7),
x = 46 + 77c_{2}
46 + 77 · c_{2} ≡ 1 (mod 3),
2 · c_{2} ≡ 0 (mod 3),
x = 46.

Zjistili jsme, že číslo 46 má v grupě (Z_{231}^{∗}, ·,^{−1} , 1) řád 30. □

2.13. Najděte v grupě (Z_{231}^{∗}, ·,^{−1} , 1) aspoň 3 prvky a, pro která a^{231−1} = 1. Kolik takových prvků existuje?

Hledáme tedy 3 Fermatovy lháře, přesněji řečeno 3 báze pseudoprvočísla 231, tj. čísla a ∈ Z_{231}^{∗}, pro něž a^{230} ≡ 1(mod 231). Vidíme, že tuto podmínku splňují právě ty prvky grupy (Z_{231}^{∗}, ·,^{−1} , 1), jejichž řád dělí číslo 231 − 1 = 230 = 2 · 5 · 23, tedy, jak jsme ukázali v úloze 2.11 právě prvky řádu 1,2, 5 a 10. Zřejmě tedy tuto podmínku splňuje prvek 1 a dále prvky 155 a 197, která jsou podle 2.12 řádu 2. Konečně poznamenejme, že prvků řádu 1,2, 5 a 10 je v grupě (Z_{231}^{∗}, ·,^{−1} , 1) celkem 40. □

7.4.

2.14. Uvažujme grupu (Z_{297}^{∗}, ·,^{−1} , 1).

(a) Spočítejte, kolik v grupě Z_{297}^{∗} existuje bází pseudoprvočísla 297 (tj. Fermatových lhářů),

(b) určete, kolik čísel a ∈ Z_{297} nesplní podmínku a^{296} ≡ 1 (mod 297) (tj. neprojdou Fermatovým testem),

(c) najděte všechny báze pseudoprvočísla 297,

(d) najděte všechny báze silného pseudoprvočísla 297 (tj. čísla, která neprojdou Rabinovým-Millerovým testem).

(a) Protože, 297 = 3^{3} · 11, opět si uvědomíme, že

Z_{297}^{∗} ≅ Z_{3^{3}}^{∗} × Z_{11}^{∗} ≅ Z_{18} × Z_{10} ≅ Z_{2}^{2} × Z_{9} × Z_{5}.

(zdůrazněme, že dvě grupy vlevo mají multiplikativní strukturu a dvě grupy vpravo mají aditvní strukturu). Zodpovíme tedy otázku v grupě Z_{2}^{2}×Z_{9}×Z_{5}, kde hledáme počet prvků, jejichž řád dělí číslo 296. Stejně jako v úloze 2.11 si tedy uvědomíme, že pro prvek (a, b, c, d) ∈ Z_{2} × Z_{2} × Z_{9} × Z_{5} platí x(a, b, c, d) = (xa, xb, xc, xd) = (0, 0, 0, 0), právě když nsn(o(a), o(b), o(c), o(d))/x. Protože chceme, aby zároveň x/296 = 2^{3}·37, hledáme tedy taková (a, b, c, d), aby y = nsn(o(a), o(b), o(c), o(d))/2^{3}· 37. Protože víme, že y = 2^{α} · 3^{β} · 5^{γ} pro vhodná α, γ ∈ Z_{2} a β ∈ Z_{3}, stačí nám uvažovat dělitele NSD(2^{1} · 3^{2} · 5^{1}, 2^{3} · 37) = 2. Vidíme, že stačí spočítat prvky exponentu 2 (tedy řádů, které dělí 2), jimiž jsou právě (a, b, 0, 0), kde s, b ∈ Z_{2}^{2}. Zjistili jsme, že máme právě čtyři Fermatovy lháře.

(b) Platí-li pro nějaké a ∈ Z_{297}, že a^{m} ≡ 1 (mod 297) pro nějaké kladné m, potom (a^{m−1})mod 297 je inverz k číslu a, a proto a ∈ Z_{297}^{∗}, To znamená, že pro číslo a soudělné s hodnotou 297 podmínka a^{296} ≡ 1 (mod 297) nemůže být splněna. Fermatovým testem tedy neprojdou pouze 4 hodnoty z grupy Z_{297}^{∗} spočítané v příkladu (a).

(c) Díky úvaze z (a) postupujeme stejně jako v příkladu 2.11. Nejprve snadno najdeme (jediné) prvky řádu 2 v grupách Z_{11}^{∗} a Z_{27}^{∗}, jimiž jsou zřejmě prvky opačné k jedničce, tedy −1 ≡ 10 (mod 11) a −1 ≡ 26 (mod 27). Dále bez počítání uvážíme, že jediným prvkem řádu 1 je v grupě Z_{297}^{∗} prvek 1 a zjevným prvkem řádu 2 je zde −1 ≡ 296 (mod 297) (přitom zjevně platí, že −1 ≡ 296 (mod 11) a −1 ≡ 296 (mod 27)). Tedy zbývá najít báze a, b ∈ Z_{297}^{∗} splňující

a ≡ −1(mod 11), a ≡ 1(mod 27), b ≡ 1(mod 11), b ≡ −1(mod 27).

Protože a ≡ −b(mod 297), stačí vyřešit pouze jednu z dvojic kongruencí. Obvyklým způsobem vyjádříme a = 1 + 27c a upravujme:

1 + 27c ≡ −1 (mod 11),
5c ≡ −2 (mod 11),
10c ≡ −4 (mod 11),
−c ≡ −4 (mod 11),
c ≡ 4 (mod 11),

proto a = 1+27·4 = 109 a b = 297−109 = 188. Našli jsme množinu {1, 109, 188, 296} všech Fermatových lhářů.

(d) Připomeňme, že pro N − 1 = 2^{e} · m, kde je m liché, je a ∈ Z_{N} bází silného pseudoprvočísla N, jestliže buď a^{m} ≡ 1 (mod N) nebo existuje nezáporné j < e, pro něž a^{2^{j}·m} ≡ −1 (mod N) (a zjišťování, zda platí tato podmínka se nazývá Rabinův-Millerův test prvočíselnosti čísla N v bázi a). Pro jakékoli liché N zjevně platí, že 1^{m} ≡ 1 (mod N) a (−1)^{m} ≡ −1 (mod N), tedy 1 a −1 jsou báze pseudoprvočísla N. Dále poznamenejme, že číslo, které projde Rabinovým-Millerovým testem nutně splni podmínku a^{N−1} ≡ 1 (mod N), tedy projde i Fermatovým testem.

Zbývá nám Rabinovým-Millerovým testem otestovat čísla 109 a 188 pro N − 1 = 296 = 2^{3} · 37. Protože můžeme využít Čínskou větu o zbytcích pro kanonický okruhový izomorfismus f : Z_{297}^{∗} → Z_{11}^{∗} × Z_{27}^{∗}, nebudeme samozřejmě opravdu počítat (109^{37})mod 297, protože

f(109^{37}) = f(109)^{37} = ((−1)^{37}, 1^{37}) = (−1, 1) = f(109),

tedy (109^{37})mod 297 = 109. Podobně (288^{37})mod 297 = 288. Dále

f(109^{2^{j}·37}) = f(109)^{2^{j}·37} = (2^{j} · 37, 1^{2^{j}·37}) = (−1^{2^{j}}, 1) = (1, 1) = f(1),

tedy (109^{2^{j}·37})mod 297 = 1 pro každé kladné j. Podobnou úvahu můžeme udělat i pro číslo 188. Vidíme, že báze 109 a 188 Rabinovým-Millerovým testem neprojdou. Jedinými bázemi silného pseudoprvočísla 297 jsou čísla 1 a 296. □

2.15. Rozhodněte, která z čísel 429, 561, 663, 1105 jsou Carmichaelova.

Máme za úkol pro dané liché N zjistit, zda pro všechna a ∈ Z_{N}^{∗} platí kongruence a^{N−1} ≡ 1 (mod N). Uvažujme prvočíselný rozklad N = ∏_{i} p_{i}^{r_{i}}. V úloze 2.14 jsme nahlédli, že potřebujeme zjistit, zda řády všech prvků grupy Z_{N}^{∗} ≅ ∏_{i=1}^{s} Z_{p_{i}^{r_{i}}}^{∗}, kde

Z_{p_{i}^{r_{i}}}^{∗} jsou cyklické grupy řádu (p_{i} − 1)p_{i}^{r_{i}−1}, dělí číslo N − 1. Tedy díky cykličnosti grup Z_{p_{i}^{r_{i}}}^{∗} budeme zjišťovat, zda

nsn((p_{1} − 1)p_{1}^{r_{1} −1}, …, (p_{s} − 1)p_{s}^{r_{s}−1})/N − 1.

Uvažejme nyní jednotlivé případy: (N=429) Spočítáme-li prvočíselný rozklad 429 = 3 · 11 · 13 a nsn(2, 10, 12) = 60,

snadno nahlédneme, že 60 nedělí číslo 428, tedy existuje prvek grupy Z_{429}^{∗}, který není bází pseudoprvočísla 429, proto číslo 429 není Carmichaelovo. Konkrétně si uvědomme, že umíme najít například prvek a ∈ Z_{429}^{∗} řádu 5, pro který tudíž platí, že a^{428} ≡ a^{425} · a^{3} ≡ a^{3} ≢ 1 (mod 429).

(N=561) Opět spočítáme prvočíselný rozklad 561 = 3 · 11 · 17 a nsn(2, 10, 16) = 80. Nyní vidíme, že 80/560, proto jsou všechny prvky grupy Z_{561}^{∗} báze pseudoprvočísla 561 a číslo 561 je Carmichaelovo.

(N=663) Protože 663 = 3 · 13 · 17 a nsn(2, 12, 16) = 48 nedělí číslo 662, číslo 663 není

Carmichaelovo.

(N=1105) Tentokrát 1105 = 5 · 13 · 17 a nsn(4, 12, 16) = 48 dělí číslo 1104, číslo 1105

tudíž je Carmichaelovo.

□

14.4.

2.16. Spočítejte kolik existuje bází silného pseudoprvočísla 561.

Víme, že 560 = 2^{4} · 35 a 561 = 3 · 11 · 17. Obvyklým způsobem přeložíme otázku počtu čísel a ∈ Z_{561}^{∗} splňujících buď a^{35} ≡ 1 (mod 561) nebo a^{2^{j}·35} ≡ −1 (mod 561) pro nějaké nezáporné j < 4 do aditivní grupy Z_{2} ×Z_{2} ×Z_{5} ×Z_{16}, která je izomorfní multiplikativní grupě Z_{561}^{∗} ≅ Z_{3}^{∗} × Z_{11}^{∗} × Z_{17}^{∗}.

Nejprve uvážíme, že involuci −1 grupy Z_{561}^{∗} odpovídá při kanonickém izomorfismu Čínské věty o zbytcích prvek (−1, −1, −1) grupy Z_{3}^{∗} × Z_{11}^{∗} × Z_{17}^{∗}. Protože je každá z grup Z_{3}^{∗}, Z_{11}^{∗} a Z_{17}^{∗} cyklická, obsahuje jedinou involuci, tedy jsou tyto multiplikativní grupy izomorfní aditivním grupám po řadě Z_{2}, Z_{2} × Z_{5} a Z_{16} s involucemi 1, (1, 0) a 8. Proto involuci −1 z grupy Z_{561}^{∗} odpovídá v grupě Z_{2}×Z_{2}×Z_{5}×Z_{16} prvek (1, 1, 0, 8).

Nyní hledáme a = (a_{1}, a_{2}, a_{3}, a_{4}) ∈ Z_{2} × Z_{2} × Z_{5} × Z_{16}, pro která platí

35 · a = (35a_{1}, 35a_{2}, 35a_{3}, 35a_{4}) = (a_{1}, a_{2}, 0, 3a_{4}) = (0, 0, 0, 0)

nebo pro nějaké nezáporné j < 4

35 · 2^{j} · a = (2^{j}a_{1}, 2^{j}a_{2}, 0, 3 · 2^{j}a_{4}) = (1, 1, 0, 8).

Poznamenejme, že 2^{j}a_{1} = 1 může nastat pouze pro j = 0, proto druhá podmínka platí pro j = 0, a_{1} = a_{2} = 1, a_{4} = 8 a a_{3} libovolné ze Z_{5}, tedy pro pět různých a. Podobně první podmínka je spolňena pro a_{1} = a_{2} = a_{4} = 0 a a_{3} ∈ Z_{5}, tedy i v tomto případě nacházíme 5 bází. Zjistili jsme, že existuje celkem 10 bází silného pseudoprvočísla 561. □

Závěrem poznamenejme, že je číslo 561 Carmichaelovo, tedy existuje φ(561) = 320 bází pseudoprvočísla 561, což znamená, že zatímco při Fermatově testu pro náhodně zvolené číslo a ∈ Z_{561} \ \{0\} máme pravděpodobnost \frac{320}{560} = \frac{4}{7}, že neodhalíme, že se nejedná o prvočíslo, v případě Rabinova-Millerova testu bude pravděpodobnost neodhalení neprvočíselnosti pouze \frac{10}{560} = \frac{1}{56} .

Další úlohy

(1) Rozhodněte, zda je okruh Z[i\sqrt{3}] Gaussův.

(2) Kolik prostých homomorfismů leží v množině Hom(Z_{7^{10}} , Z_{7^{20}} )?

(3) Kolik homomorfismů na obsahuje množina Hom(Z_{999}, Z_{333})?

(4) Určete řád prvku 4^{i} v grupě (Z_{3^{10}}^{∗} , ·,^{−1} , 1) pro každé celé i.

(5) Najdtěte v grupě (Z_{7^{3}}^{∗} , ·,^{−1} , 1) všechny prvky řádu 2,3 a 7.

(6) Najděte generátor cyklické grupy (Z_{7^{777}}^{∗} , ·,^{−1} , 1).

(7) Najděte v grupě (Z_{1323}^{∗} , ·,^{−1} , 1) všechny prvky řádu 2, 3, 4, 6, 7 a 9.

(8) Najděte v grupě (Z_{1000}^{∗} , ·,^{−1} , 1) všechny involuce.

(9) Najděte najmenší přirozené s, aby a^{s} ≡ 1(mod 999) pro všechna a ∈ Z_{999}^{∗}.

(10) Najděte v grupě (Z_{1000}^{∗} , ·,^{−1} , 1) aspoň 3 prvky a, pro která a^{999} = 1. Kolik takových prvků existuje?

(11) Spočítejte, kolik existuje bází pseudoprvočísla 2465 a najděte nějakou bázi nejvyššího možného řádu.

(12) Rozhodněte, která z čísel 1547 1547, 1729, 2717, 3003 jsou Carmichaelova.

(13) U každého z čísel z předchozí úlohy najděte číslo, které je s ním nesoudělné a není jeho bazí jako silného pseudoprvočísla.