Dělitelnost

celé číslo, které dané celé číslo dělí beze zbytku

Dělitelnost je vlastnost dvojic celých čísel. Celé číslo p je dělitelné nenulovým celým číslem q (číslo q dělí p) právě tehdy, když p je celočíselným násobkem q, tj. jestliže existuje takové celé číslo k, pro které platí, že

p = kq.

Tato relace se obvykle značí . Např. číslo 27 je dělitelné třemi, neboť 27 = 9 · 3. Jiná definice: p je dělitelné q, jestliže zbytek po dělení je nula.

Formální definice

editovat

Pro   definujeme relaci dělitelnosti jako   Podle konvence se někdy přidává předpoklad  , ale obvykle není nutný.

Obecně

editovat
  • Číslo p se nazývá dělenec,
  • číslo q se nazývá dělitel,
  • číslo k se nazývá podílem čísla p při dělení číslem q, (jednoznačně určen s výjimkou pro p=0)
  • v oboru celých čísel mají čísla p a −p tytéž dělitele,
  • čísla 1, −1, p a −p se nazývají nevlastní (triviální) dělitelé čísel p a −p,
  • existují-li ještě další dělitelé, nazývají se vlastní dělitelé (netriviální),
  • každé celé číslo mimo nulu je dělitelem nuly, nula ale není dělitelem žádného celého čísla různého od nuly.

Vlastnosti dělitelnosti

editovat

Pro všechna   platí:

  •   (reflexivita)
  •   (tranzitivita)
  •   (Jestliže a dělí b, tak a dělí jakýkoli násobek b.)
  •   (Když a dělí dvě čísla, tak a dělí i jejich součet.)

Prvočísla

editovat

Přirozené číslo větší než 1, které je dělitelné pouze číslem 1 a samo sebou, se nazývá prvočíslo. Přirozené číslo větší než 1, které není prvočíslem, se nazývá složené číslo.

Dělitelnost prvočíslem

editovat

Pro každé přirozené číslo a větší jedné existuje alespoň jedno prvočíslo p, které dělí a. Pokud navíc a je složené, tak  .

Důkaz je následovný:

Množina dělitelů a bez 1 je konečná, nechť tedy p je její minimum. Pokud a je prvočíslo, tak a = p, tím pádem existuje prvočíslo, které dělí a.

Pokud a je složené, tak p je prvočíslo. Tento fakt lze dokázat sporem. Předpokládejme, že p není prvočíslo. Potom p = q · r (1 < q < p < a). Ovšem pokud p dělí a a q dělí p, tak q dělí a. Avšak 1 < q < p, což odporuje faktu, že p je nejmenší dělitel a větší jedné. Z toho vyplývá, že p je prvočíslo.

Zbývá dokázat, že  .

Nechť a = p · k ( k ). Platí pk · p , p · k = a 

 

Prvočinitel

editovat

Prvočíslo, které dělí číslo p, se nazývá prvočinitel. Každé složené číslo lze napsat jako součin prvočinitelů. Tento zápis (pokud nebereme v úvahu pořadí prvočinitelů) je pro každé číslo jedinečný (viz faktorizace).

Každé prvočíslo s výjimkou čísla 1 má jen 2 dělitele; sebe samo a 1. Číslo 1 má jen sebe samo a tudíž má exkluzivní postavení, není ani prvočíslem ani číslem složeným.

Dvě čísla se nazývají soudělná, když mají společného dělitele většího než 1. Pokud takového dělitele nemají, pak se nazývají nesoudělná.

Kritéria dělitelnosti

editovat

Následující tabulka obsahuje kritéria dělitelnosti celých čísel v desítkové číselné soustavě, která umožňují snadno zjistit, je-li celé číslo dělitelné malým číslem q. Pokud je kritériem dělitelnost výsledku nějakého postupu, lze na něj opět použít stejný postup.

