V následujícím textu užíváme označení: Zn je množina všech zbytkových tříd modulo n, dále (Z*, •) je grupa jednotek okruhu (Zn, +, •). Naším cílem je dokázat následující větu: Věta. Nechi n G N je liché složené číslo, N > 10. Rozložme N— 1 = 2t-q, kde t, q G N, 2 \ q. Pak z množiny {a G Z; 0 < a < N, (a, N) = 1} nejvýše čtvrtina čísel splní podmínku aq = l (mod N) nebo 3e G {0,1,... ,t — 1} : a2e'q = —1 (mod N). (1) Nejdříve zformulujme několik tvrzení, která budou v důkaze věty užitečná: 1. Pro libovolná u, v G N, (u, v) = 1 předpis [a]uv \—> ([a]u, [a]v) pro libovolné a G Z zadává korektně izomorfismus okruhů a tedy i izomorfismus aditivních grup (Zu„,+) (Zu,+) x (Z„,+) a izomorfismus multiplikativních grup jednotek &0^(^,-)x(Z*,.)- 2. Jestliže (G, •) je komutativní grupa a g G N, pak zobrazení / : G —> G, dané předpisem f (a) = aq pro libovolné a G G, je homomorfismus grup. Je-li navíc G konečná a její řád \G\ je nesoudělný s q, pak je / izomorfismus. 3. Je-li / : G —^ H homomorfismus grup, pak pro libovolné a, b G G platí f (a) = f (b), právě když a-ker f = b-ker f. Proto index podgrupy ker/ v grupě G je |G/ker/| = kde f(G) = {f(a);a G G}. Je-li G konečná, tak každá třída rozkladu G j ker / má | ker f\ prvků, a tedy na každý prvek f{G) se zobrazí právě | ker f \ prvků. 4. Každá konečná cyklická grupa (G, ■) řádu m je izomorfní s grupou (Zm,+). 5. Libovolná konečná cyklická grupa řádu 2C, kde c G N, má 1 prvek řádu 1, 1 prvek řádu 2, 2 prvky řádu 4, 4 prvky řádu 8, ..., 2C~1 prvků řádu 2C. 1 6. Pro každé liché prvočíslo p a libovolné n G N je grupa (Z*™, •) cyklická. Důkaz věty. Rozložme N = Yí^iP?^ kde Pii---iPs Jsou různá lichá prvočísla, e1;..., es G N. Pro každé i = 1,..., s rozložme pi — 1 = 2^ ■ qÍ7 kde íj, qi G N, 2 { qi. Máme následující izomorfismy grup (ZN^)=n(z;?'0=n(z(Pi_1)1,rl,+)= = J]((Z2tl,+) x (Z9i,+) x (Zpri,+)) = (£>,+) x kde d = n-=iZ2ti, l = n:=i(X x ^r0- Získaný izomorfismus pojmenujme ip : Z^- —>• D x L. Nechť ^DxI-^DxI je umocňování na g-tou (vzhledem k tomu, že operaci značíme aditivně, je asi lepší mluvit o násobení číslem q). Dále označme 7Td : D x L —> D a -kl '■ D x L —>• L projekce ze součinu. Charakterizujme ta a G Z, (a, N) = 1, která splní podmínku (1). Jestliže a splní tuto podmínku, pak řád [aq]N v grupě (Z^, •) je mocnina dvou a navíc je roven řádu [aq] h v grupě (Zxei, •) pro každé i = 1,..., s. Ekvivalentně to tedy můžeme popsat tak, že [a]^ G ker(7T£ o tp o ip) a navíc každá z s složek (ttd o tp o ■í/))([a]Ar) má stejný řád. Ukažme, že zúžení homomorfismu -KDOtpoip na podgrupu ker(7r£ oipoip) grupy (Z^, •) je surjektivní. Protože q je liché, je násobení číslem q na grupě (D, +) izomorfismus, a tedy pro každé d E D existuje c E D takové, že qc = d, kde qc znamená součet q kopií prvku c v grupě (D,+). Protože ip je izomorfismus, existuje a G Z, (a, N) = 1, tak, že ^([a]^-) = (c, 0), kde 0 znamená neutrální prvek grupy (L,+). Zřejmě (y? o ■0)([a]w-) = (d, 0), což dokazuje slíbené tvrzení o surjektivitě (ttd o tp o ■ŕ/>)|ker(7rLoiŕoi/;)- Odhadněme nejprve, kolik z prvků grupy (D, +) splní, že mají v každé své složce stejný řád. Je-li s = 1, tak to zřejmě splní všech 2*1 prvků, v případě s > 1 to však všechny prvky nesplní. Označme r = min{ŕi,..., ts}. V každé složce řád 1 má jediný prvek, v každé složce řád 2 má jediný prvek, v každé složce řád 4 má 2S prvků, v každé složce řád 8 má 22s prvků, v každé složce řád 16 má 23s prvků, ..., v každé složce řád 2r má 2(-r~1^s prvků. Celkový počet těchto prvků zjistíme sečtením geometrické řady 1 + 1 + 2S + 22s + 23s + • • • + 2{r'-1)s = 1 + 2'S ~ 1. 2S — 1 2 Ukažme, že pokud je s = 2, pak lze počet takových prvků odhadnout shora číslem 2rs~1, a pokud je s > 3, pak dokonce polovičním číslem 2rs~2. Skutečně, pro s = 2 platí 1 +--- = 1 +--- = 2—-2— + ± = 2—- i-£ < 2—\ 2S - 1 3 2632 3~' přičemž rovnost nastane jen v případě r = 1. Je-li s > 3, pak pro r = 1 platí 2rs - 1 1 = 2 < 2S~2 = 2rs~2 přičemž rovnost nastane jen v případě s = 3. Předpokládejme nyní s > 3 a r > 2, pak nerovnost ors _ i --- + 1 < 2—2 2S - 1 je ekvivalentní s nerovností 2S - 1 2rs + 2S - 2 <--2rs ~ 4 (násobili jsme 2S — 1 > 0), a tedy i s nerovností 2S_^ 2S - 2 <--2rs ~ 4 (odečetli jsme 2rs od obou stran). Ovšem ľjll. . 2rs > —— ■ 2S ■ 2S > (2S - 5) • 2S > 3 • 2S > 2S - 2. 4 ~ 4 v / _ Odtud plyne tvrzení věty pro s > 3, protože v tomto případě nejvýše čtvrtina prvků grupy (D, +) má ve všech složkách stejný řád, neboť \D\ > 2rs (rovnost nastane jen v případě, kdy r = las = 3a současně t\ = t) = Z^, právě když řád každé cyklické grupy, jejichž součinem je L, je dělitelem čísla q. To se nemůže stát, pokud některé e« > 1, protože Pi\N, q\N — 1, a tedy (j?i,q) = 1. Zaměřme se na případ s = 2. Víme, že nejvýše polovina prvků grupy D splní podmínku o stejných řádech. Je-li ei > 1 nebo e2 > 1, pak nejvýše třetina z prvků grupy leží v ker(7T£0(^o-í/>) a z nich nejvýše polovina se zobrazí na prvky grupy D splňující 3 podmínku o stejných řádech, odkud plyne tvrzení věty. Nechť dále N = pip2. Jestliže qi = g2, pak z pi / p2 plyne t\ ^ h, a tedy \D\ = 2Í1+Í2 > 2 • 2rs, tedy nejvýše čtvrtina prvků grupy D splňuje podmínku o stejných řádech a věta je dokázána i v tomto případě. Předpokládejme, že N = P\P2 a q± Ý q2, bez újmy na obecnosti například q± > g2. Pak q\ > 3, q± \ p\ — 1, q± \ q2, a z lichosti qi plyne q± \ 2*2 • g2 = P2 — 1- Protože 2* • q = N - 1 = pip2 - 1 = P2 - 1 (mod gi), platí gi { 2* • g, a tedy gi { g. To znamená, že nejvýše třetina z prvků grupy leží v ker(7TL o tp o ■0). Věta je dokázána i v tomto případě. Zbývá případ s = 1. Pak N = pl1, a protože iV je složené, je ei > 2. Protože g | N — 1 a px | N, je (g,pi) = 1 a násobení číslem g na grupě (Zpei-i,+) je surjektivní. Proto |(7rLoV?o^)(Z^)|>^-1>5, neboť v případě p\ = 3 z iV > 10 plyne ei > 3. Odtud plyne I ker(7TL oipoip)\ = —- < |(7rLoV?o^)(Z^)| " 5 a důkaz věty je ukončen. Poznámka. Pro zajímavost analyzujme předchozí důkaz, abychom zjistili, pro která lichá složená N > 10 platí, že právě čtvrtina čísel z množiny {a G Z; 0 < a < N, (a, N) = 1} splní podmínku (1). V případě s = 1 se to nestane nikdy. V případě s = 2 to nastane, právě když gx = g2, tx + t2 = 2r + 1, ei = 62 = 1- Jestliže předpokládáme, že p\ < P2, tak nutně t\ = r, ŕ2 = r + 1-Odtud p2 = 1 + 2i2g2 = 1 + 2il+1gx = 1 + 2(Pl - 1) = 2pi - 1. Jde tedy právě o čísla N = p\ ■ (2pi — 1), přičemž prvočíslo p\ splňuje, že také 2pi — 1 je prvočíslo. Příkladem je N = 15 nebo N = 91. V případě s > 3 musí nutně platit s = 3, íi = í2 = í3 = r = 1, ei = e2 = e3 = 1, Q2\q, Q3\q- Pak tedy každé prvočíslo Pí = 3 (mod 4), odkud iV = P1P2P3 = 3 (mod 4) a pi — 1 = 2g^ | 2g = N — 1. Znamená to, že číslo iV je Carmichaelovo číslo, které je součinem tří různých prvočísel, která dávají zbytek 3 po dělení čtyřmi. Příkladem je N = 7 ■ 19 • 67 = 8911. 4