Def. 2 Přirozené číslo p>l nazýváme prvočíslem, pravé když má právě dva přirozené dělitele. Přirozené číslo a>l, které není prvočíslem (tj. má více než dva přirozené dělitele), nazýváme složeným číslem.
O tom, zda dané číslo je prvočíslo nebo složené číslo, můžeme rozhodnout pomocí tzv. Eratosthenova síta nebo podle věty 3.
Věta 3. Jestliže přirozené číslo a není dělitelné žádným prvočíslem menším nebo rovným ■Ja , pak a je prvočíslo.
Pf. Zjistěte, zda 173 jc prvočíslo nebo složené číslo.
fT73< 14, proto budeme zjišťovat, zda číslo 173 je dělitelné některým z prvočísel 2, 3, 5, 7, 11, 13. Číslo 173 není dělitelné žádným z těchto prvočísel, proto je prvočíslem.
Věta 4. Každé složené číslo a lze vyjádřit právě jedním způsobem ve tvaru součinu konečného počtu prvočísel
a=P;-.p^.... .P;<
kde pi, P2......, Pk jsou prvočísla,     ei, e2,...,    jsou nenulová přirozená čísla.
Tento zápis se nazývá prvočíselný rozklad přirozeného čísla a a pi, pí,......Pk jsou tzv.
prvočinitele rozkladu.
Pí.  600 = 23.3'.5!
Def. 3 Společný dělitel přirozených čísel a, b je každé přirozené číslo d, pro které platí d a a d b.
Def. 4 Největší společný dělitel přirozených čísel a, b je ten ze společných dělitelů, který je dělitelný všemi společnými děliteli. Označujeme D(a,b).
Pozn. V množině přirozených čísel lze též říci, že největší společný dělitel je největší (maximální) číslo ze společných dělitelů.
Def. 5 Přirozená čísla a, b se nazývají nesoudělná, právě když je jejich největší společný dělitel roven 1.     D(a,b) = l
Def. 6 Přirozená čísla a, b se nazývají soudělná, právě když je jejich největší společný dělitel větší než 1. D(a,b)>l.
Def. 7 Společný násobek přirozených čísel a, b je každé přirozené číslo m, které je dělitelné oběma čísly a, b, tj. a m a b m.
Def. 8 Nejmenší společný násobek přirozených čísel a, b je ten ze společných násobků, který je dělitelem všech společných násobků čísel a, b. Označujeme n(a,b). Pozn. V množine přirozených čísel lze těž říci, že n(a,b) je nejmenší číslo z kladných společných násobků čísel a,b.
Pozn. Definice 3 - 8 lze rozšířit na libovolný konečný počet přirozených čísel ai, a„.
Určování D(a,b) a n(a,b)
1) pomocí Euklidova algoritmu
2) z rozkladů čísel na součin prvočinitelů
ad 1) Euklidův algoritmus vychází z věty 7.1 (uč. na str. 189).
Podle této věty platí: Jestliže přirozené číslo a dává při dělení nenulovým přirozeným číslem b zbytek z, tj. a = b.q + z a z < b, pak největší společný dělitel čísel a, b je roven nej většímu společnému děliteli čísel b, z, tj. D(a,b) = D(b,z).
Tím převádíme problém určení D(a,b) na určení D(b,z). Čísla baz jsou menší než čísla a, b.
Př. Zjistěte D(268, 80)
268 : 80 = 3 neboli 268 - 80 . 3 + 28
28
80:28=2 80 = 28.2 + 24
24
28 : 24 - 1 28 - 24. 1 + 4
4
24 : 4 = 6 24 = 6 . 4
0
Největší společný dělitel čísel 268 a 80 je číslo 4, tj. poslední nenulový zbytek při postupném dělení.
Nejmenší společný násobek čísel a, b pak lze vypočítat podle věty 8.2 v učebnici na str. 191. Věta 4: Pro každá dvě přirozená čísla a, b platí:    n(a.b). D(a,b) = a. b
ad 2) Určení největšího společného dělitele a nejmenšího společného násobku z rozkladu daných čísel na součin prvočinitelů.
Největší společný dělitel daných přirozených čísel je součinem všech prvočinitelů, kteří se současně vyskytují v prvočíselných rozkladech všech daných čísel, a to s nejmenším s vyskytujících se exponentů.
Nejmenší společný násobek daných čišel je součinem všech různých prvočinitelů, kteří se vyskytují v rozkladech daných čísel, a to v největší mocnině.
Př. Zjistěte D(108,90) a u(108,9O). 108-22. 33       90= 2.3J.5 D(108,90)= 2.32- 18 n(108,9O)= 22.33.5 = 540
Určení počtu všech přirozených dělitelů daného přirozeného čísla:
Věta 5: Je-li a = pel. pcl.....p1* prvočíselný rozklad přirozeného čísla a > 1, pak počet
všech přirozených dělitelů čísla a (ozn, 9 (a)) je určen takto: S(a) = (e, + l).(e2+l).....(ek+l)
Všechny přirozené dělitele čísla a určíme jako všechny možné součiny prvočinitelů, přičemž každý prvočinitel, probíhá všechny mocniny od 0. po tu, ve které se vyskytují v rozkladu.
		3°	3'	3J	
2°	.5°	1	3	9	90 = 2 . 32. 5
2°	51	5	15	45	
2'	5"	2	6	18	9 (90) = (1+1)
2'	5'	10	30	90