Řešení kongruencí o jedné neznámé Podobně jako řešení rovnic vede k výpočtu neznámé, řešení kongruencí vede k určení hodnot, kterých neznámá může nabývat. Navíc se u kongruencí pohybujeme pouze v oboru celých čísel. Definice. Nechť m N, f(x), g(x) Z[x]. Zápis (1) f(x) g(x) (mod m) nazýváme kongruencí o jedné neznámé x a rozumíme jím úkol nalézt množinu řešení, tj. množinu všech takových čísel c Z, pro která f(c) g(c) (mod m). Dvě kongruence o jedné neznámé nazveme ekvivalentní, mají-li stejnou množinu řešení. Kongruence (??) je ekvivalentní s kongruencí f(x) - g(x) Z[x] 0 (mod m). Co je to počet řešení kongruence uvádí následující definice. Definice. Počtem řešení kongruence o jedné neznámé modulo m rozumíme počet zbytkových tříd modulo m obsahujících řešení této kongruence. Pro určení hodnot kongruence o jedné neznámé může sloužit následující věta. Věta. Nechť m N, f(x) Z[x]. Pro libovolná a, b Z platí a b (mod m) = f(a) f(b) (mod m). Podle výše uvedené věty je řešením kongruence vždy buď celá zbytková třída, nebo žádný její prvek. Její využití tedy spočívá v postupném zkoušení zástupců všech zbytkových tříd, a zjišťování, zda je kongruence splňená. Pro vyšší moduly je však tento postup velmi pracný. Lineární kongruence a soustavy lineárních kongruencí Nejdříve zjistíme, kdy má lineární kongruence o jedné neznámé řešení, a pokud ano, kolik řešení má. To pak využijeme i u soustav lineárních kongruencí. 1 Věta. Nechť m N, a, b Z. Označme d = (a, m). Pak kongruence ax b (mod m) (o jedné neznámé x) má řešení právě tehdy, když d | b. V případě, kdy d | b, má tato kongruence právě d řešení (modulo m). Pomocí předchozí věty lze dokázat Wilsonovu větu, která udává nutnou a postačující podmínku prvočíselnosti. Věta (Wilsonova). Přirozené číslo n > 1 je prvočíslo, právě když (2) (n - 1)! -1 (mod n) Máme-li soustavu lineárních kongruencí o téže neznámé, můžeme rozhodnout o řešitelnosti každé z kongruencí. Pokud alespoň jedna z nich není řešitelná, pak ani soustava nemá řešení. V opačném případě lze každou z kongruencí upravit na tvar x ci (mod mi). Věta. Nechť c1, c2 jsou celá čísla, m1, m2 přirozená. Označme d = (m1, m2). Soustava dvou kongruencí (3) x c1 (mod m1) x c2 (mod m2) v případě c1 c2 (mod d) nemá řešení. Jestliže naopak c1 c2 (mod d), pak existuje celé číslo c tak, že x Z splňuje danou soustavu, právě když vyhovuje kongruenci x c (mod [m1, m2]). Podobným způsobem lze určit i řešení soustavy o více než dvou kongruencích. Věta (Čínská zbytková věta). Nechť m1, , . . . , mk N jsou po dvou nesoudělná, a1, . . . , ak Z. Pak platí: soustava (4) x a1 (mod m1) ... x ak (mod mk) má jediné řešení modulo m1 m2 mk. Kongruence vyšších stupňů V obecnějším případě mohou na obou stranách kongruence stát polymony téže proměnné x s celočíselnými koeficienty. Tuto kongruenci můžeme snadno převést na tvar F(x) 0 (mod m), kde F(x) Z[x], m N. Tuto kongruenci pak můžeme řešit podle věty ??. 2 Nevýhodou výše uvedené metody je její pracnost, zvyšuje-li se hodnota modulu. Je-li m složené, m = pn1 1 . . . pnk k , kde pi, i {1, 2, . . ., k} jsou různá prvočísla, můžeme kongruenci F(x) 0 (mod m) nahradit soustavou kongruencí (5) F(x) 0 (mod pn1 1 ) ... F(x) 0 (mod pnk k ), kterou umíme řešit např. pomocí Čínské zbytkové věty; v případě vyšších mocnin prvočísel můžeme k řešení využít následující větu: Věta (Henselovo lemma). Nechť p je prvočíslo, f(x) Z[x], a Z je takové, že p | f(a), p f (a). Pak platí: pro každé n N má soustava (6) x a (mod p) f(x) 0 (mod pn ) právě jedno řešení modulo pn . Věta. Buď p prvočíslo, f(x) Z[x]. Má-li kongruence f(x) 0 (mod p) více než st(f) řešení, pak jsou všechny koeficienty polynomu f násobkem p. Binomické kongruence a primitivní kořeny Definice. Nechť m N, a Z, (a, m) = 1. Číslo a nazveme n-tým mocninným zbytkem modulo m, pokud je kongruence xn a (mod m) řešitelná. V opačném případě nazveme a n-tým mocninným nezbytkem modulo m. Pro n = 2, 3, 4 používáme termíny kvadratický, kubický a bikvadratický zbytek, resp. nezbytek modulo m. Binomické kongruence je často vhodné řešit pomocí primitivních kořenů. Definice. Nechť m N. Celé číslo a Z, (a, m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (m). Lemma 1. Je-li g primitivní kořen modulo m, pak pro každé číslo a Z, (a, m) = 1 existuje jediné xa Z, 0 xa < (m) s vlastností gxa a (mod m). Pomocí primitivních kořenů a Eulerovy funkce můžeme rozhodnout, zda je daná binomická kongruence řešitelná, a kolik má řešení. 3 Věta. Buď m N takové, že modulo m existují primitivní kořeny. Dále nechť a Z, (a, m) = 1. Pak kongruence xn a (mod m) je řešitelná (tj. a je n-tý mocninný zbytek modulo m), právě když a(m)/d 1 (mod m), kde d = (n, (m)). Přitom, je-li tato kongruence řešitelná, má právě d řešení. Je potřeba vědět, pro jaké moduly primitivní kořeny existují. Věta. Buď m N, m > 1. Primitivní kořeny modulo m existují právě tehdy, když m splňuje některou z následujících podmínek: * m = 2 nebo m = 4, * m je mocnina lichého prvočísla * m je dvojnásobek mocniny lichého prvočísla. Nyní tedy víme, pro jaké moduly primitivní kořeny existují. Obecně je ale nalezení primitivního kořene pro daný modul výpočetně náročná operace. Následující věta udává ekvivalentní podmínku pro to, aby zkoumané číslo bylo primitivním kořenem. Věta. Buď m takové, že modulo m existují primitivní kořeny. Zapišme (m) = q1 1 qk k . Pak pro libovolné g Z, (g, m) = 1 platí, že g je primitivní kořen modulo m, právě když g (m) q1 1 (mod m), . . . , g (m) qk 1 (mod m). Kvadratické kongruence, Legendrův a Jacobiho symbol Důvodem pro zavedení Lagendrova symbolu byla snaha najít jednodušší způsob ověření řešitelnosti kvadratické kongruence x2 a (mod p), resp. x2 + bx + c 0 (mod p), než jaký byl uveden v předchozí části (věta ??). Definice. Nechť je p liché prvočíslo. Legendreův symbol definujeme předpisem a p = 1 p a, a je kvadratický zbytek modulo p, 0 p | a, -1 p a, a je kvadratický nezbytek modulo p. Jakým způsobem pracovat s Legendrovým symbolem uvádí následující věta: 4 Lemma 2. Nechť p je liché prvočíslo, a, b Z libovolná. Pak platí: 1. a p a p-1 2 (mod p). 2. ab p = a p b p . 3. a b (mod p) = a p = b p . Vztah mezi Legendrovým symbolem a kvadratickými kongruencemi dokláda i následující věta. Věta. 1. V libovolné redukované soustavě zbytků modulo p je stejný počet kvadratických zbytků a nezbytků. 2. Součin dvou kvadratických zbytků je zbytek, součin dvou nezbytků je zbytek, součin zbytku a nezbytku je nezbytek. 3. (-1/p) = (-1) p-1 2 , tj. kongruence x2 -1 (mod p) je řešitelná právě tehdy, když p 1 (mod 4). Protože kongruence x2 1 (mod p) je řešitelná pro libovolné liché prvočíslo p, je Legendrův symbol 1 p = 1. Pro výpočet Legendrova symbolu je důležitá následující věta: Věta (Zákon kvadratické reciprocity). Nechť p, q jsou různá lichá prvočísla. Pak 1. -1 p = (-1) p-1 2 2. 2 p = (-1) p2-1 8 3. q p = p q (-1) p-1 2 q-1 2 Podmínku 2 předchozí věty lze ekvivalentně zapsat také takto: 2 p = 1 je-li p 1 (mod 8), -1 je-li p 3 (mod 8). Ne vždy se ale v kvadratických kongruencích na pozici modulu vyskytuje prvočíslo, bylo by ale vhodné mít k dispozici podobný nástroj k rozhodnutí o řešitelnosti, resp. neřešitelnosti, takové kongruence. Takovéto rozšíření Legendrova symbolu se nazývá Jacobiho symbol. Definice. Nechť a Z, b N, 2 b. Nechť b = p1p2 pk je rozklad b na (lichá) prvočísla (výjimečně neseskupujeme stejná prvočísla do mocniny, ale vypisujeme každé zvlášť, např. 135 = 3 3 3 5). Symbol a b = a p1 a p2 a pk se nazývá Jacobiho symbol. Vlastnosti Jacobiho symbolu jsou velmi podobné vlastnostem Legendrova symbolu. Nelze ale z jeho hodnoty zjistit, zda je daná kvadratická kongruence řešitelná, je však možné dokázat, že řešitelná není. Vlastnosti Jacobiho symbolu uvádí následující věty. 5 Věta. Nechť a, a1, a2 Z, b, b1, b2 N, 2 b1b2, 2 b. Pak platí: 1. a1 a2 (mod b) = a1 b = a2 b 2. a b1b2 = a b1 a b2 3. a1a2 b = a1 b a2 b Věta. Nechť a, b N jsou lichá nesoudělná čísla. Pak platí: 1. -1 b = (-1) b-1 2 2. 2 b = (-1) b2-1 8 3. a b b a = (-1) a-1 2 b-1 2 6