Seminár 8: Teória čísel II – úlohy o najmenšom spoločnom násobku a najväčšom spoločnom deliteli
Ciele
Zoznámiť sa s metódami riešenia príkladov o spoločných deliteľoch a násobkoch, upevniť znalosti zo seminára predchádzajúceho.
Úlohy a riešenia
Úloha 61-I-3-N1
Riešenie*
Komentár
Úloha je relatívne jednoduchá a nevyžaduje žiadne špeciálne znalosti, zároveň však nie je triviálna. Tvorí tak príjemné preklenutie medzi školskými a olympiádnymi príkladmi.Úloha 60-I-5-N1
Riešenie
Komentár
Táto mini-úloha je prípravným krokom k nasledujúcemu všeobecnejšiemu tvrdeniu a zároveň môže pripomenúť použitie dôkazu sporom.Úloha 60-I-5-N2
Riešenie
Alternatívne môžeme vzťah dokázať úvahou o exponentoch prvočísel, z ktorých sú čísla \(a\) a \(b\) zložené. Nech \(a=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}\) a \(b=p_1^{\beta_1}\cdot p_2^{\beta_2} \cdots p_k^{\beta_k}\), kde \(p_1\) až \(p_k\) sú prvočísla a \(\alpha_k, \beta_k\) prirodzené čísla. Potom
\[\begin{aligned} (a,b) &=p_1^{\min\{\alpha_1, \beta_1\}}\cdot p_2^{\min\{\alpha_2, \beta_2\}}\cdots p_k^{\min\{\alpha_k, \beta_k\}},\\ [a,b] &=p_1^{\max\{\alpha_1, \beta_1\}}\cdot p_2^{\max\{\alpha_2, \beta_2\}}\cdots p_k^{\max\{\alpha_k, \beta_k\}},\\ ab &=p_1^{\alpha_1+\beta_1}\cdot p_2^{\alpha_2+\beta_2}\cdots p_k^{\alpha_k, \beta_k}.\end{aligned}\]
Keďže pre akékoľvek čísla \(\alpha, \beta\) platí \(\max\{\alpha, \beta\}+\min\{\alpha, \beta\}=\alpha+\beta\), a to vo všetkých prípadoch \(\alpha < \beta\), \(\alpha = \beta\), \(\alpha > \beta\), je naše tvrdenie dokázané.
Komentár
Predchádzajúce tvrdenie je stavebným kameňom mnohých úloh o spoločných násobkoch a deliteľoch, najmä myšlienka zápisu prirodzených čísel \(a\) a \(b\) v tvare \(a=ud\) a \(b=vd\), kde \(u\) a \(v\) sú prirodzené čísla také, že \((u,v)=1\) a \(d=(a,b)\) nájde uplatnenie veľmi často.Úloha 64-I-5-N4
Riešenie
Komentár
Všeobecnejší pohľad na predchádzajúci problém by sme dostali skrz pohľad na exponenty prvočísel, z ktorých sú čísla \(a, b, c\) zložené. Skúmaná rovnosť nastane len v prípade, že sú všetky tri čísla navzájom po dvoch nesúdeliteľné.Zároveň úloha demonštruje riešenie uvedením protipríkladu, čo je princíp, s ktorým sme sa v seminároch zatiaľ nestretli a jeho spomenutie je určite vhodné.
Úloha 64-I-5-N5
Riešenie
Tvrdenie pre najmenší spoločný násobok neplatí, uvedieme protipríklad. Pre čísla \(a=12\), \(b=8\), \(a+b=20\), \(a-b=4\), \([12,8]=24\), avšak \([12,8,20,4]=120\).
Komentár
Úloha precvičuje dôkaz všeobecného tvrdenia a opäť prináša protipríklad ako dostatočný argument.Úloha 61-I-3-N4, resp. 50-II-1
Riešenie*
\(d\) | \(u+1\) | \(v+1\) | \(u\) | \(v\) | \(a\) | \(b\) |
---|---|---|---|---|---|---|
1 | 2 | 25 | 1 | 24 | 1 | 24 |
1 | 5 | 10 | 4 | 9 | 4 | 9 |
2 | 5 | 5 | 4 | 4 | 8 | 8 |
5 | 2 | 5 | 1 | 4 | 5 | 20 |
V prípade \(d=2\) dostaneme \(u=v=4\), to je však spor s tým, že \(u\) a \(v\) sú nesúdeliteľné. Preto má úloha práve tri riešenia.
Komentár
Úloha okrem vhodného zapísania čísel \(a\), \(b\) a \([a,b]\) vyžaduje ešte vhodnú úpravu rovnosti zo zadania, opäť tak kombinuje algebraické poznatky s poznatkami z oblasti teórie čísel.Úloha 61-S-1
Riešenie*
V prípade \(a = 2\) (vzhľadom na to, že \(b\) je nepárne) platí \[a \cdot [a, b] = 2 \cdot [2, b] = 2 \cdot 2b = 4b,\] čo znamená, že prvá rovnosť v [eq:61S1] je splnená jedine pre \(b = 45\). Vtedy \(b \cdot (a, b) = 45 \cdot (2, 45) = 45\), takže je splnená aj druhá rovnosť v [eq:61S1], a preto dvojica \(a = 2, b = 45\) je riešením úlohy.
V prípade \(a = 6\) podobne dostaneme \[a \cdot [a, b] = 6 \cdot [6, b] = 6 \cdot 2 \cdot [3, b] = 12 \cdot [3, b],\] čo znamená, že prvá rovnosť v [eq:61S1] je splnená práve vtedy, keď \([3, b] = 15\). Tomu vyhovujú jedine hodnoty \(b = 5\) a \(b = 15\). Z nich však iba hodnota \(b = 15\) spĺňa druhú rovnosť v [eq:61S1], ktorá je teraz v tvare \(b\cdot(6, b) = 45\). Druhým riešením úlohy je teda dvojica \(a = 6\), \(b = 15\), žiadne ďalšie riešenia neexistujú.
Záver. Hľadané dvojice sú dve, a to \(a = 2, b = 45\) a \(a = 6, b = 15\).
Iné riešenie*. Označme \(d = (a, b)\). Potom \(a = ud\) a \(b = vd\), pričom \(u, v\) sú nesúdeliteľné prirodzené čísla, takže \([a, b] = uvd\). Z rovností \[a \cdot [a, b] = ud \cdot uvd = u^2vd^2 \ \ \ \text{a} \ \ \ \ b \cdot (a, b) = vd \cdot d = vd^2\] vidíme, že číslo \(a \cdot [a, b]\) je \(u^2\)-násobkom čísla \(b \cdot (a, b)\), takže zadaná rovnosť množín môže byť splnená jedine tak, ako sme zapísali vzťahmi (1) v prvom riešení. Tie teraz môžeme vyjadriť rovnosťami \[u^2vd^2= 180 \ \ \ \text{a} \ \ \ \ vd^2= 45.\] Preto platí \(u^2 =180/45= 4\), čiže \(u = 2\). Z rovnosti \(vd^2 = 45 = 3^2 \cdot 5\) vyplýva, že buď \(d = 1\) (a \(v = 45\)), alebo \(d = 3\) (a \(v = 5\)). V prvom prípade \(a = ud = 2 \cdot 1 = 2\) a \(b = vd = 45 \cdot 1 = 45\), v druhom \(a = ud = 2 \cdot 3 = 6\) a \(b = vd = 5 \cdot 3 = 15\).
Poznámka. Keďže zo zadanej rovnosti okamžite vyplýva, že obe čísla \(a, b\) sú deliteľmi čísla 180 (takým deliteľom je dokonca aj ich najmenší spoločný násobok \([a, b]\)), je možné úlohu vyriešiť rôznymi inými cestami, založenými na testovaní konečného počtu dvojíc konkrétnych čísel \(a\) a \(b\). Takýto postup urýchlime, keď vopred zistíme niektoré nutné podmienky, ktoré musia čísla \(a, b\) spĺňať. Napríklad spresnenie rovnosti množín na dvojicu rovností (1) možno (aj bez použitia úvahy o parite čísel \(a, b\)) vysvetliť všeobecným postrehom: súčin \(a \cdot [a, b]\) je vždy deliteľný súčinom \(b \cdot (a, b)\), pretože ich podiel možno zapísať v tvare \[\frac{a \cdot [a, b]}{b \cdot (a, b)}=\frac{a}{(a, b)}\cdot\frac{[a, b]}{b},\] teda ako súčin dvoch celých čísel.
Komentár
Úloha je zložitejšia ako predchádzajúce, dá sa však riešiť mnohými spôsobmi a bude iste zaujímavé vidieť rôzne študentské riešenia. Je taktiež vhodným miestom na to, aby sme študentov nechali diskutovať o prístupoch medzi sebou a prípadne skúšali hľadať slabiny jednotlivých zdôvodnení. Určite považujeme za vhodné zmieniť poslednú rovnosť z poznámky, keďže ide o zaujímavý postreh a metóda vhodného zapísania tvaru zlomku je užitočná nielen tu. Na túto úlohu nadväzuje komplexnejšia domáca práca, ktorá však vychádza z veľmi podobného princípu.Úloha 64-I-5
Riešenie*
a) \(u = 2 014\) a \(v = 1\): \(u - v~= 2 013\) nedelí 2 010;
b) \(u = 19 \cdot 53 = 1 007\) a \(v = 2\): \(u - v~= 1 005 \mid 2 010\), \(d = 2\), \(a = 1 007 \cdot 2 = 2 014\), \(b = 2 \cdot 2 = 4\);
c) \(u = 2 \cdot 53 = 106\) a \(v = 19\): \(u - v~= 87\) nedelí 2 010;
d) \(u = 53\) a \(v = 2 \cdot 19 = 38\): \(u - v= 15 \mid 2010\), \(d = 134\), \(a = 53 \cdot 134 = 7 102\), \(b = 38 \cdot 134 = 5 092\).
Záver. Hľadané čísla tvoria jednu z dvojíc \((2014, 4)\) alebo \((7 102, 5 092)\).
Komentár
Úloha neprináša žiadne nové poznatky a princípy, je však vhodná na trénovanie riešenia sústavy dvoch rovníc s dvomi neznámymi a opäť tak vytvorí prepojenie s minulými seminármi.Úloha 60-I-5-D3
Riešenie*
Komentár
Úloha je zaujímavá tým, že prácu s najväčším spoločným deliteľom obsahuje nepriamo a využíva tiež poznatky o deliteľnosti z minulého seminára.Úloha 60-I-5
Riešenie*
Iné riešenie*. Označme \(d = (a, b)\), takže \(a = ud\) a \(b = vd\) pre nesúdeliteľné prirodzené čísla \(u, v\). Z toho hneď vieme, že \([a, b] = uvd\). Keďže \[\begin{aligned} a \cdot (a, b) + b \cdot [a, b]& = ud^2+ uv^2d^2= u(1 + v^2)d^2,\\ 2ab& = 2uvd^2,\end{aligned}\] je vzhľadom na \(ud^2 > 0\) nerovnosť zo zadania ekvivalentná s nerovnosťou \(1 + v^2 \geq 2v\), čiže \((v - 1)^2 \geq 0\), čo platí pre každé \(v\). Rovnosť nastane práve vtedy, keď \(v = 1\), čiže \(b \mid a\).
Iné riešenie*. Označme \(d = (a, b)\). Je známe, že \([a, b] \cdot (a, b) = ab\). Po vyjadrení \([a, b]\) z tohto vzťahu, dosadení do zadanej nerovnosti a ekvivalentnej úprave dostaneme ekvivalentnú nerovnosť \(d^2 + b^2 \geq 2bd\), ktorá platí, lebo \((d - b)^2 \geq 0\). Rovnosť nastáva pre \(d = b\), čiže v prípade \(b \mid a\).
Komentár
Na úspešné zvládnutie úlohy je opäť potrebná znalosť z predchádzajúceho seminára o nerovnostiach a taktiež ponúka široké spektrum prístupov, takže bude zaujímavé sledovať, ako k nej študenti pristúpia.Domáca práca
Úloha 61-I-3
Riešenie*
Podľa uvedených zistení môžeme čísla \(a, b, c\) usporiadať tak, že rozklady čísel \(a, b\) obsahujú po jednom exemplári prvočísla 5 (potom \((c, 5) = 1\)) a že \((a, 2) = 2\) (ako vieme, aspoň jedno z čísel \(a, b\) musí byť párne). Číslo 5 z množiny \(M\) je potom nutne rovné \((a, b)\), takže platí \((b, 2) = 1\), a preto \((b, 3) = 3\) (inak by platilo \((b, c) = 1\)), odtiaľ zase s ohľadom na \((a, b) = 5\) vyplýva \((a, 3) = 1\). Máme teda \(a = 5 \cdot 2^s\) a \(b = 5 \cdot 3^t\) pre vhodné prirodzené čísla \(s\) a \(t\).
Z rovnosti \([a, b] = 2^s \cdot 3^t \cdot 5\) vyplýva, že nastane jeden z troch nasledujúcich prípadov.
(1) \(2^s \cdot 3^t \cdot 5 = 60 = 2^2 \cdot 3^1 \cdot 5\). Vidíme, že platí \(s = 2\) a \(t = 1\), čiže \(a = 20\) a \(b = 15.\) Ľahko určíme, že tretím číslom je \(c = 18\).
(2) \(2^s \cdot 3^t \cdot 5 = 90 = 2^1 \cdot 3^2 \cdot 5\). V tomto prípade \(a = 10\), \(b = 45\) a \(c = 12\).
(3) \(2^s \cdot 3^t \cdot 5 = 180 = 2^2 \cdot 3^2 \cdot 5\). Teraz \(a = 20\), \(b = 45\) a \(c = 6\).
Záver. Hľadané čísla \(a, b, c\) tvoria jednu z množín \(\{20, 15, 18\}\), \(\{10, 45, 12\}\) a \(\{20, 45, 6\}\).
Iné riešenie*. V danej rovnosti je množina napravo tvorená šiestimi rôznymi číslami väčšími ako 1, takže čísla \((a, b), (a, c), (b, c)\) musia byť netriviálnymi deliteľmi postupne čísel \([a, b], [a, c], [b, c]\). Čísla 2, 3, 5 ale žiadne netriviálne delitele nemajú, musí teda platiť \[\{(a, b), (a, c), (b, c)\}= \{2, 3, 5\} \ \ \ \text{a} \ \ \ \{[a, b], [a, c], [b, c]\} = \{60, 90, 180\}.\] Pretože poradie čísel \(a, b, c\) nehrá žiadnu úlohu, môžeme predpokladať, že platí \((a, b) = 2, (a, c) = 3\) a \((b, c) = 5\). Odtiaľ vyplývajú vyjadrenia \[a = 2 \cdot 3 \cdot x = 6x, \ \ \ b = 2 \cdot 5 \cdot y = 10y, \ \ \ c = 3 \cdot 5 \cdot z~= 15z\] pre vhodné prirodzené čísla \(x, y, z\). Zo známej rovnosti \([x, y]\cdot(x, y) = xy\) tak dostaneme vyjadrenia najmenších spoločných násobkov v tvare \[[a, b] =\frac{6x \cdot 10y}{2}= 30xy, \ \ \ [a, c] =\frac{6x \cdot 15z}{3}= 30xz,\ \ \ [b, c] =\frac{10y \cdot 15z}{5}= 30yz.\] Z rovnosti \(\{30xy, 30xz, 30yz\} = \{60, 90, 180\}\) upravenej na \(\{xy, xz, yz\} = \{2, 3, 6\}\) potom vďaka tomu, že 2 a 3 sú prvočísla, vyplýva \(\{x, y, z\} = \{1, 2, 3\}\). Pretože z podmienky \(5 = (b, c) = (10y, 15z)\) vyplýva \(y \neq 3\) a \(z \neq 2\), prichádzajú do úvahy len trojice \((x, y, z)\) rovné (1, 2, 3), (2, 1, 3) a (3, 2, 1), ktorým postupne zodpovedajú trojice \((a, b, c)\) rovné (6, 20, 45), (12, 10, 45), (18, 20, 15). Skúškou sa presvedčíme, že všetky tri vyhovujú množinovej rovnosti zo zadania úlohy.
Úloha 63-S-2
Riešenie*
Ak zvolíme napríklad \(a = 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720\) a \(b = 1 \cdot 7 \cdot 8 \cdot 9 \cdot 10 = 5040\), bude najmenší spoločný násobok oboch čísel práve \(5040\). Tým je ukázané, že \(5040\) je naozaj najmenšia zo všetkých možných hodnôt \(n\).
I keď bolo úlohou nájsť iba jeden príklad, pre úplnosť uvedieme všetky rozdelenia s minimálnou hodnotou \(n = 5040\):
Prvá skupina čísel | Druhá skupina čísel |
---|---|
2, 3, 4, 5, 6 | 1, 7, 8, 9, 10 |
3, 5, 6, 8 | 1, 2, 4, 7, 9, 10 |
2, 5, 8, 9 | 1, 3, 4, 6, 7, 10 |
1, 2, 3, 4, 5, 6 | 7, 8, 9, 10 |
1, 3, 5, 6, 8 | 2, 4, 7, 9, 10 |
1, 2, 5, 8, 9 | 3, 4, 6, 7, 10 |
2, 3, 4, 5, 6, 7 | 1, 8, 9, 10 |
3, 5, 6, 7, 8 | 1, 2, 4, 9, 10 |
2, 5, 7, 8, 9 | 1, 3, 4, 6, 10 |
1, 2, 3, 4, 5, 6, 7 | 8, 9, 10 |
1, 3, 5, 6, 7, 8 | 2, 4, 9, 10 |
1, 2, 5, 7, 8, 9 | 3, 4, 6, 10 |
Nájsť ich nie je ťažké, keď si uvedomíme, že čísla 1 a 7 môžeme dať do ľubovoľnej z oboch skupín, zatiaľ čo v tej istej skupine spolu nemôžu byť 4 s 8, 5 s 10, 3 s 9 ani 6 s 9; s 8 spolu môže byť práve jedno z párnych čísel 2, 6 a 10. Získame tak iba tri základné rozdelenia (prvé tri riadky tabuľky), z ktorých možno každé štyrmi spôsobmi doplniť číslami 1 a 7.
Poznámka. Úlohu možno vyriešiť aj bez výpočtu súčinu \(a \cdot b\). Deliteľnosť \(n\) číslami \(3^2, 5\) a 7 vyplýva z ich priameho zastúpenia medzi rozdeľovanými číslami, deliteľnosť číslom \(2^4\) z jednoduchej úvahy o rozdelení všetkých piatich párnych čísel: ak nie je číslo 8 vo svojej skupine ako párne jediné, je všetko jasné, v opačnom prípade sú v rovnakej skupine čísla 2, 4 a 6 (aj 10, ale to už ani nepotrebujeme).
Doplňujúce zdroje a materiály
Materiály vhodné na ďalšie počítanie nájdeme v minulom seminári. Keďže témy sú si veľmi blízke, publikácie zvyčajne obsahujú úlohy zamerané na obe témy.