21.4.

3. Gaussova celá čísla

3.1. Uvažujme čísla 3, 5, 19, 101, 103, 149 a 157.

(a) Která z nich jsou prvočinitelé oboru Z[i]?

(b) Čísla, pro něž je to možné, napište jako součet čtverců.

(c) Ta čísla, kerá nejsou prvočinitely rozložte v oboru Z[i] na součin prvočinitelů.

□

Všimněme si, že všechna uvedená čísla jsou lichá prvočísla.

(a) Podle věty z přednášky stačí zjistit, zda je zbytek po dělení daného prvočísla čtyřkou roven jedné či třem. Zřejmě

3 ≡ 3, 5 ≡ 1, 19 ≡ 3, 101 ≡ 1, 103 ≡ 3, 149 ≡ 1, 157 ≡ 1 (mod 4).

Proto jsou prvočinitelem v oboru Z[i] právě čísla 3, 19 a 103.

(b) Připomenutá věta z přednášky, říká, že součtem čtverců jsou právě prvočísla, která jsou rozložitelná nad Z[i]. Snadno zkusmo spočítáme, že

5 = 1^{2} + 2^{2}, 101 = 1^{2} + 10^{2}, 149 = 7^{2} + 10^{2}, 157 = 6^{2} + 11^{2}.

(c) Z přednášky opět víme, že prvočinitelé Z[i] jsou právě ta prvočísla, která nejsou součet čtverců, a jakmile p = a^{2} + b^{2} = (a + bi)(a − bi) pro nějaké prvočíslo p, pak jsou Gausova čísla (a + bi) a (a − bi) zřejmě prvočinitelé (jejich norma je totiž prvočíselná). Přímo z (b) tedy dostáváme rozklady na prvočinitele:

5 = (1 + 2i)(1 − 2i), 101 = (1 + 10i)(1 − 10i),
149 = (7 + 10i)(7 − 10i), 157 = (6 + 11i)(6 − 11i).
□

3.2. Najděte v grupách Z_{5}^{∗} Z_{101}^{∗}, Z_{149}^{∗} a Z_{157}^{∗} všechny druhé odmocniny z −1.

Pro každé z prvočísel p hledáme prvky a ∈ Z_{p}^{∗}, pro něž a^{2} ≡ −1(mod p), tedy p/a^{2} + 1. To znamená, že potřebujeme najít kořeny polynomu x^{2} + 1 v tělese Z_{p}. Všimněme si, že −1 je v grupě Z_{p}^{∗} (jediný) prvek řádu 2 a hledáme prvky Z_{4}^{∗} řádu 4. Protože 4 dělí 5 − 1, 101 − 1, 149 − 1 i 157 − 1, druhé odmocniny z −1 existují a jsou právě 2.

Už jsme našli rozklady 5 = 1^{2}+2^{2} = 1^{2}+(−2)^{2} = 1^{2}+3^{2} v Z_{5} a 101 = 1^{2}+10^{2} = 1^{2} + (−10)^{2} = 1^{2} + 91^{2} v Z_{101}, proto okamžitě dostáváme 2 a 3 druhé odmocniny z −1 v grup v grupě Z_{5}^{∗} a 10 a 91 druhé odmocniny z −1 v grup v grupě Z_{101}^{∗}.

Nyní předpkládejme, že a^{2} ≡ −1(mod 149), tedy 149/a^{2} +1 v oboru celých čísel, proto 149/a^{2} +1 v oboru Z[i]. V úloze (b) jsme zjistili, že 149 = (7+10i)(7−10i) je rozklad na prvočinitele, tedy například (7 + 10i) dělí a^{2} + 1 = (a + i)(a − i) v oboru Z[i]. Podle definice prvočinitele víme, že buď (7+10i)/(a+i) nebo (7+10i)/(a−i). Předpokládáme-li například, že (7 + 10i)/(a + i), víme, že existuje (x + yi) ∈ Z[i], pro které (7 + 10i) · (x + yi) = (7x − 10y) + (10x + 7y)i = a + i, a proto

7x − 10y = a, 10x + 7y = 1.

