Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo oooooooooooo Diskrétni matematika - 1. týden Elementární teorie čísel - dělitelnost Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Společní dělitelé a a společné násobky oooooooooooo Obsah přednášky Problémy teorie čísel Dělitelnost ooo ooooo Problémy teorie čísel Dělitelnost Q Společní dělitelé a a společné násobky Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooooooo Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo oooooooooooo • 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. • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Společní dělitelé a a společné násobky oooooooooooo Plán přednášky __ Problémy teorie čísel Dělitelnost ooo ooooo Problémy teorie čísel Dělitelnost Q Společní Problémy teorie čísel •OO Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooooooo Přirozená a celá čísla jsou nejjednodušší matematickou strukturou, zkoumání jejich vlastností však postavilo před generace matematiku celou řadu velice obtížných problémů. Často jsou to problémy, které je možno snadno formulovat, přesto však dodnes neznáme jejich řešení. V několika přednáškách se teď budeme zabývat úlohami o celých číslech. Převážně v nich půjde o dělitelnost celých čísel, popřípadě o řešení rovnic v oboru celých nebo přirozených čísel. God made integers, all else is the work of man. (L. Kronecker) • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla • Goldbachova hypotéza (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla • Goldbachova hypotéza (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), • velká Fermatova věta (Fermaťs Last Theorem) - rozhodnout, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí x" + y" = z"; Pierre de Fermat jej formuloval cca 1637, vyřešil Andrew Wiles v roce 1995. Problémy teorie čísel OO* Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooooooo Bruče Willis a Samuel Jackson ve filmu Smrtonosná past 3 mají za úkol zlikvidovat bombu pomoci 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů. Mají tedy vyřešit nad celými čísly rovnici 3/c + bl = 4. To asi zvládneme - např. tak, že si všimneme, že bl musí dávat po dělení 3 zbytek 1. Je tedy í = 2 + 3ř pro jakékoliv celé t (protože je při počítání "až na násobky tří'pětka totéž co dvojka a ta je sama sobě inverzním prvkem). Dosazením spočteme 3(/c + 5ř) = —6 a tedy volba t dá řešení Umíme to pro jakékoliv koeficienty? Jak by to dopadlo třeba pro (k,£) = (-2 5t,2 + 3t)- 2k + M = 3? Problémy teorie číše Dělitelnost Společní dělitelé a a společné násobky ooo ooooo oooooooooooo Plán přednášky Q Problémy teorie čísel 0 Dělitelnost Q Společní dělitelé a a společné násobky Problémy teorie číše ooo Dělitelnost •oooo Společní dělitelé a a společné násobky oooooooooooo Definice Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a ■ c = b. Píšeme pak a | b. Problémy teorie číše ooo Dělitelnost •oooo Společní dělitelé a a společné násobky oooooooooooo Definice Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a ■ c = b. Píšeme pak a | 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; Problémy teorie číše ooo Dělitelnost •oooo Společní dělitelé a a společné násobky oooooooooooo Definice Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a ■ c = b. Píšeme pak a | 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 | b A b | c a \ b A a | c c ^ 0 alfa A fa > 0 a | c a \ b + c A a | b — c (a | b <í=^> ac | bc) a< b Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo o»ooo oooooooooooo Příklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo o»ooo oooooooooooo Príklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem Řešení Platí n2 — 1 = (n + l)(n — 1), a tedy číslo n + 1 dělí číslo n2 — 1. Předpokládejme, že n + 1 dělí i číslo n2 + 1. Pak ovšem musí dělit i rozdíl (n2 + 1) - (n2 - 1) = 2. Protože n G N, platí n + 1 > 2, a tedy z n + 1 | 2 plyne n + 1 = 2, proto n = 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. □ Společní dělitelé a a společné násobky oooooooooooo Dělení se zbvtkem Problémy teorie čísel Dělitelnost ooo oo»oo Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 6 Z, m £ N existují jednoznačně určená čísla q 6 Z, r £ {0,1,..., m — 1} tak, že a = qm + r. Problémy teorie číše Dělitelnost Společní dělitelé a a společn násobky ooo oo»oo oooooooooooo Dělení se zbytk* BITI Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 6 Z, m £ N existují jednoznačně určená čísla q 6 Z, r £ {0,1,..., m — 1} tak, že a = qm + r. Důkaz. Dokažme nejprve existenci čísel q, r. Předpokládejme, že přirozené číslo m je dáno pevně a dokažme úlohu pro libovolné a 6 Z. Nejprve budeme předpokládat, že a £ No a existenci čísel q, r dokážeme indukcí: Problémy teorie číše Dělitelnost Společní dělitelé a a společn násobky ooo oo»oo oooooooooooo Dělení se zbytk* BITI Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 6 Z, m £ N existují jednoznačně určená čísla q 6 Z, r £ {0,1,..., m — 1} tak, že a = qm + r. Důkaz. Dokažme nejprve existenci čísel q, r. Předpokládejme, že přirozené číslo m je dáno pevně a dokažme úlohu pro libovolné a 6 Z. Nejprve budeme předpokládat, že a £ No a existenci čísel q, r dokážeme indukcí: Je-li 0 < a < m, stačí volit q = 0, r = a a rovnost a = qm + r platí. <(5P> Problémy teorie číše Dělitelnost Společní dělitelé a a společn násobky ooo oo»oo oooooooooooo Dělení se zbytk* BITI Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 6 Z, m £ N existují jednoznačně určená čísla q 6 Z, r £ {0,1,..., m — 1} tak, že a = qm + r. Důkaz. Dokažme nejprve existenci čísel q, r. Předpokládejme, že přirozené číslo m je dáno pevně a dokažme úlohu pro libovolné a 6 Z. Nejprve budeme předpokládat, že a £ No a existenci čísel q, r dokážeme indukcí: Je-li 0 < a < m, stačí volit q = 0, r = a a rovnost a = qm + r platí. Předpokládejme nyní, že a > m a že jsme existenci čísel q, r dokázali pro všechna a' 6 {0,1, 2,..., a — 1}. Speciálně pro a' = a — m tedy existují q', r' tak, že a' = q'm + r' a přitom r' £ {0,1,..., m — 1}. Zvolíme-li q = q' + 1, r = r', platí a = a' + m = (q' + l)m + r' = qm + r, což jsme chtěli dokázat. □ Problémy teorie číše ooo Dělitelnost ooo»o Společní dělitelé a a společné násobky oooooooooooo 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 = — q'm — 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, r s požadovanými vlastnostmi existují pro každé a G Z, m G N. Problémy teorie číše ooo Dělitelnost ooo»o Společní dělitelé a a společné násobky oooooooooooo 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 = — q'm — 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, r s 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, <72 £ Z; 1, r2 G {0,1,..., m — 1} platí a = gim + ri = + ^2- Úpravou dostaneme ri — r2 = (<72 — a tedy m \ r\ — r2- Ovšem z 0 < r\ < m, 0 < r2 < m plyne —m < r\ — r2 < m, odkud dostáváme r\ — r2 = 0. Pak ale i (92 — O čísel 3i,32, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel 3i,32, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel 3i,32 a značí se (31,32) (resp. [31,32]). Problémy teorie číše ooo Dělitelnost ooooo Společní dělitelé a a společné násobky O0OOOOOOOOOO Poznámka Přímo z definice plyne, že pro libovolné a, b G Z platí (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = \a\, (a, 0) = \a [a,0] =0. Problémy teorie číše ooo Dělitelnost ooooo Společní dělitelé a a společné násobky O0OOOOOOOOOO Poznámka Přímo z definice plyne, že pro libovolné a, b G Z platí (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = \a\, (a, 0) = \a [a,0] =0. Poznámka 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), a„) [ai,..., an] = [[ai,..., a„-i], an] Problémy teorie ooo Dělitelnost ooooo Společní dělitelé a a spole oo«ooooooooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla /r?i, /r?2 £ No totiž podle definice platí, že pokud m\ \ rri2 a zároveň rr>2 | mi, je nutně m\ = rri2- 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]. Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a a společné násobky oo«ooooooooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla /r?i, /r?2 £ No totiž podle definice platí, že pokud m\ \ rri2 a zároveň rr>2 | mi, je nutně m\ = rri2- 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 3i, 32 jsou přirozená čísla. Pro každé n > 3, pro které än-i Ý 0, označme an zbytek po dělení čísla a„_2 číslem a„_i. Pak po konečném počtu kroků dostaneme a^ = 0 a platí 3k-l = (ai, 32)- Problémy teorie číše ooo Dělitelnost ooooo Společní dělitelé a a společné násobky OOO0OOOOOOOO Důkaz. 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 = 0, přičemž 3/<_i 7^ 0. Z definice čísel an plyne, že existují celá čísla qi, q2,..., qk-2 tak, že 3\ = qi ■ a2 + a3, 3k-3 = qk-3 ■ 3k-2 + 3k-l 3k-2 = qk-2 ■ 3k-í- Z poslední rovnosti plyne, že 3/<_i | 3^-2, dále 3/<_i | 3^-3, atd tedy ak-\ společný dělitel čísel 3i,32- Naopak jejich libovolný společný dělitel dělí i číslo 33 = a\ — q\32, proto i 34 = 32 - 9233,..., a proto i ak-\ = 3k-3 - qk-33k-2- Dokázali jsme, že 3/(_1 je největší společný dělitel čísel a\, 32. je □ Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo oooo»ooooooo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, fa) = (a, —fa) = (—a, fa) = (—a, —fa), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo oooo»ooooooo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, fa) = (a, —fa) = (—a, fa) = (—a, —fa), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla a\, 32 existuje jejich největší společný dělitel (ai, 32), přitom existují celá čísla k\, /c2 tak, že (ai, a2) = /qsi + k2a2. Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo 00000*000000 Důkaz. Jistě stačí větu dokázat pro a\, a2 G N. Všimněme si, že jestliže je možné nějaká čísla r, s G Z vyjádřit ve tvaru r = r\3\ + r2a2, s = s\3\ + S232, kde ri, r2, si,s2 G Z, můžeme tak vyjádřit i r + s = (n + si)si + (r2 + s2)a2 a také c • r = (c • ri)ai + (c • r2)a2 pro libovolné c G Z. Protože 3i = 1 • a\ + 0 • 32, 32 = 0 • 3i + 1 • 32, plyne z (5), že takto můžeme vyjádřit i 33 = 3l — <7l32, 34 = 32 — <7233, . . . , 3fr_i = 3fr_3 — qk-3ak-2, coz je ovšem (si, 32). □ 4Ľ3*4l3*4 = k4 = * ^ -O^O Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a a společné násobky oooooo»ooooo Príklad Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s využitím výpočetní techniky i pro relativně velká čísla poměrně rychlý. V našem příkladu to vyzkoušíme na 2 číslech A,B, z nichž každé je součinem dvou 101-ciferných prvočísel. Všimněme si, že výpočet největšího společného dělitele i takto velkých čísel trval zanedbatelný čas. Příklad v systému SAGE je dostupný na https://sage.math.muni.cz/home/pub/6/. Poznámka Euklidův algoritmus a Bezoutova věta jsou základními výsledky elementární teorie čísel a tvoří jeden z pilířů algoritmů algebry a teorie čísel. 4Ľ3k4l3*4 = k4 = * -š -O^O Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo ooooooo»oooo Nejmenší společný násobek Věta Pro libovolná celá čísla a\, 32 existuje jejich nejmenší společný násobek [si, 32] a platí (si, 32) • [si, 32] = |si • 321- Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo ooooooo»oooo Nejmenší společný násobek Věta Pro libovolná celá čísla a\, 32 existuje jejich nejmenší společný násobek [si, a?\ a platí(si, 32) • [si, 32] = \a\ • 321. Důkaz. Věta jistě platí, je-li některé z čísel 3i, 32 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla 3i,32 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a\ • 32/(31, 32) je nejmenší společný násobek čísel 3i, 32. □ Problémy teorie číše ooo Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooo»ooo Dokončení. Protože (ai, 32) je společný dělitel čísel 3i, 32, jsou 31/(31,32) i 32/(31,32) celá čísla, a proto _ 3i32 _ 3i _ 32 (31,32) (31,32) (31,32) je společný násobek čísel a\, 32. Podle věty 3 existují k\, k2 6 Z tak, že (si, 32) = k\3\ + ^32- Předpokládejme, že n 6 Z je libovolný společný násobek čísel 3i,32 a ukážeme, že je dělitelný číslem q. Je tedy n/si, n/a2 £ Z, a proto je i celé číslo n . n n(k1a1 + k2a2) n(a1,a2) n — • K\ H--• «2 = - = - = — ■ 32 3l 3i32 3i32 Í7 To ovšem znamená, že q \ n, což jsme chtěli dokázat. □ ■0 0.0 Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo ooooooooo»oo Nesoudělnost Definice Čísla 3i, 32,..., an G Z se nazývají nesoudělná, jestliže platí (si, 32,..., 3„) = 1. Čísla 3i, 32,..., sn G Z se nazývají po dvou nesoudělná, jestliže pro každé i, j takové, že 1 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. Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooooo»o Věta Pro libovolná přirozená čísla a, b, c platí O (ac, bc) = (a, b) • c, 0 jestliže a \ bc, (a, b) = 1, pak a \ c, 0 d = (a, b) právě tehdy, když existujíqi, q2 £ N tak, že a = dqi, b = dq2 a (gi, g2) = 1- Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky ooo ooooo ooooooooooo* 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, fac). Podle Bezoutovy věty existují k, I G Z tak, že (a, Ď) = /ca + A£>. Protože (ac, fac) je společný dělitel čísel ac, fac, dělí i číslo kac + Ibc = (a, Ď) • c. Dokázali jsme, že (a, b) • c a (ac, fac) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. Problémy teorie číše ooo Dělitelnost ooooo Společní dělitelé a a společné násobky 00000000000» 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, fac). Podle Bezoutovy věty existují It.lsZ tak, že (a, fa) = /ca + /fa. Protože (ac, bc) je společný dělitel čísel ac, fac, dělí i číslo kac + A£>c = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, fac) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. ad 2. Předpokládejme, že (a, b) = 1 a a | fac. Podle Bezoutovy věty existují It.lsZ tak, že ka + Ib = 1, odkud plyne, že c = c(/ca + A£>) = /cca + lbe. Protože a | fac, plyne odsud, že i a | c. Problémy teorie číše ooo Dělitelnost ooooo Společní dělitelé a a společné násobky 00000000000» 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, fac). Podle Bezoutovy věty existují It.lsZ tak, že (a, fa) = /ca + /fa. Protože (ac, bc) je společný dělitel čísel ac, fac, dělí i číslo kac + A£>c = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, fac) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. ad 2. Předpokládejme, že (a, b) = 1 a a | fac. Podle Bezoutovy věty existují It.lsZ tak, že ka + Ib = 1, odkud plyne, že c = c(/ca + A£>) = /cca + lbe. Protože a | fac, plyne odsud, že i a | c. ad 3. Nechť d = (a, fa), pak existují qi, q2 G N tak, že a = c/qi, fa = dq2. Pak podle 1. části platí d = (a, b) = (dqx, dq2) = d ■ (qi, q2), a tedy (qi, q2) = 1. Naopak, je-li a = c/qi, b = c/q2 a (qi, q2) = 1, pak (a, b) = (c/qi, c/q2) = d(qi, q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). □