Dělitelnost

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
Pro  definujeme relaci dělitelnosti jako  Podle konvence se někdy přidává předpoklad , ale obvykle není  nutný.

Obecně 
 Čí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.
 Pokud b je dělitelné a, píše se a|b (a dělí b)

Vlastnosti dělitelnosti 
Pro všechna  platí:
  (reflexivita)
  (tranzitivita)
  (antisymetrie)
  (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 
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 
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í p ≤ k · p ≤ ,
p · k = a ≤

Prvočinitel 
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 
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.

Obecné kritérium dělitelnosti 
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 + 5a7 − a8 + 7a9 + 2a10 + 3a11 − 4a12 − 6a13
+ 8a14 − 5a15 + a16 + … je dělitelné 17.

Externí odkazy 
 BAKALÁŘSKÁ PRÁCE DĚLITELNOST – modely dělitelnosti v různých soustavách a v gaussových oborech integrity

Teorie čísel
Aritmetika