Slovník | Vyhledávání | Mapa webu
 
Základy informatiky pro biologyTeoretické základy informatiky Teorie čísel Dělitelnost

Logo Matematická biologie

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 aZ 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 = p1a1* p2a2*...* pkak, kde p1, p2,..., pk jsou navzájem různá prvočísla a a1, a2,..., ak 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 = 24 * 32 * 52

4864 = 28 * 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 d1 dělí obě čísla a a b, pak d1 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|d1 a b|d1, pak d|d1 pro nějaké celé číslo d1.

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 = 22 * 31 * 52

18 = 21 * 32

NSD(300,18) = 21 * 31 * 50 = 6

NSN(300,18) = 22 * 32 * 52 = 900

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

Úlohy k procvičení

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict