Dělitelnost

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 = k*q. Např. číslo 27 je dělitelné třemi, neboť 27 = 9 * 3. Číslo q se nazývá dělitel čísla p, zapisujeme q|p (p dělí q). Alternativně můžeme říci, že je p dělitelné q, jestliže zbytek po dělení p/q je nula. Následující seznam představuje další známé pojmy a fakta:

1. Jako triviální dělitele a ∈ Z označujeme čísla 1 a číslo a samotné
2. Celé číslo c je společným dělitelem celých čísel a a b jestliže c|a a zároveň c|b
3. Prvočíslo je číslo ≥ 2, které nemá jiné dělitele než triviální
4. Číslo, které není prvočíslem, nazýváme číslem složeným
5. Každé celé číslo ≥ 2 je buď prvočíslo, nebo se dá zapsat jako součin prvočísel

Definice 1.2: Jestliže a,b ∈ Z a b ≥ 1, pak dělení čísla a číslem b dává čísla q (podíl) a r (zbytek) taková, že a = q*b + r, kde 0 ≤  r < b. Čísla q a r jsou jednoznačná. Zbytek po dělení budeme značit také a (mod b).

Definice 1.3: Každé celé číslo n ≥ 2 se dá zapsat jednoznačně (až na pořadí) v kanonickém tvaru n = p₁^a1* p₂^a2*...* p_k^ak, kde p_1, p_2,..., p_k jsou navzájem různá prvočísla a a₁, a₂,..., a_k jsou celá kladná čísla.

Příklad: Vyjádřete v kanonickém tvaru číslo 2394.

Řešení

1. 2394/2 = 1197 - číslem 2 již nelze dělit, zkusíme dále dělení číslem 3

2. 1179/3 = 399

3. 399/3 = 133 - číslem 3 již nelze dělit, číslem 5 také ne, zkusíme dělení číslem 7

4. 133/7 = 19 - číslo 19 je již prvočíslo, výsledek tedy bude 2394 = 2*3*3*7*19

Příklady na procvičení:

3600 = 2⁴ * 3² * 5²

4864 = 2⁸ * 19

3458 = 2 * 7 * 13 * 19

Definice 1.4: Kladné celé číslo d je největším společným dělitelem (dále jen NSD, anglicky GCD - greatest common divisor) celých čísel a a b, když platí:

1. d je společný dělitel celých čísel a a b.
2. Jestliže nějaké celé číslo d₁ dělí obě čísla a a b, pak d₁ dělí také d.

Euklidův algoritmus slouží k nalezení NSD dvou čísel.

function nsd(a, b) {

  var c;

  while (b != 0) {

    c = b;

    b = a mod b;

    a = c;

  }

  return a;

}

Příklad: Ukázka výpočtu Euklidova algoritmu pro čísla 72 a 246:

1. 246 = 3 * 72 + 30	(246 mod 72 = 30)
2. 72 = 2 * 30 + 12	(72 mod 30 = 12)
3. 30 = 2 * 12 + 6	(30 mod 12 = 6)
4. 12 = 2 * 6 + 0	NSD (72,246) = 6

Příklad: Společní dělitelé čísel 12 a 18 jsou {1,2,3,6}. NSD(12,18) = 6

Definice 1.5: Kladné celé číslo d je nejmenším společným násobkem (dále jen NSN, anglicky LCM - least common multiple) celých čísel a a b, když platí:

1. a|d a zároveň b|d.
2. Jestliže a|d₁ a b|d₁, pak d|d₁ pro nějaké celé číslo d₁.

Příklad: Jestliže a a b jsou kladná celá čísla, pak NSN(a,b) = a*b / NSD(a,b).
Např.: NSN(12,18) = 12*18/NSD(12,18) = 12*3 = 36.

Příklad: Je snadné nalézt NSD a NSN dvou celých čísel ≥ 2, pokud je vyjádříme v kanonickém tvaru:

300 = 2² * 3¹ * 5²

18 = 2¹ * 3²

NSD(300,18) = 2¹ * 3¹ * 5⁰ = 6

NSN(300,18) = 2² * 3² * 5² = 900

Definice 1.6: Dvě celá čísla jsou nesoudělná (relatively prime), když jejich NSD je 1.

Úlohy k procvičení