q kritérium příklad
0 dělení nulou není v celých číslech definováno
1 všechna celá čísla jsou dělitelná 1 1, 6, 329
2 je-li na místě jednotek sudé číslo 128, 1 102
3 je-li ciferný součet dělitelný 3 228 → 2+2+8 = 12 → 1+2 = 3
4 je-li poslední dvojčíslí dělitelné 4 612, 1 108
5 je-li na místě jednotek 5 nebo 0 35, 10 040
6 je-li číslo dělitelné 2 a 3 (viz výše) 924, 29 952
7 je-li rozdíl součtu lichých a sudých trojic cifer dělitelný 7 2 022 048 → 002-022+048 = 28
je-li sedmi dělitelný součet vypočtený tak, že se první až n-tá číslice odzadu vynásobí postupně čísly (periodicky se opakujícími): 1, 3, 2, 6, 4, 5 138 309 241 → 1×1+4×3+2×2+9×6+0×4+3×5+8×1+3×3+1×2=105 → 5×1+0×3+1×2=7
je-li rozdíl zbývající části a poslední číslice vynásobené 2 dělitelný 7 1 946 → 194 − (2×6) = 182 → 18 − (2×2) = 14
je-li součet zbývající části a poslední číslice vynásobené 5 dělitelný 7 1 946 → 194 + (5×6) = 224 → 22 + (5×4) = 42
je-li po opakovaném odečítání z čísla násobků 7 končících na stejnou cifru (mohou být jakékoliv) a následném dělení čísla deseti výsledek nula (když číslo není dělitelné 7, výsledek přejde do záporných čísel) 7 436 429 − 49 = 7 436 380 / : 10
743 638 − 28 = 743 610 / : 10
74 361 − 91 = 74 270 / : 10
7 4277 = 7 420 / : 10
742 − 42 = 700 / : 10
70 - 70 = 0
8 je-li poslední trojčíslí dělitelné 8 12 504
je-li poslední dvojčíslí dělitelné 8 a na místě stovek je sudé číslo 208, 123 672
je-li poslední dvojčíslí zvětšené (či zmenšené) o 4 dělitelné 8 a na místě stovek je liché číslo 104, 234 760
9 je-li ciferný součet dělitelný 9 1 683 → 1+6+8+3=18 → 1+8 = 9 → OK
10 je-li na místě jednotek 0 1 120, 2 280
11 je-li rozdíl součtu číslic na sudém a lichém místě dělitelný jedenácti 5 357 → −5 +3 −5 +7 = 0 → OK
je-li součet jednotlivých dvojčíslí dělitelný 11 5 357 → 53 + 57= 110 OK
je-li rozdíl trojčíslí na sudých a lichých místech dělitelný 11 5 357 → −5 + 357 = 352
12 je-li číslo dělitelné 3 a 4 (viz výše) 65 520 → 6+5+5+2+0=18 → dělitelné 3 → OK; 65 520 → 20/4=5 → OK
13 je-li rozdíl součtů lichých a sudých trojic cifer dělitelný třinácti 2 022046 2 + 46 − 22 = 26 → dělitelné 13 → OK
14 je-li číslo dělitelné 2 a 7 (viz výše) 868, 5 564
15 je-li číslo dělitelné 3 a 5 (viz výše) 930, 1 170
16 je-li poslední čtyřčíslí dělitelné 16 736, 1 156, 21 152
je-li součet čtyřnásobku zbývající části a posledního dvojčíslí dělitelný 16 11 312 → (4×113) + 12 = 464 → (4×4) + 64 = 80
17 je-li výsledek následujícího postupu dělitelný sedmnácti: střídavě se odečítají a přičítají dvojice cifer vynásobené 2 a mezivýsledky se vždy dělí dvěma. Konečný výsledek se pak vynásobí násobkem deseti tak, aby vyšlo celé číslo. 51 153 → ((53−(2×11))/2 + 2×5 = 25,5 a 255 je dělitelné 17)
je-li rozdíl zbývající části a pětinásobku poslední číslice dělitelný 17 867 → 86 − (5×7) = 51 je dělitelné 17
18 je-li číslo dělitelné 2 a 9 (viz výše) 1 134, 162
19 je-li součet zbývající části a dvojnásobku poslední číslice dělitelný 19 10 735 → 1 073+(2×5) = 1 083 → 108+(2×3) =114 → 11+(2×4) = 19
20 je-li číslo dělitelné 4 a 5 (viz výše)
je-li poslední dvojčíslí dělitelné 20 1 180, 5 542 200
21 je-li číslo dělitelné 3 a 7 (viz výše)
je-li rozdíl zbývající části a dvojnásobku poslední číslice dělitelný 21 273 → 27 − (2×3) = 21
22 je-li číslo dělitelné 2 a 11 (viz výše) 396, 1 474
23 je-li součet zbývající části a sedminásobku poslední číslice dělitelný 23 3128 → 312+(7×8) = 368 → 36+(7×8) = 92
je-li součet zbývající části a trojnásobku posledních 2 číslice dělitelný 23 1725 → 17+(3×25) = 92
24 je-li číslo dělitelné 3 a 8 (viz výše) 456, 1 656
25 je-li poslední dvojčíslí 00 nebo dělitelné 25 – tedy 25, 50 nebo 75 125, 15 575
30 je-li číslo dělitelné 3 a 10 (viz výše) 4 490, 631 110
40 je-li poslední trojčíslí 000 nebo dělitelné 40 5 200, 6 840
50 je-li poslední dvojčíslí 00 nebo 50 550, 700
100 je-li poslední dvojčíslí 00 15 500, 700
1000 je-li poslední trojčíslí 000 154 000, 7 000
10 000 je-li poslední čtyřčíslí 0000 154 0000, 7 0000

Obecné kritérium dělitelnosti

editovat

Libovolné kritérium dělitelnosti lze zapsat jako ciferný součet s vahami – číslo x je dělitelné prvočíslem n právě když Σk αkak je dělitelné n, kde x = a0 + 10a1 + 100a2 + 1000a3 + … + 10nan, neboli je zapsáno v poziční soustavě se základem 10.

Jednotlivé váhy v ciferném součtu jsou řešení jednoduchých kongruencí  . Řešení jsou tedy zbytky po dělení 10k/n.

Například číslo x je dělitelné 17 právě když a0 − 7a1 − 2a2 − 3a3 + 4a4 + 6a5 − 8a6 + 5a7a8 + 7a9 + 2a10 + 3a11 − 4a12 − 6a13 + 8a14 − 5a15 + a16 + … je dělitelné 17.

Externí odkazy

editovat