Zbytkové třídy Jan Paseka Masarykova univerzita Brno Zbytkové třídy ­ p.1/15 Abstrakt V této kapitole se budeme zabývat počítáním se zbytkovými třídami. Zbytkové třídy ­ p.2/15 Abstrakt V této kapitole se budeme zabývat počítáním se zbytkovými třídami. Budeme definovat sčítání a násobení zbytkových tříd. Zbytkové třídy ­ p.2/15 Abstrakt V této kapitole se budeme zabývat počítáním se zbytkovými třídami. Budeme definovat sčítání a násobení zbytkových tříd. Ukážeme, že zbytkové třídy tvoří komutativní grupu vzhledem k takto definovanému sčítání a komutativní monoid vzhledem k násobení. Zbytkové třídy ­ p.2/15 Abstrakt V této kapitole se budeme zabývat počítáním se zbytkovými třídami. Budeme definovat sčítání a násobení zbytkových tříd. Ukážeme, že zbytkové třídy tvoří komutativní grupu vzhledem k takto definovanému sčítání a komutativní monoid vzhledem k násobení. Budeme charakterizovat invertibilní prvky vůči operaci násobení. Zbytkové třídy ­ p.2/15 Obsah přednášky Kongruence a b (mod n) podle modulu n. Faktorová množina Zn. Množina zbytkových tříd a operace na ní. Zbytkové třídy ­ p.3/15 Obsah přednášky Kongruence a b (mod n) podle modulu n. Faktorová množina Zn. Množina zbytkových tříd a operace na ní. (Zn, +) je komutativní grupa. (Zn, ) je komutativní monoid. Invertibilní prvky v (Zn, ). Zbytkové třídy ­ p.3/15 Kongruence podle modulu Necht' n N a necht' a, b Z. Ř ekneme, že čísla a, b jsou kongruentní podle modulu n, jestliže n | a - b. Zbytkové třídy ­ p.4/15 Kongruence podle modulu Necht' n N a necht' a, b Z. Ř ekneme, že čísla a, b jsou kongruentní podle modulu n, jestliže n | a - b. Píšeme a b (mod n) . Zbytkové třídy ­ p.4/15 Kongruence podle modulu Necht' n N a necht' a, b Z. Ř ekneme, že čísla a, b jsou kongruentní podle modulu n, jestliže n | a - b. Píšeme a b (mod n) . a b (mod n), právě když čísla a, b dají po dělení číslem n stejný zbytek. Zbytkové třídy ­ p.4/15 Relace kongruence Zvolme číslo n N pevně. Zbytkové třídy ­ p.5/15 Relace kongruence Zvolme číslo n N pevně. Uvedeným předpisem je definována binární relace na množině Z, které říkáme relace kongruence podle modulu n. Zbytkové třídy ­ p.5/15 Relace kongruence Zvolme číslo n N pevně. Uvedeným předpisem je definována binární relace na množině Z, které říkáme relace kongruence podle modulu n. Tato relace je ekvivalence na Z. Zbytkové třídy ­ p.5/15 Relace kongruence Zvolme číslo n N pevně. Uvedeným předpisem je definována binární relace na množině Z, které říkáme relace kongruence podle modulu n. Tato relace je ekvivalence na Z. Příslušnou faktorovou množinu, to znamená roz- klad množiny Z podle této ekvivalence pak zna- číme Zn. Zbytkové třídy ­ p.5/15 Zbytková třída podle modulu Pro každé číslo a Z značíme [a]n třídu tohoto rozkladu obsahující a, takže máme [a]n = {b Z | a b (mod n)}, a nazýváme tuto množinu zbytkovou třídou čísla a podle modulu n. Zbytkové třídy ­ p.6/15 Zbytková třída podle modulu Pro každé číslo a Z značíme [a]n třídu tohoto rozkladu obsahující a, takže máme [a]n = {b Z | a b (mod n)}, a nazýváme tuto množinu zbytkovou třídou čísla a podle modulu n. Můžeme pak psát Zn = {[a]n | a Z}. Zbytkové třídy ­ p.6/15 Zbytková třída podle modulu Pro každé číslo a Z značíme [a]n třídu tohoto rozkladu obsahující a, takže máme [a]n = {b Z | a b (mod n)}, a nazýváme tuto množinu zbytkovou třídou čísla a podle modulu n. Můžeme pak psát Zn = {[a]n | a Z}. Někdy též píšeme Zn = {k Z; k < n} = {0, 1, . . . , n - 1}.Zbytkové třídy ­ p.6/15 Vlastnosti zbytkových tříd Pro libovolná čísla a, b Z máme [a]n = [b]n a b (mod n). Zbytkové třídy ­ p.7/15 Vlastnosti zbytkových tříd Pro libovolná čísla a, b Z máme [a]n = [b]n a b (mod n). Je-li r zbytek po dělení čísla a Z číslem n, platí n | a - r. Tedy a r (mod n). Zbytkové třídy ­ p.7/15 Vlastnosti zbytkových tříd Pro libovolná čísla a, b Z máme [a]n = [b]n a b (mod n). Je-li r zbytek po dělení čísla a Z číslem n, platí n | a - r. Tedy a r (mod n). Odtud [a]n = [r]n, r {0, 1, . . . , n - 1}. Zároveň pro s, t {0, 1, . . . , n - 1} splňující s = t máme [s]n [t]n = . Zbytkové třídy ­ p.7/15 Vlastnosti zbytkových tříd Pro libovolná čísla a, b Z máme [a]n = [b]n a b (mod n). Je-li r zbytek po dělení čísla a Z číslem n, platí n | a - r. Tedy a r (mod n). Odtud [a]n = [r]n, r {0, 1, . . . , n - 1}. Zároveň pro s, t {0, 1, . . . , n - 1} splňující s = t máme [s]n [t]n = . Celkem Zn = {[0]n, [1]n, . . . , [n - 1]n}. Zbytkové třídy ­ p.7/15 (Zn, +) je grupoid Tvrzení. Pro libovolné n N a pro libovolná a, b, c, d Z platí: [a]n = [c]n & [b]n = [d]n = [a + b]n = [c + d]n. Zbytkové třídy ­ p.8/15 (Zn, +) je grupoid Tvrzení. Pro libovolné n N a pro libovolná a, b, c, d Z platí: [a]n = [c]n & [b]n = [d]n = [a + b]n = [c + d]n. Na faktorové množině Zn lze korektně definovat binární operaci +. Pro a, b Z klademe [a]n + [b]n = [a + b]n. Zbytkové třídy ­ p.8/15 (Zn, +) je grupoid Tvrzení. Pro libovolné n N a pro libovolná a, b, c, d Z platí: [a]n = [c]n & [b]n = [d]n = [a + b]n = [c + d]n. Na faktorové množině Zn lze korektně definovat binární operaci +. Pro a, b Z klademe [a]n + [b]n = [a + b]n. [a]n + [b]n je zbytková třída [r]n, kde r je zbytek po dělení součtu a + b číslem n. Zbytkové třídy ­ p.8/15 Sčítání v Z5 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 Tabulka sčítání v Z5. Zbytkové třídy ­ p.9/15 (Zn, +) je komutativní grupa Věta. Pro libovolné n N je (Zn, +) komutativní grupa. Zbytkové třídy ­ p.10/15 (Zn, +) je komutativní grupa Věta. Pro libovolné n N je (Zn, +) komutativní grupa. + na Zn je asociativní a komutativní. Zbytkové třídy ­ p.10/15 (Zn, +) je komutativní grupa Věta. Pro libovolné n N je (Zn, +) komutativní grupa. + na Zn je asociativní a komutativní. zbytková třída [0]n je jednotkovým prvkem vzhledem k operaci +. Zbytkové třídy ­ p.10/15 (Zn, +) je komutativní grupa Věta. Pro libovolné n N je (Zn, +) komutativní grupa. + na Zn je asociativní a komutativní. zbytková třída [0]n je jednotkovým prvkem vzhledem k operaci +. Pro libovolné a Z je třída [-a]n inverzním prvkem ke třídě [a]n. Zbytkové třídy ­ p.10/15 (Zn, ) je grupoid Tvrzení. Pro libovolné n N a pro libovolná a, b, c, d Z platí: [a]n = [c]n & [b]n = [d]n = [ab]n = [cd]n. Zbytkové třídy ­ p.11/15 (Zn, ) je grupoid Tvrzení. Pro libovolné n N a pro libovolná a, b, c, d Z platí: [a]n = [c]n & [b]n = [d]n = [ab]n = [cd]n. Na faktorové množině Zn lze korektně definovat také binární operaci . Pro a, b Z klademe [a]n [b]n = [ab]n. Zbytkové třídy ­ p.11/15 (Zn, ) je grupoid Tvrzení. Pro libovolné n N a pro libovolná a, b, c, d Z platí: [a]n = [c]n & [b]n = [d]n = [ab]n = [cd]n. Na faktorové množině Zn lze korektně definovat také binární operaci . Pro a, b Z klademe [a]n [b]n = [ab]n. [a]n [b]n je zbytková třída [r]n, kde r je zbytek po dělení součinu ab číslem n. Zbytkové třídy ­ p.11/15 Násobení v Z5. 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 Tabulka násobení v Z5. Zbytkové třídy ­ p.12/15 (Zn, ) je komutativní monoid Věta. Pro libovolné n N je (Zn, ) komutativní monoid. Zbytkové třídy ­ p.13/15 (Zn, ) je komutativní monoid Věta. Pro libovolné n N je (Zn, ) komutativní monoid. na Zn je asociativní a komutativní. Zbytkové třídy ­ p.13/15 (Zn, ) je komutativní monoid Věta. Pro libovolné n N je (Zn, ) komutativní monoid. na Zn je asociativní a komutativní. zbytková třída [1]n je jednotkovým prvkem vzhledem k operaci . Zbytkové třídy ­ p.13/15 Inverzní prvky v (Zn, ) Věta. Necht' n N a necht' a Z. Pak zbytková třída [a]n má inverzní prvek v monoidu (Zn, ) právě tehdy, když (a, n) = 1, to jest právě tehdy, když čísla a, n jsou nesoudělná. Zbytkové třídy ­ p.14/15 Inverzní prvky v (Zn, ) Věta. Necht' n N a necht' a Z. Pak zbytková třída [a]n má inverzní prvek v monoidu (Zn, ) právě tehdy, když (a, n) = 1, to jest právě tehdy, když čísla a, n jsou nesoudělná. Pro libovolné n N položme Z# n = {[a]n | a Z, (a, n) = 1}. Zbytkové třídy ­ p.14/15 Inverzní prvky v (Zn, ) Věta. Necht' n N a necht' a Z. Pak zbytková třída [a]n má inverzní prvek v monoidu (Zn, ) právě tehdy, když (a, n) = 1, to jest právě tehdy, když čísla a, n jsou nesoudělná. Pro libovolné n N položme Z# n = {[a]n | a Z, (a, n) = 1}. Z# n je právě množinou všech invertibilních prvků monoidu (Zn, ). Zbytkové třídy ­ p.14/15 (Z# n , ) je komutativní grupa Fakt: Součin nesoudělných prvků s n je nesoudělný prvek s n. Zbytkové třídy ­ p.15/15 (Z# n , ) je komutativní grupa Fakt: Součin nesoudělných prvků s n je nesoudělný prvek s n. Tedy (Z# n , ) je komutativní monoid. Zbytkové třídy ­ p.15/15 (Z# n , ) je komutativní grupa Fakt: Součin nesoudělných prvků s n je nesoudělný prvek s n. Tedy (Z# n , ) je komutativní monoid. Důsledek. Pro libovolné n N je (Z# n , ) komutativní grupa. Zbytkové třídy ­ p.15/15 (Z# n , ) je komutativní grupa Fakt: Součin nesoudělných prvků s n je nesoudělný prvek s n. Tedy (Z# n , ) je komutativní monoid. Důsledek. Pro libovolné n N je (Z# n , ) komutativní grupa. Pro libovolné a Z, (a, n) = 1 existují u, v Z, (u, n) = 1 taková, že 1 = au + nv. Tedy [1]n = [a]n [u]n a třída [u]n je inverzním prvkem ke třídě [a]n. Zbytkové třídy ­ p.15/15