Snadno najdeme řešení (x, y) = (5, −7) druhé rovnice (poznamenejme, že jde právě o Bezoutovy koeficienty nutně nesoudělných hodnot 7 a 10), díky němuž spočítáme a = 7 · 5 + 10 · 7 = 105. Zbylou odmocninu nemusíme hledat pomocí úvahy (7 − 10i)/(a+i), stačí vzít v tělese Z_{149} prvek opačný k nalezenému, tedy 149−105 = 44. Čísla 44 a 105 jsou obě druhé odmocniny z −1 v grupě Z_{149}^{∗}.

Analogicky budeme postupovat i v grupě Z_{157}^{∗}. Opět uvážíme, že hledáme a ∈ Z_{157}^{∗}, aby v oboru Z[i]

(6 + 11i)(6 − 11i) = 157/a^{2} + 1 = (a + i)(a − i),

cože vede na rovnice

6x − 11y = a, 11x + 6y = 1.

Snadno najdeme (x, y) = (5, −9) splňující druhou rovnici, proto a = 6 · 5 + 11 · 9 = 129. Tedy Čísla 129 a 157 − 129 = 28 jsou obě druhé odmocniny z −1 v grupě Z_{157}^{∗}. □

3.3. Uvažujme grupu Z_{317}^{∗}.

(a) Rozhodněte, pro která m existuje a_{m} ∈ Z_{317}^{∗}, pro něž a_{m}^{2} = 2^{m}.

(b) Ověřte, že je prvek 2^{79} prvek řádu 4.

(c) Najděte všechny prvky řádu 4.

Předně si všimněme, že 317 je prvočíslo a 317 − 1 = 4 · 79, kde 79 je prvočíslo. Grupa Z_{317}^{∗} je proto cyklická řádu 316 a obsahuje právě dva prvky řádu 4.

(a) Na přednášce bylo dokázáno pro každé prvočíslo p, že 2 = a^{2} v grupě Z_{p}^{∗}, právě když p ≡ ±1mod 8. Protože 317 ≡ 5mod 8, vidíme, že 2 není čtvercem. Uvědomme si, že množina D = {a^{2}| a ∈ Z_{317}^{∗}} je podgrupa grupy Z_{317}^{∗} indexu 2 (v izomorfní cyklické grupě Z_{316} s aditivním zápisem odpovídá právě podgrupě násobků dvojky, tedy podgrupě 2Z_{316} = ⟨2⟩), proto 2^{m} ∈ D, právě když je m liché.

(b) Protože (2^{79})^{4} = 2^{316} = 1 podle Lagrangeovy věty, musí mít prvek 2^{79} exponent 4, tedy je řádu 1,2 nebo 4. Ovšem prvek řádu 1 i prvek řádu 2 je v cyklické grupě jediný (1, resp. 316) a protože Z_{317}^{∗} obsahuje pogrupu řádu 4, musí být oba čtvercem (1 = 316^{2} a 316 je čtvercem odmocniny z −1, tedy právě kteréhokoli prvku řádu 4). Díky (a) je tedy 2^{79} nutně řádu 4.

(c) Stačí abychom vyčíslili 2^{79} v grupě Z_{317}^{∗}, což lze snadno provést i ručně:

2^{10} = 1024 ≡ 73, 2^{20} ≡ 73^{2} ≡ −60, 2^{18} ≡ −15, (mod 317)

2^{38} ≡ 4 · 15^{2} ≡ −51, 2^{79} ≡ 8 · 51^{2} ≡ 8 · 65 ≡ 203 (mod 317)

Zjistili jsme, že 203^{2} ≡ (−203)^{2} ≡ −1(mod 317), tedy 203 a 317 − 203 = 114 jsou oba prvky řádu 4 grupy Z_{317}^{∗}. □

28.4.

3.4. Najděte přirozená čísla a, b, aby 317 = a^{2} + b^{2}.

V předchozí úloze jsme zjistili, že 114^{2}+1 ≡ 0(mod 317), tedy, že 317/114^{2}+1 = (114 + i)(114 − i) v oboru Z[i]. O hledaných hodnotách a, b ovšem víme, že 317 = a^{2} +b^{2} = (a+bi)(a−bi) a že a+bi i a−bi jsou prvočinitelé oboru Z[i], proto nutně buď a + bi/114 + i nebo a + bi/114 − i, budeme-li hledat celá a, b, můžeme si vybrat například podmínku a+bi/114+i. Zjistili jsme, že hledaný prvočinitel je společným dělitelem čísel 317 a 114 + i, tudíž stačí abychom Eukleidovým algoritmem našli největší společný dělitel těchto dvou Gaussových celých čísel:

