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:
- Jako triviální dělitele a ∈ Z označujeme čísla 1 a číslo a samotné
- Celé číslo c je společným dělitelem celých čísel a a b jestliže c|a a zároveň c|b
- Prvočíslo je číslo ≥ 2, které nemá jiné dělitele než triviální
- Číslo, které není prvočíslem, nazýváme číslem složeným
- 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.
2394/2 = 1197 - číslem 2 již nelze dělit, zkusíme dále dělení číslem 3
1179/3 = 399
399/3 = 133 - číslem 3 již nelze dělit, číslem 5 také ne, zkusíme dělení číslem 7
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í:
- d je společný dělitel celých čísel a a b.
- 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í:
- a|d a zároveň b|d.
- 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.