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 naturale 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ă a0 şi b0, 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, 0r m1|m2.
Rezultă atunci că m1 |m şi m|m1 deci m=m1.
Algoritmul lui Euclid
Definiţie. Algoritmul lui Euclid al numerelor a şi b cu a>b, este tabloul de relaţii:
a=bq1 + r1 unde 0
Aceasta descriere este doar o parte din referat.Pentru a vizualiza tot referatul va rugam sa-l descarcati de mai jos.
|
|
