Dělitelnost

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Dělitelnost je vlastnost celých čísel. Celé číslo p je dělitelné nenulovým celým číslem q (číslo q dělí p), jestliže existuje takové celé číslo k, pro které platí, že

p = kq.

Např. číslo 27 je dělitelné třemi, neboť 27 = 9 · 3. Alternativně je p dělitelné q, jestliže zbytek po dělení p/q je nula.

Obecně[editovat | editovat zdroj]

  • Číslo p se nazývá dělenec,
  • číslo q se nazývá dělitel,
  • číslo k se nazývá podíl čísla p při dělení číslem q,
  • 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 nuly je dělitelem nuly, nula ale není dělitelem žádného celého čísla různého od nuly.
  • Pokud b je dělitelné a, píše se a|b (a dělí b)

Vlastnosti dělitelnosti[editovat | editovat zdroj]

  •  a|b \implies \forall k \in \mathbb{Z} a|k \cdot b (Když a dělí b,tak a dělí jakýkoli násobek b)
  •  a|b \and b|c \implies a|c (Pokud a dělí b a b dělí c,tak a dělí c.) Tato vlastnost je ekvivalentní té první.
  • a|b \and a|c \implies a|(b+c)(Když a dělí dvě čísla,tak a dělí i jejich součet.

Sudá a lichá čísla[editovat | editovat zdroj]

Celé číslo dělitelné dvěma se nazývá sudé. Pokud číslo není sudé, nazývá se liché.

Prvočísla[editovat | editovat zdroj]

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 | editovat zdroj]

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 p \leq \sqrt{a}.

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 p \leq \sqrt{a}.

Nechť a = p · k ( k\mathbb{N}). Platí pk · pk^2, p · k = ak^2

p\leq \sqrt{a} \leq k

Prvočinitel[editovat | editovat zdroj]

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 | editovat zdroj]

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
2 je-li na místě jednotek sudé číslo 128, 1 002
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 008
5 je-li na místě jednotek 5 nebo 0 35, 10 540
6 je-li číslo dělitelné 2 a 3 924, 29 250
7 je-li rozdíl součtu lichých a sudých trojic cifer dělitelný 7
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
je-li rozdíl zbývající části a posledního čísla vynásobeného dvakrát dělitelný 7
2 022 048 (002-022+048 = 28)
138 309 241 : 1×1+4×3+2×2+9×6+0×4+3×5+8×1+3×3+1×2=105 (1×5+3×0+2×1=7, číslo dělitelné 7), 138 309 241 je tedy dělitelné 7.
1 946; 194 - 2×6 = 194 - 12 = 182; 18 - 2×2 = 18 - 4 = 14
8 je-li poslední trojčíslí dělitelné 8 12 504.
9 je-li ciferný součet dělitelný 9 1 683 (1+6+8+3=18, 1+8=9)
10 je-li na místě jednotek 0 1 220, 2 180
11 je-li rozdíl součtu číslic na sudém a lichém místě dělitelný jedenácti,
je-li součet jednotlivých dvojčíslí dělitelný 11,
je-li rozdíl trojčíslí na sudých a lichých místech dělitelný 11
5 357 ((-5 +3 -5 +7)=0)
5 357 ((53 + 57)= 110)
5 357 ((-5 + 357)= 352)
12 je-li číslo dělitelné 3 a 4 65 412 (6+5+4+1+2=18 → dělitelné 3 → OK); 65 412 (12/4=3 → OK)
13 je-li rozdíl součtů lichých a sudých trojic cifer dělitelný třinácti 2 022 046 ((2 + 46) - 22 = 26 → dělitelné 13 → OK)
14 je-li číslo dělitelné 2 a 7 868, 5 964
15 je-li číslo dělitelné 3 a 5 930, 1 170
16 je-li poslední čtyřčíslí dělitelné 16 1 456, 1 552
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.
je-li sedmnácti dělitelné číslo, vzniklé odečtením pětinásobku poslední cifry od čísla zapsaného zbylými ciframi
51 153 ((53-(2×11))/2 + 2×5 = 25,5 a 255 je dělitelné 17)

867 = 86-(5×7) = 51 je dělitelné 17
18 je-li číslo dělitelné 2 a 9 1 134, 162
19 je-li součet počtu desítek s dvojnásobkem jednotek dělitelný 19 10 735 → 1 073+2x5=1 083 → 108+2x3=114 → 11+2x4=19
20 je-li číslo dělitelné 4 a 5, je-li poslední dvojčíslí dělitelné 20 1 680, 5 142 800
25 je-li poslední dvojčíslí 00 nebo dělitelné 25 125, 15 475
30 je-li číslo dělitelné 3 a 10 4 590 , 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 jsou-li poslední dvě číslice 0 15 400, 700
1000 jsou-li poslední tři číslice 0 154 000, 7 000

Obecné kritérium dělitelnosti[editovat | editovat zdroj]

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í \alpha_k \equiv 10^k\,(mod\ n). Ř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.

Reference[editovat | editovat zdroj]