C.m.m.d.c si C.m.m.m.c

C.m.m.d.c

Definitie. Numãrul întreg d este cel mai mare divizor comun (c.m.m.d.c.) al numerelor întregi a ºi b (notãm d=(a, b)), dacã satisface condiþiile:
d | a ºi d | b;
pentru orice întreg , pentru care |a ºi |b, rezultã |d.
Lemã. Fie m, n, p trei numere reale astfel încât m=n+p. Dacã numãrul natural nenul q divide oricare douã dintre numerele m,n,p atunci q divide ºi pe al treilea numãr.

Demonstraþie. Fie q|n ºi q|p. Atunci u, v N : n=qu ºi p=qv. Rezultã m=q(u+v), deci q|m. Fie acum q|m ºi q|n. Atunci t, s N : m=qt ºi n=qs. Din qt=qs+p rezultã qs  qt ºi cum q>0 obþinem s  t, de unde rezultã cã w N aºa încât t = s+w. Din qt = qs+p rezultã qs+qw=qs+p, deci qw=p, unde q|p.
Analog se aratã cã din q|m ºi q|p rezultã q|n.

Lemã. Dacã x, y,q,r N satisfac egalitatea x=yq+r atunci existã cel mai mare divizor comun al lui x ºi y dacã ºi numai dacã existã cela mai mare divizor comun al lui y ºi r. În plus, avem (x, y) = (y, r).
Demonstraþie. Presupunem cã existã cel mai mare divizor comun al lui x ºi y, pe care-l notãm cu d. Din d|x ºi d|y rezultã, conform lemei anterioare, cã d|r, deci avem d|y ºi d|r.

Fie acum d’ N, aºa încât d’|y ºi d’|r. Conform aceleaºi leme, rezultã cã d’|x ºi deci d’|x ºi d’|y, adicã d’|d. Aºadar, d este cel mai mare divizor comun al lui y ºi r ºi avem (y, r) = d = (x, y).
Reciproc, presupunând cã existã cel mai mare divizor comun al numerelor y ºi r, pe care îl notãm cu d, va rezulta d|y ºi d|r, unde d|qy+r=x, deci avem d|x ºi d|y.

Fie acum d’ N, aºa încât d’|x ºi d’|y. Obþinem d’|r, deci d’|y ºi d’|r, de undew d’|d. Astfel, d este cel mai mare divizor comun al lui x ºi y ºi avem (x, y)=d=(y, r).
Teoremã. Fie a, b N . Atunci existã ºi este unic cel mai mare divizor comun al numerelor a ºi b.
Demonstraþie. Dacã a=b=0, atunci cel mai mare divizor comun este 0. Presupunem, în continuare, b 0. Procedeul de determinare pe care-l vom folosi poartã numele de Algoritmul lui Euclid.

C.m.m.m.c

Definiþie. Numãrul întreg m este cel mai mic multiplu comun (c.m.m.m.c.) al numerelor întregi a ºi b (notãm m=[a, b]) dacã satisface condiþiile:
a | m ºi b | m;
pentru orice întreg , pentru care a |  si b | , rezultã m | .
Teoremã. Pentru orice a, b N existã su este unic cel mai mic multiplu comun al lor.
Demonstraþie.Dacã a=0 sau b=0,atunci singurul multiplu a lui a ºi b este 0.
Presupunem în continuare cã a0 ºi b0, prin urmare 0 nu divide ab, deci 0 nu satisface condiþiile de a fi cel mai mic multiplu comun pentru a ºi b.

Considerãm mulþimea: Ma,b={m’ N* | a|m’ ºi b|m’}.
Din faptul cã ab Ma,b:m  m’, oricare ar fi m’ Ma,b.
Vom arãta cã m=[a,b].
Din m Ma,b rezultã a|m ºi b|m.

Aplicãm teorema împãrþirii cu rest pentru m’ ºi m. Rezultã cã existã q, r aºa încât m’=mq+r, 0r

Prin urmare, r=0, de unde m|m’ ºi cu aceasta am verificat faptul cã m=[a, b].
Mai rãmâne de arãtat unicitatea lui m.
Presupunem cã existã m1 N, astfel încât dã fie satisfãcute condiþiile:
a|m1, b|m1
oricare m2 N : a|m2, b|m2 => m1|m2.
Rezultã atunci cã m1 |m ºi m|m1 deci m=m1.