0. z_{0} = 317.

1. z_{1} = 114 + i.

2. Určíme nejprve komplexní c_{1} = \frac{317}{114+i} = \frac{317·(114−i)}{114^{2} +1} = \frac{317·(114)}{114^{2} +1} − i\frac{317}{114^{2} +1} , a okamžitě vidíme, že 3 je nejbližší celé číslo k číslu \frac{317·(114)}{114^{2} +1} a 0 je nejbližší celé číslo k \frac{317}{114^{2} +1} . Nyní dostaneme z_{2} = 317 − 3 · (114 + i) = −25 − 3i.

3. Abychom určili podíl při dělení se zbytkem, opět spočítáme c_{2} = \frac{114+i}{−25−3i} = \frac{(114+i)·(−25+3i)}{25^{2} +3^{2}} = \frac{−114·(25)−3}{634} − i\frac{114·3−25}{634} = −\frac{5}{2} + i\frac{1}{2}, a zbývá najít zbytek z_{3} = 114 + i + 4 · (−25 − 3i) = 14 − 11i.

4. Snadnu už nahlédneme, že 14 − 11i/ − 25 − 3i, tedy 14 − 11i je hledaný největší společný dělitel.

Zjistili jsme, že 317 = (14 − 11i)(14 + 11i) = 14^{2} + 11^{2}.

Závěrem poznamenejme, že kdybychom spočítali 114^{2} + 1 = 317 · 41 a uvědomili si, že 41 = 4^{2} + 5^{2} = (4 − 5i)(4 + 5i), stačilo by nám pro nalezení ireducibilního rozkladu čísla 317 v oboru Z[i] spočítat buď podíl \frac{114+i}{4−5i} nebo \frac{114+i}{4+5i} . Vidíme, že zatímco \frac{114+i}{4−5i} ∉ Z[i], dostáváme \frac{114+i}{4−5i} = 11 + 14i∥14 − 11i. □

4. Charaktery a kvadratické zbytky

Připomeňme, že charakterem komutativní grupy rozumíme každý její homomorfismus do grupy (C^{∗}, ·,^{−1} , 1). Je-li χ charakter komutativní grupy A jehož obraz χ(A) je konečný, potom zřejmě |χ(a)| = 1 pro všechna a ∈ A.

4.1. Najděte všechny charaktery

(a) aditivní grupy Z_{2},

(b) aditivní grupy Z_{3},

(c) aditivní grupy Z_{n} pro každé přirozené n,

(d) aditivní grupy Z_{2} × Z_{2},

(e) multiplikativní grupy Z_{5}^{∗},

(a) Jistě χ(0) = 1 pro každý charakter χ, tedy zbývá rozhodnout kam se zobarazí prvek 1 grupy Z_{2}. Protože je χ(1)·χ(1) = χ(1+1) = χ(0) = 1 musí být χ(1) kořenem polynomu x^{2}−1. Zřejmě tedy máme právě dva charaktery, první konstatntní χ_{0} ≡ 1 a druhý daný podmínkou χ_{1}(1) = −1.

(b) Uvážíme-li, že je Z_{3} cyklická grupa řádu 3, stačí nám najít obraz generátoru v grupě C^{∗}, který bude exponentu 3. Prvky exponentu 3 jsou právě všechny kořeny polynomu x^{3} − 1, tedy čísla 1, −\frac{1}{2} + \frac{\sqrt{3}}{2}i a −\frac{1}{2} − \frac{\sqrt{3}}{2}i, proto najdeme právě tři charaktery: konstantní χ_{0} ≡ 1 a dva nekonstatntní χ_{1} a χ_{2} dané podmínkou χ_{1}(1) = −\frac{1}{2} + \frac{\sqrt{3}}{2}i a χ_{2}(1) = −\frac{1}{2} − \frac{\sqrt{3}}{2}i, pro pořádek uveďme jejich hodnoty na celém definičním oboru:

χ_{1}(0) = 1, χ_{1}(1) = −\frac{1}{2} + \frac{\sqrt{3}}{2}i, χ_{1}(2) = −\frac{1}{2} − \frac{\sqrt{3}}{2}i,

