Divizibilitate, numere prime, compuse

Definiţia: Dacă considerăm două numere naturale a și b, spunem că b divide a dacă există un număr natural c astfel încât a = bc.

În acest caz, spunem că b este un divizor al lui a sau b divide a sau  a este un multiplu de b.

Notație:

b divide a:                               b/a

a divizibil cu b:                      

b nu divide pe a:                     

Proprietăți ale relației de divizibilitate.

Fie a, b, c numere naturale.

a)         1 divide orice număr natural.

b)        Relația de divizibilitate este o relație de ordine:

Orice număr natural se divide cu el însuși. (Reflexivitatea)

Dacă a divide b și b divide a atunci a = b. (Antisimetria)

Dacă a divide b și b divide c atunci a îl va divide pe c. (Tranzitivitate)

c)         Orice număr natural în divide pe 0.  Operația 0 divide a, nu are sens.

d)        Dacă a îl divide pe b și pe c atunci a va divide orice combinație liniară a lui b și c.

Observaţia  Orice număr natural diferit de 1 admite cel puţin 2 divizori distincţi pe 1 şi pe a.

Definiţia  Divizorii 1 și a ai numărului a se numesc divizori improprii. Orice alt divizor diferit de 1 sau a se numeşte divizor propriu.

Definiţia  Un număr natural diferit de 1 care nu admite divizori proprii se numeşte număr prim. Un număr natural care admite divizori proprii se numeşte număr compus.

Observaţia 

a)    Numărul 1 este singurul număr natural care admite un singur divizor din mulţimea numerelor naturale. Din acest motiv, 1 este considerat caz de excepţie.

b)    Dacă p, q sunt numere prime și dacă p îl divide pe q, atunci p este egal cu q.

c)   Două numere consecutive sunt prime doar în cazul în care p = 2 și p’ = 3, deoarece singurul număr prim par este 2.

d)    Un număr natural p mai mare decât 1 este număr prim dacă fiind divizor al unui produs de doi factori, el divide măcar unul din aceşti doi factori: dacă p divide ab, atunci p divide a sau p divide b.

e)   Dacă p este prim şi p divide a₁a₂…a_k, atunci p trebuie să dividă cel puțin unul din factori.

Propoziția  Dacă un număr este compus, cel mai mic divizor propriu al său este prim.

Teorema lui Euclid: Mulţimea numerelor prime este infinită.

Definiţia: Cel mai mic multiplu comun (c.m.m.m.c) a două sau mai multe numere reprezintă cel mai mic număr natural care se divide cu toate numerele date. Notație: m = [a, b].

Algoritm:

1. Descompunem numerele în factori primi.

2. Înmulțim toți factorii comuni și necomuni la puterea cea mai mare.

Definiţia: Cel mai mare divizor comun (c.m.m.d.c) a două sau mai multe numere reprezintă cel mai mare număr natural care divide toate numerele date. Notație: d = (a, b).

Algoritm:

1. Descompunem numerele în factori primi.

2. Înmulțim toți factorii comuni la puterea cea mai mică.

Algoritmul lui Euclid este dat prin: Cel mai mare divizor comun a două numere a şi b este ultimul rest diferit de 0 al împărţirilor succesive:

            a = bq + r,                  0 < r < b,

            b = rq₁ + r₁,                0 < r₁ < r,

            r = r₁q₂ + r₂,               0 < r₂ < r₁

            ........    .......

            r_s-2 = r_s-1q_s + r_s,           0 < r_s < r_s-1,

            r_s-1 = r_sq_s+1,

adică r_s = d = (a, b).

Teorema fundamentală a aritmeticii sau Teorema factorizării unice este o teoremă care afirmă că orice număr întreg poate fi exprimat în mod unic ca produs de numere prime.