MA0002 — řešení DU č. 6
Cvičení 6.1 Najděte prvočíselný rozklad čísla:
(a) 210 = 2 • 3 • 5 • 7 (e) 3575 = 52 • 11 • 13
(b) 143 = 11 • 13 (f) 3705 = 3-5-13-19
(c) 247 = 13-19 (g) 3 925 = 52 • 147 fdj 1001 = 7 ■ 11 ■ 13 (h) 10127 = 13 ■ 19 ■ 41
Cvičení 6.2 Najděte největší společný dělitel a nejmenší společný násobek čísel:
(a) 240 a 264 (c) 391 a 10127
(b) 51 a 81 (d) 437 a 247
Řešení:
Každé z čísel si rozložíme na prvočísla a následně určíme NSD a nsn. 240 = 23 • 3 • 5        NSD(240; 264) = 23 • 3 = 24
(a)
(b)
(c)
(d)
264 = 23 • 3 • 11      nsn(240; 264) = 23 ■ 3 • 5 ■ 11 = 2640
51 = 3-17      iV5D(51;81) =3
81 = 34 nsn(51; 81) = 34 • 17 = 1377
391 = 17-23 iVS,£>(391;10127) = 1
10127 =13-19-41      nsn(391; 10127) = 13 • 17 ■ 19 • 23 ■ 41 = 3 959 657
437 = 19-23      NSD(437; 247) = 19
247 = 13-19      nsn(437; 247) = 13 • 19 • 23 = 5 681
Cvičení 6.3 Určete součet všech kladných dělitelů čísla s výjimkou čísla samotného:
(a) 10 (e) 18
(b) 14
(f) 21
(c) 15
(d) 24 (9) 6
74
Řešení:
(a)
(b)
(c)
(d)
10
5
14
7
15
5
24 12
8
6
S=8
S=10
S=9
S=36
(e)
(f)
(g)
18 9
6
21
7
6 3
S=21
S=ll
S=6
Cvičení 6.4 Určete rozklad čísla na prvočinitele a počet všech jeho kladných dělitelů:
(a) 236
(b) 3159
(c) 1296
(d) 5400
Řešení:
(e) 10125
(f) 5! (9) 10! (h) 12!
Každé z čísel rozložíme na prvočinitele. Zřejmě každý z jeho dělitelů je složen z prvočísel obsažených v rozkladu nejvýše v mocnině, v jaké se vyskytuje v původním čísle. Pokud bude například v rozkladu čísla 23, bude se v rozkladu každého z dělitelů vyskytovat prvočíslo 2 v mocninách 0, 1, 2, nebo 3. Označme si počet dělitelů čísla n symbolem r(n) a vyjádřeme obecný vztah.
u = pT-pT
■p?
r(n) = (ai + l)(a2 + 1)... (a* + 1)
(a) 236 = 22 • 59   r(236) =3-2 = 6
(b) 3159 = 35 • 13   t(3 159) = 6 • 2 = 12
(c) 1296 = 24 - 34  r(1296) = 5-5 = 25
(d) 5400 = 23 ■ 33 ■ 52   r(5400) = 4 ■ 4 ■ 3 = 48
(e) 10125 = 34 • 53   r(10125) = 5 • 4 = 20
(f) 5! = 23 • 3 • 5   t(5!) = 4 • 2 • 2 = 16
(g) 10! = 28 ■ 34 • 52 ■ 7  r(10!) = 9 ■ 5 • 3 • 2 = 270
(h) 12! = 2*0 ■ 35 • 52 ■ 7 ■ 11   r(12!) = 11 ■ 6 ■ 3 • 2 • 2 = 792
75
Cvičení 6.5 Najděte alespoň pět přirozených čísel, která maji lichý počet dělitelů.
Řešení:
Můžeme využít znalosti ze cvičení 6.3, případně ze cvičení 6.4. Podíváme-li se ještě jednou na řešení 6.3, kde je každý z dělitelů daného čísla (včetně jeho samého a jedničky) zapsán na nějaké straně svislé čáry, vidíme, že pro lichý počet dělitelů musí být v posledním řádku dvě stejná čísla. Číslo s lichým počtem dělitelů tedy musí být čtverec nějakého přirozeného čísla.
Chceme-li využít cvičení 6.4, hledáme takové mocniny prvočísel ct\, ct2, ■. • afe, aby počet dělitelů byl lichý. Ze součinu získáme lichý výsledek právě tehdy, když jsou všechny činitele lichá čísla. Proto všechna cti, ct2,... musí být sudá (to opět znamená, že hledané číslo je čtverec).
Hledaná čísla jsou například 1, 4, 9, 16 a 25.
Cvičení 6.6 Najděte alespoň pět přirozených čísel, která mají sudý počet dělitelů.
Řešení:
Z předchozího cvičení víme, že můžeme zvolit jakákoli čísla, která nejsou druhou mocninou přirozeného čísla.
Hledaná čísla jsou například 3, 5, 8, 15 a 24.
Cvičení 6.7 Pro každá dvě přirozená čísla platí, že součin největšího společného dělitele a nejmenšího společného násobku je roven součinu těchto dvou čísel.
(a) Vysvětlete vlastními slovy, že uvedené tvrzení platí.
(b) Ukažte na konkrétním příkladě, že předchozí tvrzení nelze obecně rozšířit na trojici čísel.
Řešení:
(a) Největší společný dělitel je tvořen průnikem prvočísel obsažených v daných číslech (včetně mocnin), nejmenší společný násobek je tvořen sjednocením prvočísel obsažených v rozkladu daných čísel (ve nejvyšších mocninách). Proto je-li prvočíslo pi v rozkladu pouze prvního z čísel, objeví se v součinu NSD a nsn i v součinu daných čísel, a to ve stejné mocnině, v jaké je obsažené v prvním čísle.
Máme-li v rozkladu prvního čísla prvočíslo p^1 a v rozkladu druhého čísla prvočíslo p^2, kde cti < ct2, objeví se v součinu NSD a nsn člen £>21-22> stejně tak se ale tento člen objeví i v součinu daných čísel. Jiná možnost než dvě výše popsané nastat nemůže, proto tvrzení platí.
(b) NSD(A; 6; 8) = 2   nsn(4; 6; 8) = 24   2 ■ 24 + 4 • 6 • 8 Cvičení 6.8 (*) Najděte všechna přirozená čísla x, y, pro která platí:
nsn(x; y) = NSD(x, y) + 5
76
Řešení:
Zřejmě nemůže platit x = y, pak by bylo nsn = NSD. V dalších případech je vždy nsn > NSD, nsn je totiž NSD vynásobený nejméně jedním prvočíslem (je minimálně dvakrát větší). Proto musí být NSD < 5 a nsn(x; y) < 10, což nám ovšem velmi omezuje volbu čísel x, y.
NSD(x;y) = l nsn(x,y)=6 [x;y] € [1; 6]; [6; 1]; [2;3]; [3; 2]
NSD{x;y) = 2 nsn(x,y) = 7 nelze
NSD{x\y) = 3 nsn(x,y) — 8 nelze
NSD(x;y) = 4 nsn(x,y) = 9 nelze
NSD(x; y) = 5 nsn(x, y) = 10 [x; y] € [5; 10]; [10; 5]
Vyhovující uspořádané dvojice čísel jsou [1; 6]; [6; 1]; [2; 3]; [3; 2]; [5; 10] a [10; 5].
Cvičení 6.9 Dokažte, že pro každá dvě přirozená čísla a, b platí:
(a) NSD(a; b) = 1 =>- NSD(ab; a2 + b2) = l
(b) NSD(a; b) = 1    NSD(a + b; a2 + b2) < 2 Řešení:
(a) Jsou-li čísla a, b nesoudělná, nemají ve svých prvočíselných rozkladech žádná společná prvočísla. Proto ani výrazy a2,b2 nemají žádná společná prvočísla, z výrazu a2 + b2 nelze žádné z prvočísel vyskytujících se v prvočíselném rozkladu čísel a, b vytknout. Avšak v prvočíselném rozkladu čísla db jsou stejná prvočísla, jako v rozkladech čísel a, b, proto musí být NSD(ab; a2 + b2) = 1.
(b) Uvažujme nejprve situaci pro sudý součet a + b (to znamená, že a, b jsou obě sudá, nebo obě lichá). Potom i součet druhých mocnin a, b musí být sudý a NSD(a + b; a2 + b2) > 2. Dále si můžeme výraz a2 + b2 upravit do tvaru (a + b)2 — 2ab a protože jsou a, b nesoudělná, podobně jako v předchozí variantě dojdeme k závěru, že žádné jiné prvočíslo se v NSD neobjeví. Platí NSD(a + b; a2 + b2) = 2.
Je-li součet a + b lichý, nemůže se v NSD objevit ani prvočíslo 2, pro lichý součet a + b platí NSD(a + b; a2 + b2) = 1. Dohromady získáváme NSD{a + b;a2 + b2) < 2.
Cvičení 6.10 (*) Dokažte, že jestliže zvolíme libovolných 7 různých prvočísel, bude součin jejich kladných rozdílů dělitelný číslem 163840.
Řešení:
Nejprve si rozložme číslo 163 840 na součin prvočísel: 163 840 = 215 • 5. Kladných rozdílů dvou prvočísel bude stejně, jako dvouprvkových kombinací ze sedmi prvočísel Q =21. Rozdíl každých dvou lichých prvočísel bude sudé číslo (dělitelné dvěma). Protože však existuje pouze jedno sudé prvočíslo, může se vyskytovat nejvýše v šesti rozdílech s jiným prvočíslem. Jistě tedy
77
alespoň 15 rozdílů prvočísel bude sudých, alespoň z 15 rozdílů můžeme vytknout číslo 2 - součin rozdílů musí být dělitelný číslem 215.
Zbývá nám ověřit dělitelnost pěti. Jestliže alespoň jeden z rozdílů bude dělitelný pěti, jistě bude celý součin dělitelný pěti. Pokud ale nebude žádný z rozdílů dělitelný pěti, musí každý rozdíl dávat po dělení pěti zbytek 1,2,3, nebo 4. Protože máme k dispozici 21 rozdílů, jistě bude dávat alespoň 5 rozdílů stejný zbytek po dělení pěti. Z toho ale plyne, že právě součin těchto rozdílů je dělitelný pěti.
Dokázali jsme, že součin kladných rozdílů 7 různých prvočísel musí být dělitelný číslem 163 840.
78