χ_{2}(0) = 1, χ_{2}(1) = −\frac{1}{2} − \frac{\sqrt{3}}{2}i, χ_{2}(2) = −\frac{1}{2} + \frac{\sqrt{3}}{2}i,

(c) Podobně jako v úloze (b) stačí uvážit, že je charakter χ určen obrazem generátoru grupy Z_{n} a že χ(Z_{n}) leží v množině všech kořenů polynomu x^{n} − 1.

Uvážíme-li, že kořeny polynomu x^{n} − 1 tvoří cyklickou grupu

⟨e^{\frac{2π}{n} i}⟩ = \{1, e^{2 \frac{2π}{n} i}, e^{3 \frac{2π}{n} i}, …, e^{(n−1) \frac{2π}{n} i}\},

kde e^{k \frac{2π}{n} i} = cos(k \frac{2π}{n}) + i sin(k \frac{2π}{n}), máme pro každé j ∈ Z_{n} charakter χ_{j} daný vztahem χ_{j}(1) = e^{j \frac{2π}{n} i}. Tedy existuje právě n různých charakterů a determinuje je předpis χ_{j}(k) = e^{jk \frac{2π}{n} i}.

(d) Uvažujme charakter χ grupy Z_{2} × Z_{2}. V příkladu (a) jsme popsali homomorfismy Z_{2} do C^{∗}. Protože jsou inkluze ν_{1} a ν_{2} grupy Z_{2} do grupy Z_{2} × Z_{2} dané předpisem ν_{1}(a) = (a, 0) a ν_{1}(a) = (0, a) zřejmě homomorfismy, zobrazení χν_{1} a χν_{2} jsou charaktery grupy Z_{2}. Protože χ((1, 1)) = χ((1, 0)+(0, 1)) = χ((1, 0))·χ((0, 1)), určují obrazy prvků (1, 0) a (0, 1) právě jeden homomorfismus. Tedy máme právě 4 charaktery grupy Z_{2} × Z_{2}; konstantu χ_{++} ≡ 1 a dále

χ_{−+} ((0, 0)) = 1, χ_{−+} ((1, 0)) = −1, χ_{−+} ((0, 1)) = 1, χ_{−+} ((1, 1)) = −1,

χ_{+−} ((0, 0)) = 1, χ_{+−} ((1, 0)) = 1, χ_{+−} ((0, 1)) = −1, χ_{+−} ((1, 1)) = −1,

χ_{−−}((0, 0)) = 1, χ_{−−}((1, 0)) = −1, χ_{−−}((0, 1)) = −1, χ_{−−}((1, 1)) = 1.

(e) Protože je Z_{5}^{∗} cyklická grupa řádu 4, stačí nám najít její generátor a využít příkladu (c) (tentokrát ovšem pracujeme s cyklickou grupou v multiplikativním zápisu). Generátorem je například prvek 2, proto podle (c) existují právě 4 charaktery Z_{5}^{∗} dané předpisem χ_{j}(2^{k}) = e^{jk \frac{π}{2}i} = i^{jk} pro j ∈ Z_{4}. Opět můžeme snadno všechny charaktery po prvcích popsat:

χ_{0}(1) = χ_{0}(2) = χ_{0}(3) = χ_{0}(4) = 1,
χ_{1}(1) = 1, χ_{1}(2) = i, χ_{1}(3) = −i, χ_{1}(4) = −1,
χ_{2}(1) = χ_{2}(4) = 1, χ_{2}(2) = χ_{2}(3) = −1,
χ_{3}(1) = 1, χ_{3}(2) = −i, χ_{3}(3) = i, χ_{3}(4) = −1,
□

Protože charaktery konečné komutativní grupy můžeme po složkách násobit, dále konstanta 1 je jistě charakter a pro charakter \overline{χ} komplexně sdružený k charakteru χ platí χ · \overline{χ} ≡ 1, máme na množině charakterů strukturu (multiplikativní) komutativní grupy.

4.2. Ověřte, že je grupa charakterů grupy Z_{11}^{∗} cyklická a najděte všechny její generátory.

