Dělitelnost Společní dělitelé a a společné násobky oooo ooooooooooo Diskrétní matematika - 1. týden Elementární teorie čísel - dělitelnost Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 Společní dělitelé a a společné násobky ooooooooooo Obsah přednášky Dělitelnost oooo O Dělitel nost Q Společní dělitelé a a společné násobky Společní dělitelé a a společné násobky ooooooooooo Doporučené zdroje Dělitelnost oooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Dělitelnost Společní dělitelé a a společné násobky oooo ooooooooooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http: //is .muni . cz/el/1431/podzim2012/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. o William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf o Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Dělitelnost oooo Společní dělitelé a a společné násobky ooooooooooo Plán přednášky Q Dělitelnost □ fŠ1 Dělitelnost •ooo Společní dělitelé a a společné násobky ooooooooooo Definice Řekneme, že celé číslo a dělí cek číslem a, též b je násobek a), pr že platí a • c = b. Píšeme pak a i číslo b (neboli číslo b je dělitelné ave když existuje celé číslo c tak, b. Dělitelnost •ooo Společní dělitelé a a společné násobky ooooooooooo Definice Řekneme, že celé číslo a dělí cek číslem a, též b je násobek a), pr že platí a • c = b. Píšeme pak a i číslo b (neboli číslo b je dělitelné ave když existuje celé číslo c tak, b. Přímo z definice plyne několik jednoduchých tvrzení : Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a a; Dělitelnost •ooo Společní dělitelé a a společné násobky ooooooooooo Definice Řekneme, že celé číslo a dělí cek číslem a, též b je násobek a), pr že platí a • c = b. Píšeme pak a i číslo b (neboli číslo b je dělitelné ave když existuje celé číslo c tak, b. Přímo z definice plyne několik jednoduchých tvrzení : Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a | a; pro libovolná čísla a, b, c platí tyto čtyři implikace: a a b A b b A a | c c ^ 0 b A b > 0 a|b+c A a \ b — c (a | b ac | bc) a < b Společní dělitelé a a společné násobky ooooooooooo Dělení se zbytkem Dělitelnost o«oo Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a m a že jsme existenci čísel q, r dokázali pro všechna a7 e {0,1, 2,..., a — 1}. Speciálně pro a' — a — m tedy existují r; tak, že a' — q'm + r' a přitom r; G {0,1,..., m — 1}. Zvolíme-li q — q' + 1, r = rf, platí a = a; + m = (q; + l)m + r' — qm + r, což jsme chtěli dokázat. □ Dělitelnost oo«o Společní dělitelé a a společné násobky ooooooooooo Dokončení důkazu. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' G Z, r' G {0,1,..., m — 1} tak, že —a = q' m + r', tedy a = —qfm — r'. Je-li r; = 0, položíme r — 0, q = —q;; je-li r > 0, položíme r — m — r', q — —q' — 1. V obou případech a = q • m + r, a tedy čísla q,rs požadovanými vlastnostmi existují pro každé a G Z, m G N. Dělitelnost oo«o Společní dělitelé a a společné násobky ooooooooooo Dokončení důkazu. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' G Z, r' G {0,1,..., m — 1} tak, že —a = q' m + r', tedy a = —qfm — r'. Je-li r; = 0, položíme r — 0, q = —q;; je-li r > 0, položíme r — m — r', q — —q' — 1. V obou případech a = q • m + r, a tedy čísla q,rs požadovanými vlastnostmi existují pro každé a G Z, m G N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla gi, G Z; ri, ľ2 G {0,1,..., m — 1} platí a = qim + ri = q2in + ľ2. Úpravou dostaneme ri — T2 = ((72 <7i)/77, a tedy m | ri — r^- Ovšem z 0 < r± < m, 0 < ľ2 < m plyne —m < r± — r2 < m, odkud dostáváme r\ — r2 — 0. Pak ale i {q2 qi)m = 0, a proto q\ — q2, r\ — r^- ■v Čísla q, r jsou tedy určena jednoznačně. □ Dělitelnost ooo« Společní dělitelé a a společné násobky ooooooooooo Číslo q, resp. r z věty se nazývá (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost a = mq + r do tvaru a r . r — = q H--, přitom 0 < — < 1. mm m Dělitelnost oooo Plán prednášky Společní dělitelé a a společné násobky ooooooooooo Q Společní dělitelé a a společné násobky Dělitelnost oooo Největšř společný dělitel (gcd) Společní dělitelé a a společné násobky •oooooooooo Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána. Dělitelnost oooo Největší společný dělitel (gcd) Společní dělitelé a a společné násobky •oooooooooo Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána. Definice Mějme celá čísla ai,a2- Libovolné celé číslo m takové, že m | ai, m | a2 (resp. a\ \ m, \ m) se nazývá společný dělitel (resp. společný násobek) čísel ai,a2- Společný dělitel (resp. násobek) m > 0 čísel ai,a2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel ai,a2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel ai,a2 a značí se (ai,a2) (resp. [ai,a2]). -írnJ^ < >• ^ O Q, O Dělitelnost Společní dělitelé a a společné násobky oooo O0OOOOOOOOO Poznámka Přímo z definice plyne, že pro libovolné a, b e Z platí (a, b) = {b, a), [a,b] = [M, (*,1) = 1. [a, 1] = |a|, (a,0) = [a,0] = 0. Dělitelnost oooo Společní dělitelé a a společné násobky O0OOOOOOOOO Poznámka _1 Přímo z definice plyne, (a, b) = (b, a), [a,b] = [a,0] = 0. že pro libovolné a, b G Z platí [b, a], (a, 1) = 1, [a, 1] = |a|, (a,0) = a , Poznámka 1 Analogicky se definuje i největší společný dělitel a nejmenší společný násobek více než dvou celých čísel a snadno se následně dokáže, že platí (ai,..., an) = ((ai,..., a^—i), an) [ai,..., an] = [[ai,..., a^—i], an] Společní dělitelé a a společné násobky OO0OOOOOOOO Euklidův algoritmus Dělitelnost oooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b £ čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi, rr?2 £ No totiž podle definice platí, že pokud m\ | rr?2 a zároveň rr?2 | mi, je nutně m\ — tri2. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě, důkaz existence čísla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a,b\. Společní dělitelé a a společné násobky OO0OOOOOOOO Euklidův algoritmus Dělitelnost oooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b £ čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi, rr?2 £ No totiž podle definice platí, že pokud m\ | rr?2 a zároveň rr?2 | mi, je nutně m\ — tri2. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě, důkaz existence čísla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a,b\. Věta (Euklidův algoritmus) Necht ai, a2 jsou přirozená čísla. Pro každé n > 3, pro Ateré an-i 7^ O, označme an zbytek po dělení čísla an-2 číslem an_i po konečném počtu kroků dostaneme a^ = O a p/ar/' 3/c-i = (ai, a2). Pak Dělitelnost Společní dělitelé a a společné násobky OOOO OOO0OOOOOOO Podle Věty o dělení se zbytkem platí 32 > 33 > 34 > .... Protože jde o nezáporná celá čísla, je každé následující alespoň o 1 menší než předchozí, a proto po určitém konečném počtu kroků dostáváme 3k — 0, přičemž 3k-i 7^ 0. Z definice čísel 3n plyne, že existují celá čísla qi, q25 • • • ? 9/c-2 tak, že 3i = qi • 32 + a3, 3k-3 = Qk-3 ' 3k-2 + 3k-l 3k-2 = q k-2 ' 3k-l- Z poslední rovnosti plyne, že 3k-i \ 3k-2, dále 3k-i \ 3k-3, atd., je tedy 3k-i společný dělitel čísel 3i,32- Naopak jejich libovolný společný dělitel dělí i číslo 33 = 3\ — gi32, proto i 34 = 32 — 92^3,..., a proto i 3k-i = 3k-3 — qk-33k-2- Dokázali jsme, že 3k-i je největší společný dělitel čísel ai, 32- □ Společní dělitelé a a společné násobky oooo«oooooo Vlastnosti gcd Dělitelnost oooo Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, b) = (a, — b) = (—a, b) = (—a, —b), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Dělitelnost Společní dělitelé a a společné násobky oooo oooo«oooooo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, b) = (a, — b) = (—a, b) = (—a, —b), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla ai, a2 existuje jejich největší společný dělitel (ai, a2), pritom existují celá čísla k±, /c2 tak, že (ai,a2) = /ciai + /c2a2. Dělitelnost oooo Společní dělitelé a a společné násobky OOOOO0OOOOO Důkaz. Jistě stačí větu dokázat pro ai, a2 G N. Všimněme si, že jestliže je možné nějaká čísla r,sGZ vyjádřit ve tvaru r — r\3\ + s = s\a\ + S232, kde ri, r2, si, S2 G Z, můžeme tak vyjádřit i r + s = (n + si)ai + (r2 + s2)a2 a také c • r = (c • n)ai + (c • r2)a2 pro libovolné c £ Z. Protože ai = 1 • 3\ + 0 • a2, a2 = 0 • ai + 1 • a2, plyne z (5), že takto můžeme vyjádřit i 33 = 3i — qia2, 34 = a2 — ^2^3» ■ ■ ■, 3k-l = a/c_3 qk-33k-2, což je ovšem (ai, a2). □ Dělitelnost oooo Nejmenšř společný násobek Společní dělitelé a a společné násobky ooooooooooo Věta Pro libovolná celá čísla ai, a^ existuje jejich nejmenší společný násobek [ai, a?\ a platí(ai, a^) • [ai, a?\ — \a\-a2. Dělitelnost oooo Nejmenší společný násobek Společní dělitelé a a společné násobky oooooo«oooo Pro libovolná celá čísla ai, a2 existuje jejich nejmenší společný násobek [ai, a?\ a platí (ai, a^) • [ai, a2] = |^i • ^2 Důkaz Věta jistě platí, je-li některé z čísel ai,a2 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla ai,a2 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a± • a2/(ai, a2) je nejmenší společný násobek čísel a\.a2- □ Dělitelnost oooo Společní dělitelé a a společné násobky ooooooo«ooo Dokončení. Protože (ai, a-i) je společný dělitel čísel a±, 32, jsou ai/(ai, 32) i ^2/(31, 32) celá čísla, a proto Q = 3ia2 3\ (ai,a2) (ai,a2) • 32 = 32 (ai,a2) je společný násobek čísel ai, a2- Podle věty 3 existují ki, l<2 G tak, že (ai, a2) = /qai + ^a2- Předpokládejme, že n € Z je libovolný společný násobek čísel ai,a2 a ukážeme, že je dělitelný číslem q. Je tedy n/ai, n/a2 G Z, a proto je i celé číslo n , n ki + 32 31 k2 = n(kxai + k2a2) n(ai,a2) n 3\32 3\32 To ovšem znamená, že q n, což jsme chtěli dokázat. □ Dělitelnost oooo Nesoudělnost Společní dělitelé a a společné násobky OOOOOOOO0OO Definice Čísla ai, a2,..., a„ e Z se nazývají nesoudělná, jestliže platí (ai, a2,..., 3n) = 1. Čísla ai, a2,...,an G Z se nazývají po č/\/ol/ nesoudělná, jestliže pro každé ij takové, že 1 < / < j < n, platí (a/,a/) = 1. Poznámka V případě n — 2 oba pojmy splývají, pro n > 2 plyne z nesoudělnosti po dvou nesoudělnost, ne však naopak: například čísla 6, 10, 15 jsou nesoudělná, ale nejsou nesoudělná po dvou, neboť dokonce žádná dvojice z nich vybraná nesoudělná není: (6,10) = 2, (6,15) = 3, (10,15) = 5. -írnJ^ < >• -E O Q, O Dělitelnost oooo Společní dělitelé a a společné násobky OOOOOOOOO0O Pro libovolná přirozená čísla a, b, c platí O (ac, bc) = (a, b) • c, O jestliže a | bc, (a, b) = 1, pa/c a | c, O cf = (a, b) praVě řebc/y /cc/yž existují qi, (72 £ N ta/c, že a = c%, b = dq2 a (qu q2) = 1. Dělitelnost oooo Společní dělitelé a a společné násobky oooooooooo* Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) • c společný dělitel čísel ac, bc, proto (a, b) • c | (ac, bc). Podle Bezoutovy věty existují /c, / e Z tak, že (a, b) = /ca + /b. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + lbe = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. Dělitelnost oooo Společní dělitelé a a společné násobky oooooooooo* Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) • c společný dělitel čísel ac, bc, proto (a, b) • c | (ac, bc). Podle Bezoutovy věty existují /e, / £ Z tak, že (a, b) — ka + Ib. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + lbe = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají, ad 2. Předpokládejme, že (a, b) = 1 a a | bc. Podle Bezoutovy věty existují /c, / G Z tak, že ka + Ib = 1, odkud plyne, že c = c{ka + Ib) = kca + lbe. Protože a | bc, plyne odsud, že i a Dělitelnost oooo Společní dělitelé a a společné násobky oooooooooo* Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) • c společný dělitel čísel ac, bc, proto (a, b) • c | (ac, bc). Podle Bezoutovy věty existují /e, / £ Z tak, že (a, b) — ka + Ib. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + lbe = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. ad 2. Předpokládejme, že (a, b) = 1 a a | bc. Podle Bezoutovy věty existují /c, / G Z tak, že ka + Ib = 1, odkud plyne, že c = c{ka + Ib) = kca + lbe. Protože a | bc, plyne odsud, že i a | c. ad 3. Nechť d = (a, b), pak existují qi, (72 G N tak, ze a — dq\, b — dq2- Pak podle 1. části platí d = (a, b) = (c%, e/g2) = ^ ■ (<7i, 92). 3 tedy (qi, q2) = 1- Naopak, je-li a = c%, b = dq2 a (qi, q2) = 1, pak (a, b) = (c/qi, C/Č72) = ^(<7i5 92) — d - 1 — d (opět užitím 1. části tohoto tvrzení). □