Vlastnosti celých čísel Jan Paseka Masarykova univerzita Brno Vlastnosti celých čísel ­ p.1/14 Abstrakt V této kapitole se budeme zabývat dělitelností a prvočísly. Vlastnosti celých čísel ­ p.2/14 Abstrakt V této kapitole se budeme zabývat dělitelností a prvočísly. Zformulujeme Euklidův algoritmus pro nalezení největšího společného dělitele přirozených čísel. Vlastnosti celých čísel ­ p.2/14 Abstrakt V této kapitole se budeme zabývat dělitelností a prvočísly. Zformulujeme Euklidův algoritmus pro nalezení největšího společného dělitele přirozených čísel. Ukážeme, že každé netriviální přirozené číslo lze jednoznačným způsobem rozložit na součin prvočísel a že prvočísel je nekonečně mnoho. Vlastnosti celých čísel ­ p.2/14 Obsah přednášky Dělitelnost, dělitel. Věta o dělení se zbytkem. Podíl, zbytek. Společný dělitel, největší společný dělitel. Euklidův algoritmus. Bezoutova rovnost. Nesoudělnost. Vlastnosti celých čísel ­ p.3/14 Obsah přednášky Dělitelnost, dělitel. Věta o dělení se zbytkem. Podíl, zbytek. Společný dělitel, největší společný dělitel. Euklidův algoritmus. Bezoutova rovnost. Nesoudělnost. Prvočísla. Věta o rozkladu na součin prvočísel. Prvočísel je nekonečně mnoho. Vlastnosti celých čísel ­ p.3/14 Dělitelnost I Pracujeme s množinou N = {1, 2, 3, . . . } všech přirozených čísel Vlastnosti celých čísel ­ p.4/14 Dělitelnost I Pracujeme s množinou N = {1, 2, 3, . . . } všech přirozených čísel a s množinou Z = {. . . , -2, -1, 0, 1, 2, . . . } všech celých čísel. Vlastnosti celých čísel ­ p.4/14 Dělitelnost I Pracujeme s množinou N = {1, 2, 3, . . . } všech přirozených čísel a s množinou Z = {. . . , -2, -1, 0, 1, 2, . . . } všech celých čísel. Ř ekneme, že číslo a Z dělí číslo b Z, jestliže existuje číslo z Z takové, že b = az. Vlastnosti celých čísel ­ p.4/14 Dělitelnost II Pokud číslo a Z dělí číslo b Z, říkáme, že číslo a je dělitel čísla b, a píšeme a | b. Vlastnosti celých čísel ­ p.5/14 Dělitelnost II Pokud číslo a Z dělí číslo b Z, říkáme, že číslo a je dělitel čísla b, a píšeme a | b. Speciálně, a | 0 pro každé a Z, 0 | b když a jen když b = 0. Vlastnosti celých čísel ­ p.5/14 Věta o dělení celých čísel se zbytkem Věta. Necht' a Z, b N. Pak existují q, r Z splňující a = bq + r, 0 r < b. Vlastnosti celých čísel ­ p.6/14 Věta o dělení celých čísel se zbytkem Věta. Necht' a Z, b N. Pak existují q, r Z splňující a = bq + r, 0 r < b. Přitom čísla q, r jsou určena jednoznačně. Vlastnosti celých čísel ­ p.6/14 Věta o dělení celých čísel se zbytkem Věta. Necht' a Z, b N. Pak existují q, r Z splňující a = bq + r, 0 r < b. Přitom čísla q, r jsou určena jednoznačně. Poznámka. Č íslo q se potom nazývá podíl a číslo r zbytek po dělení čísla a číslem b. Č íslo r označujeme jako a mod b. Vlastnosti celých čísel ­ p.6/14 Společný dělitel Č íslo c Z se nazývá společný dělitel čísel a, b Z, jestliže c | a a také c | b. Vlastnosti celých čísel ­ p.7/14 Společný dělitel Č íslo c Z se nazývá společný dělitel čísel a, b Z, jestliže c | a a také c | b. Č íslo d Z, které je společným dělitelem čísel a, b a které je přitom největším číslem s touto vlastností, se nazývá největší společný dělitel čísel a, b. Vlastnosti celých čísel ­ p.7/14 Společný dělitel Č íslo c Z se nazývá společný dělitel čísel a, b Z, jestliže c | a a také c | b. Č íslo d Z, které je společným dělitelem čísel a, b a které je přitom největším číslem s touto vlastností, se nazývá největší společný dělitel čísel a, b. Je-li a = 0 nebo b = 0, pak tento největší společný dělitel d čísel a, b existuje, přitom d N, a značí se (a, b). Vlastnosti celých čísel ­ p.7/14 Společný dělitel Č íslo c Z se nazývá společný dělitel čísel a, b Z, jestliže c | a a také c | b. Č íslo d Z, které je společným dělitelem čísel a, b a které je přitom největším číslem s touto vlastností, se nazývá největší společný dělitel čísel a, b. Je-li a = 0 nebo b = 0, pak tento největší společný dělitel d čísel a, b existuje, přitom d N, a značí se (a, b). Je-li a = b = 0, pak největší společný dělitel čísel a, b podle dané definice neexistuje. Vlastnosti celých čísel ­ p.7/14 Euklidův algoritmus Metoda pro nalezení největšího společného dělitele (a, b) dvou čísel a, b N. Vlastnosti celých čísel ­ p.8/14 Euklidův algoritmus Metoda pro nalezení největšího společného dělitele (a, b) dvou čísel a, b N. Provádí se postupně následující dělení se zbytkem. Vlastnosti celých čísel ­ p.8/14 Euklidův algoritmus Metoda pro nalezení největšího společného dělitele (a, b) dvou čísel a, b N. Provádí se postupně následující dělení se zbytkem. while a = 0 do r - a mod b a - b b - r return Vlastnosti celých čísel ­ p.8/14 Příklad na Euklidův algoritmus Nalezněte (143, 110). Vlastnosti celých čísel ­ p.9/14 Příklad na Euklidův algoritmus Nalezněte (143, 110). 143 = 1 × 110 + 33 Vlastnosti celých čísel ­ p.9/14 Příklad na Euklidův algoritmus Nalezněte (143, 110). 143 = 1 × 110 + 33 110 = 3 × 33 + 11 Vlastnosti celých čísel ­ p.9/14 Příklad na Euklidův algoritmus Nalezněte (143, 110). 143 = 1 × 110 + 33 110 = 3 × 33 + 11 33 = 3 × 11 + 0 Vlastnosti celých čísel ­ p.9/14 Příklad na Euklidův algoritmus Nalezněte (143, 110). 143 = 1 × 110 + 33 110 = 3 × 33 + 11 33 = 3 × 11 + 0 Výsledek: (143, 110) = 11. Vlastnosti celých čísel ­ p.9/14 Matematický popis Euklidova algoritm Postupně se tedy hledají čísla q0, q1, . . . , qn, qn+1 N {0} a r0, r1, . . . , rn N taková, že platí: Vlastnosti celých čísel ­ p.10/14 Matematický popis Euklidova algoritm Postupně se tedy hledají čísla q0, q1, . . . , qn, qn+1 N {0} a r0, r1, . . . , rn N taková, že platí: a = bq0 + r0, 0 r0 < b, b = r0q1 + r1, 0 r1 < r0, r0 = r1q2 + r2, 0 r2 < r1, r1 = r2q3 + r3, 0 r3 < r2, . . . rn-2 = rn-1qn + rn, 0 rn < rn-1, rn-1 = rnqn+1 + 0. Vlastnosti celých čísel ­ p.10/14 Ukončení a korektnost Eukl. algoritmu Poslední dělení rn-1 = rnqn+1 + 0 je tvaru rn-1 = rnqn+1 + rn+1, kde rn+1 = 0. Vlastnosti celých čísel ­ p.11/14 Ukončení a korektnost Eukl. algoritmu Poslední dělení rn-1 = rnqn+1 + 0 je tvaru rn-1 = rnqn+1 + rn+1, kde rn+1 = 0. Poněvadž b > r0 > r1 > r2 > . . . , musí tato posloupnost dělení skončit tímto způsobem. Vlastnosti celých čísel ­ p.11/14 Ukončení a korektnost Eukl. algoritmu Poslední dělení rn-1 = rnqn+1 + 0 je tvaru rn-1 = rnqn+1 + rn+1, kde rn+1 = 0. Poněvadž b > r0 > r1 > r2 > . . . , musí tato posloupnost dělení skončit tímto způsobem. Pro r0 = 0, tj. b | a a tedy (a, b) = b, položme n = -1 a označme ještě r-1 = b. Vlastnosti celých čísel ­ p.11/14 Ukončení a korektnost Eukl. algoritmu Poslední dělení rn-1 = rnqn+1 + 0 je tvaru rn-1 = rnqn+1 + rn+1, kde rn+1 = 0. Poněvadž b > r0 > r1 > r2 > . . . , musí tato posloupnost dělení skončit tímto způsobem. Pro r0 = 0, tj. b | a a tedy (a, b) = b, položme n = -1 a označme ještě r-1 = b. Pro r0 > 0 existuje n N {0} takové, že rn+1 = 0. Vlastnosti celých čísel ­ p.11/14 Ukončení a korektnost Eukl. algoritmu Poslední dělení rn-1 = rnqn+1 + 0 je tvaru rn-1 = rnqn+1 + rn+1, kde rn+1 = 0. Poněvadž b > r0 > r1 > r2 > . . . , musí tato posloupnost dělení skončit tímto způsobem. Pro r0 = 0, tj. b | a a tedy (a, b) = b, položme n = -1 a označme ještě r-1 = b. Pro r0 > 0 existuje n N {0} takové, že rn+1 = 0. Věta. Necht' a, b N. Pak (a, b) = rn. Vlastnosti celých čísel ­ p.11/14 Bezoutova rovnost Věta. Pro libovolná a, b Z taková, že a = 0 nebo b = 0, existují u, v Z taková, že (a, b) = au + bv. Vlastnosti celých čísel ­ p.12/14 Bezoutova rovnost Věta. Pro libovolná a, b Z taková, že a = 0 nebo b = 0, existují u, v Z taková, že (a, b) = au + bv. Důsledek. Necht' a, b Z, a = 0 nebo b = 0. Pak číslo d N je největším společným dělitelem čísel a, b, právě když d | a, d | b a je splněna podmínka, že pro každé číslo e N s vlastností, že e | a, e | b, platí e | d. Vlastnosti celých čísel ­ p.12/14 Nesoudělnost Ř ekneme, že čísla a, b Z jsou nesoudělná, jestliže (a, b) = 1. Vlastnosti celých čísel ­ p.13/14 Nesoudělnost Ř ekneme, že čísla a, b Z jsou nesoudělná, jestliže (a, b) = 1. Důsledek. Jestliže pro čísla a, b, c Z platí a | bc a současně (a, b) = 1, pak odtud plyne a | c. Vlastnosti celých čísel ­ p.13/14 Prvočísla Přirozené číslo p 2 se nazývá prvočíslo, jestliže přirozenými čísly, která jsou jeho děliteli, jsou pouze čísla 1 a p. Vlastnosti celých čísel ­ p.14/14 Prvočísla Přirozené číslo p 2 se nazývá prvočíslo, jestliže přirozenými čísly, která jsou jeho děliteli, jsou pouze čísla 1 a p. Věta. Pro každé přirozené číslo a 2 platí, že bud'to a je prvočíslo, anebo a je možno rozložit na součin prvočísel, přičemž tento rozklad je jediný až na pořadí činitelů. Vlastnosti celých čísel ­ p.14/14 Prvočísla Přirozené číslo p 2 se nazývá prvočíslo, jestliže přirozenými čísly, která jsou jeho děliteli, jsou pouze čísla 1 a p. Věta. Pro každé přirozené číslo a 2 platí, že bud'to a je prvočíslo, anebo a je možno rozložit na součin prvočísel, přičemž tento rozklad je jediný až na pořadí činitelů. Důsledek. Existuje nekonečně mnoho prvočísel. Vlastnosti celých čísel ­ p.14/14