Na přednášce bylo dokázáno, že je grupa charakterů grupy A izomorfní grupě A. Protože je grupa Z_{11}^{∗} cyklická řádu 10, je i grupa charakterů cyklická řádu 10 a musíme najít právě 4 její generátory. Navíc si uvědomme, že pro každý charakter χ je obraz χ(Z_{11}^{∗}) podgrupou desetiprvkové cyklické podgrupy ⟨e^{\frac{π}{5}i}⟩ grupy C^{∗}. Protože generátory grupy charakterů musí být prosté homomorfismy a prosté homomorfimsy grupy Z_{11}^{∗} do grupy ⟨e^{\frac{π}{5}i}⟩ jsou právě čtyři (obě grupy jsou totiž cyklické řádu 10), potřebujeme najít právě izomorfismy grupy Z_{11}^{∗} do grupy ⟨e^{\frac{π}{5}i}⟩. Homomorfismus cyklické grupy je ovšem určen obrazem generátoru a o izomorfismus půjde právě tehdy, když se generátor definičníáho oboru zobrazí na generátor oboru hodnot (tj. cyklické grupy stejného řádu).

Nyní zbývá nahlédnout, že například prvek 2 je generátorem grupy Z_{11}^{∗}, neboť 2^{5} ≡ −1 (mod 11), a že generátory grupy ⟨e^{\frac{π}{5}i}⟩ jsou právě prvky e^{k \frac{π}{5}i} pro k nesoudělné s číslem 10 pomocí popisu 4.1(c) a analogicky k úvaze 4.1(e) jsou hledanými generátory charaktery

χ_{1}(2^{k}) = e^{k \frac{π}{5}i}, χ_{3}(2^{k}) = e^{3k \frac{π}{5}i}, χ_{7}(2^{k}) = e^{7k \frac{π}{5}i}, χ_{9}(2^{k}) = e^{9k \frac{π}{5}i}.

Všimněme si, že χ_{9} = \overline{χ_{1}} = χ_{1}^{−1} a χ_{7} = \overline{χ_{3}} = χ_{3}^{−1} Z popisu 4.1(c) vidíme, že každý z charakterů je mocninou (například) charakteru χ_{1}, tedy na to, abychom ověřili, že je grupa charakterů cyklická jsme nemuseli používat větu z přednášky. □

5.5.

4.3. Popište konečné grupy, pro něž existuje prostý charakter.

Vezměme grupu (G, ·,^{−1} , 1) řádu n a nějaký její charakter χ. Podle Lagrangeovy věty g^{n} = 1, proto i χ(g)^{n} = χ(g^{n}) = 1 pro každý g ∈ G, tedy všechny prvky grupy χ(G) jsou kořeny polynomu x^{n} − 1 nad tělesem komplexních čísel. To znamená, že χ(G) je podgrupa grupy ⟨e^{\frac{2π}{n} i}⟩ ⊆ C^{∗}. Protože je grupa ⟨e^{\frac{2π}{n} i}⟩ cyklická, je cyklická i její podgrupa χ(G). Předpokládáme-li, že je χ prosté, potom musí jít izomorfismus grup G a χ(G) = ⟨e^{\frac{2π}{n} i}⟩, tudíž je nutně cyklická grupa G. Vidíme, že prostý charakter existuje právě pro cyklické konečné grupy. □

4.4. Dokažte pro konečnou cyklickou grupu (G, ·,^{−1} , 1) a nějaký její charakter χ ekvivalenci následujících tvrzení:

(1) χ je prosté,

(2) χ^{j} ≢ 1 pro žádné j = 1, …, |G| − 1,

(3) χ generuje grupu charakterů grupy (G, ·,^{−1} , 1),

(4) je-li g generátor G, pak existuje k nesoudělné s |G|, pro které χ(g) = e^{\frac{2kπ}{n} i}

(1)⇔(4) χ je prosté právě když zobrazí generátor grupy G na generátor grupy ⟨e^{\frac{2π}{n} i}⟩, je ovšem snadné nahlédnout, že generétory gruipy ⟨e^{\frac{2π}{n} i}⟩ jsou právě prvky e^{\frac{2kπ}{n} i} pro k nesoudělné s |G|.

(2)⇔(3) je zřejmé.

(4)⇒(2) Jesliže NSD(k, |G|) = 1, potom χ(g)^{j} = e^{\frac{2jkπ}{n} i} ≠ 1 pro všechna j = 1, …, |G| − 1, protože χ(g) generuje grupu χ(G) řádu |G|.

