Numere prime și compuse; descompunerea; c.m.m.d.c. și c.m.m.m.c.

Un număr natural mai mare decât $1$ se numește număr prim dacă are exact doi divizori naturali: $1$ și el însuși. De exemplu, $2,3,5,7,11,13,17,19,23$ sunt numere prime. Numărul $2$ este singurul număr prim par; toate celelalte numere prime sunt impare (dar nu orice număr impar este prim: $9,15,21,25$ sunt impare și, în același timp, compuse). Un număr natural mai mare decât $1$ care are mai mult de doi divizori se numește număr compus (de exemplu $4,6,8,9,10$). Numărul $1$ are un singur divizor (pe el însuși), deci nu este nici prim, nici compus.

O metodă clasică de identificare a numerelor prime dintr-un interval este ciurul lui Eratostene: se scriu toate numerele de la $2$ până la o limită dată, apoi se elimină succesiv multiplii fiecărui număr prim găsit (întâi multiplii lui $2$, apoi ai lui $3$, ai lui $5$ ș.a.m.d.); numerele rămase neeliminate sunt numere prime.

Orice număr natural mai mare decât $1$ se poate scrie, în mod unic (până la ordinea factorilor), ca produs de puteri de numere prime — aceasta se numește descompunere canonică (în factori primi): $n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$, unde sunt numere prime distincte, iar sunt numere naturale nenule. De exemplu, . Pentru descompunere folosim criteriile de divizibilitate (cu ) învățate anterior.

Cel mai mare divizor comun (c.m.m.d.c.) a două numere naturale se poate afla în două moduri:

1. Prin descompunere în factori primi: se descompun numerele, apoi c.m.m.d.c. este produsul factorilor primi comuni, luați la puterea cea mai mică.
2. Prin algoritmul lui Euclid: se împarte numărul mai mare la cel mai mic, apoi împărțitorul se împarte la restul obținut, și tot așa, succesiv, până se obține restul $0$; c.m.m.d.c. este ultimul rest nenul.

Cel mai mic multiplu comun (c.m.m.m.c.) a două numere se calculează prin descompunere în factori primi, ca fiind produsul factorilor primi comuni și necomuni, luați la puterea cea mai mare.

Între c.m.m.d.c. și c.m.m.m.c. a două numere $a$ și $b$ există relația fundamentală: $cmmdc(a,b)\cdot cmmmc(a,b)=a\cdot b$ Această relație este utilă atât pentru verificarea calculelor, cât și pentru aflarea rapidă a unuia dintre cei doi termeni, cunoscând produsul și celălalt termen.

Două numere naturale $a$ și $b$ se numesc prime între ele dacă $cmmdc(a,b)=1$, adică nu au niciun factor prim comun. De exemplu, $35$ și $48$ sunt prime între ele (, — nu au factori primi comuni), deși niciunul dintre ele nu este, individual, un număr prim.