CMMDC și CMMMC

C.m.m.d.c

Definitie. Numarul intreg d este cel mai mare divizor comun (c.m.m.d.c.) al numerelor intregi a si b (notam d=(a, b)), daca satisface conditiile:

d | a si d | b;

pentru orice intreg ?, pentru care ?|a si ?|b, rezulta ?|d.

Lema. Fie m, n, p trei numere naturale astfel incat m=n+p. Daca numarul natural nenul q divide oricare doua dintre numerele m,n,p atunci q divide si pe al treilea numar.

Demonstratie. Fie q|n si q|p. Atunci u, v N : n=qu si p=qv. Rezulta m=q(u+v), deci q|m. Fie acum q|m si q|n. Atunci t, s N : m=qt si n=qs. Din qt=qs+p rezulta qs ? qt si cum q>0 obtinem s ? t, de unde rezulta ca w N asa incat t = s+w. Din qt = qs+p rezulta qs+qw=qs+p, deci qw=p, unde q|p.

Analog se arata ca din q|m si q|p rezulta q|n.

Lema. Daca x, y,q,r N satisfac egalitatea x=yq+r atunci exista cel mai mare divizor comun al lui x si y daca si numai daca exista cela mai mare divizor comun al lui y si r. In plus, avem (x, y) = (y, r).

Demonstratie. Presupunem ca exista cel mai mare divizor comun al lui x si y, pe care-l notam cu d. Din d|x si d|y rezulta, conform lemei anterioare, ca d|r, deci avem d|y si d|r.

Fie acum d' N, asa incat d'|y si d'|r. Conform aceleasi leme, rezulta ca d'|x si deci d'|x si d'|y, adica d'|d. Asadar, d este cel mai mare divizor comun al lui y si r si avem (y, r) = d = (x, y).

Reciproc, presupunand ca exista cel mai mare divizor comun al numerelor y si r, pe care il notam cu d, va rezulta d|y si d|r, unde d|qy+r=x, deci avem d|x si d|y.

Fie acum d' N, asa incat d'|x si d'|y. Obtinem d'|r, deci d'|y si d'|r, de undew d'|d. Astfel, d este cel mai mare divizor comun al lui x si y si avem (x, y)=d=(y, r).

Teorema. Fie a, b N . Atunci exista si este unic cel mai mare divizor comun al numerelor a si b.

Demonstratie. Daca a=b=0, atunci cel mai mare divizor comun este 0. Presupunem, in continuare, b? 0. Procedeul de determinare pe care-l vom folosi poarta numele de Algoritmul lui Euclid.

C.m.m.m.c

Definitie. Numarul intreg m este cel mai mic multiplu comun (c.m.m.m.c.) al numerelor intregi a si b (notam m=[a, b]) daca satisface conditiile:

a | m si b | m;

pentru orice intreg ?, pentru care a | ? si b | ?, rezulta m | ?.

Teorema. Pentru orice a, b N exista su este unic cel mai mic multiplu comun al lor.

Demonstratie.Daca a=0 sau b=0,atunci singurul multiplu a lui a si b este 0.

Presupunem in continuare ca a?0 si b?0, prin urmare 0 nu divide ab, deci 0 nu satisface conditiile de a fi cel mai mic multiplu comun pentru a si b.

Consideram multimea: Ma,b={m' N* | a|m' si b|m'}.

Din faptul ca ab Ma,b:m ? m', oricare ar fi m' Ma,b.

Vom arata ca m=[a,b].

Din m Ma,b rezulta a|m si b|m.

Aplicam teorema impartirii cu rest pentru m' si m. Rezulta ca exista q, r asa incat m'=mq+r, 0?r<m. Sa presupunem acum ca r?0. Din a|m. A|m' si m'=mq+r rezulta ca a|r. Analog din b | m si b | m' rezulta ca b|r. Asadar, r Ma,b si cum m?m', oricare ar fi m' Ma,b, obtinem ca m?r, ceea ce este fals.

Prin urmare, r=0, de unde m|m' si cu aceasta am verificat faptul ca m=[a, b].

Mai ramane de aratat unicitatea lui m.

Presupunem ca exista m1 N, astfel incat da fie satisfacute conditiile:

a|m1, b|m1

oricare m2 N : a|m2, b|m2 => m1|m2.

Rezulta atunci ca m1 |m si m|m1 deci m=m1.