(2)⇒(1) Kdyby χ nebylo prosté, žádné χ^{j} by nebylo prosté, ačkoli prostý charakter podle předchozí úlohy existuje, proto ⟨χ⟩ není celá grupa charakterů. □

4.5. Popište všechny charaktery χ grupy Z_{n}^{∗} splňující podmínku χ^{2} ≡ 1, jestliže (a) n = 31,

(b) n = 65

Předně si uvědomme, že hledáme prvky grupy charakterů exponentu 2. Jedním takovým charakterem je konstantní jednička, zbývá tedy najít všechny involuce grupy charakterů. Všimněme si, že pro každou involuci χ grupy charakterů platí, že χ(Z_{n}^{∗}) = {−1, 1}.

Připomeňme navíc, že grupa charakterů je izomorfní původní grupě, tedy obvyklým způsobem snadno nahlédneme kolik involucí je třeba najít.

(a) Protože je Z_{31}^{∗} cyklická, a proto obsahuje jedinou involuci, zbývá nám najít jediný charakter. Zjistíme-li, že například 3 je generátorem grupy Z_{31}^{∗}, pak hledaný charakter určuje podmínka χ(3) = −1, proto χ(3^{j}) = (−1)^{j}. Kromě toho jsme si mohli uvědomit, že jedinou involuci grupy Z_{31}^{∗} máme z přednášky označenu Legendrovým symbolem, tj χ(a) = (\frac{a}{31} ), což říká, že χ(a) = 1 právě tehdy, když je a kvadratickým zbytkem modulo 31.

(b) Protože Z_{65}^{∗} ≅ Z_{5}^{∗} × Z_{13}^{∗} ≅ Z_{4} × Z_{3} × Z_{4}×, vidíme, že budeme hledat právě 3 involuce. Uvažujme-li χ_{5} nějaký charakter grupy Z_{5}^{∗} a χ_{13} nějaký charakter grupy Z_{13}^{∗}, pak je zobrazení χ dané předpisem χ((a, b)) = χ_{5}(a) · χ_{13}(b) charakter grupy Z_{5}^{∗} × Z_{13}^{∗}.

Připomeňme, že Legendrův symbol určuje jedinou involuci (\frac{−}{5}) na grupě Z_{5}^{∗} a podobně (\frac{−}{13} ) je jediná involuce na grupě Z_{13}^{∗}. Protože Čínská věta o zbytcích indukuje homomorfismus multiplikativních grup dostaneme hledané charaktery jako složení:

χ_{10}(k) = (\frac{kmod 5}{5}) = (\frac{k}{5}) , χ_{01}(k) = (\frac{kmod 13}{13}) = (\frac{k}{13}) ,

χ_{11}(k) = (\frac{kmod 5}{5}) (\frac{kmod 13}{13}) = (\frac{k}{5}) (\frac{k}{13}) = (\frac{k}{65}) .

V posledním řádku jsme použili Jacobiho symbol. □

4.6. Rozhodněte, zda jsou kvadratickým zbytkem (a) prvky 5 a 7 grupy Z_{13}^{∗},

(b) prvky 9, 27 a 32 grupy Z_{47}^{∗},

(c) prvky 55, 111 a 112 grupy Z_{137}^{∗}.

Budeme využívat Větu o reciprocitě a (výše užívaná) tvrzení o tom, zda jsou prvky −1 a 2 kvadratické zbytky:

(a) Počítáme:

(\frac{5}{13}) = (\frac{13}{5}) (−1)^{\frac{13−1}{2} · \frac{5−1}{2}} = (\frac{3}{5}) = (\frac{−1}{5}) (\frac{2}{5}) = 1 · (−1) = −1,

(\frac{7}{13}) = (\frac{13}{7}) (−1)^{\frac{13−1}{2} · \frac{7−1}{2}} = (\frac{−1}{7}) − 1.

Tedy ani 5 ani 7 nejsou modulo 13 kvadratické zbytky.

(b) Protože 9 = 3^{2} je určitě 9 kvadratický zbytek modulo 47, dál počítáme jako v (a):

(\frac{27}{47}) = (\frac{3}{47}) (\frac{9}{47}) = (\frac{3}{47}) = (−1)^{\frac{3−1}{2} · \frac{47−1}{2}} (\frac{−1}{3}) = (−1) · (−1) = 1,

(\frac{32}{47}) = (\frac{2}{47})^{5} = (\frac{2}{47}) = 1.

Zjistili jsme, že všechny hodnoty 9, 27 a 32 jsou kvadratické zbytky modulo 47 (c) Opět pracujeme s Lagendrovými symboly:

(\frac{55}{137}) = (\frac{5}{137}) (\frac{11}{137}) = (\frac{2}{5}) (\frac{5}{11}) = (−1) (\frac{1}{5}) = −1,

(\frac{111}{137}) = (\frac{−26}{137}) = (\frac{−1}{137}) (\frac{2}{137}) (\frac{13}{137}) = 1 · 1 · (\frac{13}{137}) = (\frac{5}{13}) = −1,

(\frac{112}{137}) = (\frac{−25}{137}) = (\frac{−1}{137}) (\frac{5}{137})^{2} = 1 · 1 = 1.

Tentokrát jsme zjistili, že 55 a 111 nejsou kvadratické zbytky modulo 134, zatímco 112 je kvadratický zbytek modulo 134. □

12.5.

4.7. Rozhodněte, zda jsou kvadratickým zbytkem čísla 4301 a 7367 modulo prvočíslo 24851.

Budeme tentokrát pracovat s Jacobiho symboly, s kterými díky dokázanému lemmatu můžeme pracovat stejně jako s Lagendrovými symboly, ovšem nemusíme pro použití Věty o reciprocitě lichá čísla rozkládat na prvočíselný rozklad. Pro zpřehlednění zápisu využijme zřejmého faktu, že a ≡ 1(mod 4), právě když (a)mod 100 ≡ 1(mod 4), tudíž v exponentech zjišťujících sudost čísla \frac{n−1}{2} budeme psát jen poslední dvě cifry čísla n − 1.

(\frac{4301}{24851}) = (−1)^{\frac{1−1}{2} · \frac{51−1}{2}} (\frac{24851}{4301}) = (\frac{3346}{4301}) = (\frac{−1}{4301}) · (\frac{955}{4301}) =

= (−1)^{\frac{1−1}{2}} (−1)^{\frac{1−1}{2} · \frac{55−1}{2}} (\frac{481}{955}) = (−1)^{\frac{81−1}{2} · \frac{55−1}{2}} (\frac{955}{481}) = (\frac{−7}{481}) =

= (\frac{−1}{481}) · (\frac{7}{481}) = (−1)^{\frac{81−1}{2}} · (\frac{481}{7}) = (\frac{−1}{7}) · (\frac{2}{7}) = −1.

Stejně uvažujeme i v druhém případu:

(\frac{7367}{24851}) = (−1)^{\frac{67−1}{2} · \frac{51−1}{2}} (\frac{2750}{7367}) = − (\frac{2}{7367}) · (\frac{1375}{7367}) =

= −(−1) · (\frac{492}{1375}) = (\frac{2}{1375})^{2} · (\frac{123}{1375}) = − (\frac{22}{123}) =

= − (\frac{2}{123}) · (\frac{11}{123}) = −(−1) · (−1) · (\frac{2}{11}) = 1.

Zjistili jsme, že čísla 4301 není kvadratickým zbytkem modulo 24851, zatímco číslo 7367 kvadratickým zbytkem je. □

Kvadratické zbytky můžeme zjišťovat i modulo složená čísla, uvědomme si ovšem, že k tomu nelze přímočaře použít Jacobiho symboly.

4.8. Najděte všechny kvadratické zbytky grupy Z_{21}^{∗}.

Najprve využijeme Čínskou větu o zbytcích, abychom kvadratické zbytky spočítali. Protože

Z_{21}^{∗} ≅ Z_{3}^{∗} × Z_{7}^{∗} ≅ Z_{2} × Z_{2} × Z_{3},

stačí spočítat počet prvků podgrupy 2(Z_{2} × Z_{2} × Z_{3}) = {0} × {0} × Z_{3} grupy Z_{2} × Z_{2} × Z_{3}, vidíme tedy, že grupa Z_{21}^{∗} obsahuje právě 3 kvadratické zbytky. Nyní snadno už snadno nahlédneme, že se jedná o prvky 1^{2} = 1, 2^{2} = 4 a 4^{2} = 16. □

Všimněme si, že 5 není kvadratický zbytek modulo 21. Ovšem 5 není kvadratický zbytek ani modulo 3 ani modulo 7, proto je hodnota Jacobiho symbolu (\frac{5}{21} ) = (\frac{5}{3}) (\frac{5}{7}) = 1.

4.9. Spočítejte kvadratické zbytky grupy Z_{75}^{∗} a Z_{225}^{∗}.

Opět využijeme Čínskou větu o zbytcích, která nám dává izomorfismus

Z_{75}^{∗} ≅ Z_{3}^{∗} × Z_{25}^{∗} ≅ Z_{2} × Z_{4} × Z_{5}.

Protože 2(Z_{2} × Z_{4} × Z_{5}) = {(0, 2a, b)| a ∈ Z_{2}, b ∈ Z_{5}}, máme v grupě Z_{75}^{∗} právě 10 kvadratických zbytků.

S grupou Z_{225}^{∗} pracujeme stejně, tentokrát máme izomorfismus

Z_{225}^{∗} ≅ Z_{3^{2}}^{∗} × Z_{5^{2}}^{∗} ≅ Z_{6} × Z_{20} ≅ Z_{2} × Z_{4} × Z_{3} × Z_{5}

a 2(Z_{2} × Z_{4} × Z_{3} × Z_{5}) = {(0, 2a, b, c)| a ∈ Z_{2}, b ∈ Z_{3}, c ∈ Z_{5}}, tudíž v grupě Z_{225}^{∗} je právě 30 kvadratických zbytků. □

Konečně poznamenejme, že hodnota Jacobiho symbolu (\frac{a}{225} ) = (\frac{a}{3})^{2} (\frac{a}{5})^{2} = 1 pro každé a ∈ Z_{225}^{∗}, ačkoli jsme zjistili, že Z_{225}^{∗} obsahuje φ(225) − 30 = 90 kvadratických nezbytků.

5. Hustota prvočísel

5.1. Najděte na základě dokázaných tvrzení dolní odhad počtu všech deseticiferných prvočísel.

Na přednášce byl dokázán horní a dolní odhad počtu π(n) prvočísel mensích jak n. Vyžijeme horní odhad pro n = 10^{9} a dolní odhad pro n = 10^{10}, tedy

π(10^{9}) < 3 · \frac{10^{9}}{log(10^{9})}, π(10^{10}) ≥ \frac{10^{10}}{log(10^{10})} · (log2 − \frac{log(10^{10} + 1)}{10^{10}} ).

Odečteme-li od sebe tyto hodnoty dostaneme dolní odhad počtu prvočísel mezi čísly 10^{9} a 10^{10}, tedy právě deseticiferných prvočísel

\frac{10^{10}}{log(10^{10})} · (log2 − \frac{log(10^{10} + 1)}{10^{10}} ) − 3 · \frac{10^{9}}{log(10^{9})} ≥ \frac{10^{9}}{log(10)}(0.693 − \frac{1}{3}) ≥ 1.5 · 10^{8}.

Další úlohy

(1) Uvažujme prvočísla p = 13, 113, 313, 613.

(a) Rozložte čísla na součin prvočinitelů v oboru Z[i],

(b) napište čísla jako součet čtverců.

(c) najděte v grupách Z_{p}^{∗} všechny druhé odmocniny z −1.

(2) Najděte v grupě Z_{313·317}^{∗} všechny druhé odmocniny z −1.

(3) Spočítejte rozklad na prvočinitele čísla 330 v oboru Z[i].

(4) Najděte všechny generátory grupy grupy charakterů grup Z_{43}^{∗}, Z_{81}^{∗}.

(5) Najděte všechny charaktery řádu 7 grupy Z_{296}^{∗}.

(6) Popište všechny involuce grup charakterů grupy Z_{66}^{∗}, Z_{147}^{∗} a Z_{1071}^{∗}.

(7) Spočítejte hodnoty (\frac{2617}{3533} ), (\frac{2533}{3533} ), (\frac{8791}{20359} ) (\frac{93757}{128713} ).

(8) Spočítejte kvadratické zbytky grup Z_{625}^{∗}, Z_{1155}^{∗} a Z_{1683}^{∗}.