C.m.m.d.c si C.m.m.m.c Categoria: Referat Matematica
Descriere: 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)... |
|
||
|
|
|||
|
1 C.m.m.d.c. şi 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<m. Să presupunem acum că r0. Din a|m. A|m’ şi m’=mq+r rezultă că a|r. Analog din b | m şi b | m’ rezultă că b|r. Aşadar, r Ma,b şi cum mm’, oricare ar fi m’ Ma,b, obţinem că mr, ceea ce este fals. 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. 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<r1<b; b=r1q1 + r2 unde 0<r2<r1; r1=r2q3 + r3 unde 0<r3<r2; ............................................ rn-2= rn-1q n + rn unde 0<rn<rn-1; rn-1 = rnqn+1 unde rn+1=0 sau relaţia a=bq, dacă b | a. Algoritmul lui Euclid există şi este finit. Ultimul rest nenul din algoritm dă c.m.m.d.c. al numerelor a şi b adică rn = (a, b). Dacă b | a, atunci (a, b) =b. Proprietăţi ale c.m.m.d.c. şi c.m.m.m.c.: (a,a) = a , [a, a] = a (idempotenţă); (a, b) = (b, a) [a, b] = [b, a] (comutativitate); (a, (b, c)) = ((a, b), c), [a, [b, c]] = [[a, b], c] (asociativitate); (a, [a, b]) = a, [a, (a, b)] = a (absorbţie), adică mulţimea numerelor �ntregi formează o latice �n raport cu c.m.m.d.c. şi c.m.m.m.c. considerate ca operaţii binare. Pentru orice pereche a, b de numere �ntregi (1) Definiţie. Numerele �ntregi a, b, se numesc prime �ntre ele sau relativ prime dacă (a, b) = 1. Teoremă fundamentală. Dacă a | bc şi (a, b =1, atunci a | c. Dacă a | c, b | c şi (a, b) = 1, atunci ab | c. Proprietatea de distributivitate: (a, [b, c]) = [(a, b), (a, c)] şi [a, (b, c)] = ([a, b)], [a, c]). Pentru orice �ntreg k (ka1, ka2, ..., kan) = k (a1, a2, ..., an) şi [ka1, ka2, ... , kan] = k [a1, a2, ..., an]. (2) C.m.m.d.c. al numerelor a1, a2, ..., an este o combinaţie liniară a acestor numere cu coeficienţi �ntregi, adică există numerele �ntregi u1, u2, ..., un astfel ca : (a1, a2,, ..., an) = a1u1+a2u2+...+anun . Definiţie. Numerele �ntregi a1, a2, ..., an se numesc prime �ntre ele dacă (a1, a2, ..., an)=1. Teoremă. Condiţia necesară şi suficientă ca numerele a1, a2, ..., an să fie prime �ntre ele este ca să existe numerele �ntregi u1, u2, ..., un astfel ca a1u1+a2u2+...+anun = 1. Datorită asociativităţii, c.m.m.d.c. şi c.m.m.m.c. se pot calcula prin recurenţă. Pentru n numere �ntregi a1, a2,, ..., an proprietatea (1) devine [a1, a2, ..., an] • (A1, A2, ..., An) = a1a2, ...an , [A1, A2, ..., An] • (a1, a2, ..., an) = a1a2, ...an , unde a1a2 ...,an = a1A1=a2A2=...=anAn. �n baza proprietăţii (2), c.m.m.d.c. se obţine lu�nd produsul factorilor comuni din descompunerea canonică, cu exponenţii cei mai mici, iar c.m.m.m.c. se obţine lu�nd produsul tuturor factorilor cu exponenţii cei mai mari. Ecuaţia x2+y2=z2 are, �n numerele �ntregi, o soluţie x=mab, Cu m �ntreg arbitrar, a şi b primi �ntre ei, impari, sau, altfel scrise, x = m(p2-q2), y = 2mpq, z = m(p2+q2), cu p şi q primi �ntre ei, de paritate diferită. Teorema lui B�zout Definiţie: dacă d=(a,b) k,l є Z: d=k•a+l•b. Demonstraţie: Definim r0=a, r1=b, n≥1, rn+1 este restul �mpărţirii lui rn-1 la rn (rn≠0). Demonstrăm prin inducţie după n. n є N αn ,βn є N : rn= αn•a+βn•b Folosim varianta de inducţie P(0) şi P(1) P(n) şi P(n-1) ==> P(n+1) n P(n) 1)Arătăm că P(0) şi P(1) sunt adevărate r0=a=1•a+0•b (α0=1,β0=0) r1=b=0•a+1•b (α1=0,β1=0) 2)Presupunem rn-1= αn-1•a+βn-1•b rn= αn•a+βn•b Arătăm că αn,βn є : rn+1= αn+1•a+βn+1•b Din Teorema �mpărţirii cu rest (T.I.R.) ==> rn-1= qn•rn+rn+1 ==> rn+1=rn-1-qn•rn rn+1=αn-1•a+βn-1•b-( αn•a+βn•b)•qn=(αn-1-qn•αn)•a+( βn-1- βn•qn)•b rn+1=αn+1•a+βn+1•b unde αn+1=αn-1-qn•αn βn+1=βn-1-an•βn Din 1) şi 2) ==> P(n) adevarată n є N Observaţie: din această demonstraţie a teoremei lui Bezout obţinem şi un algoritm de aflare a numerelor k şi l din scrierea d=k•a+l•b Vom considera tabelul următor unde a≥b: - q k l 1 0 0 1 a= b= - q 1 -q r - q1 -q1 q •q1+1 -q1•r+b=r1 ………. ………………. ………….. Algoritmul este: �mpărţim pe a la b şi obţinem restul r, q-c�tul �mpărţitii lui a la b -q•b+a=r �mpărţim pe b la r si obţinem restul r1,q1-c�tul �mpărţirii lui b la r continuăm p�nă obţinem r=0 ultimul rest nenul este d, iar numerele din tabel de pe coloanele k şi l corespunzătoare acestui rest nenul sunt cele căutate Exemplu: Să se calculeze (250,48) şi să se scrie sub forma d=250•k+48•l, k,l є Z Rezolvare: -q k l 250 48 0 0 1 -5 1 -5 10 -4 -4 21 8 -1 5 -26 2 -4 -24 125 0 Ultimul rest nenul este 2 ==> (250,48)=2 ==> 2=250•5-26•48 Consecinţe ale teoremei lui B�zout Dacă d=(a,b) ==> =1 Dacă �mpărţim două numere cu c.m.m.d.c. al lor se obţin numere prime �ntre ele .(deci două numere a şi b sunt prime �ntre ele dacă c.m.m.d.c. al lor este 1 ) Dacă m│a•b şi (m,a)=1 ==> m│b (Lema lui Gauss) (Lema lui Gauss2) dacă p-prim şi p│a•b ==> p│a sau p│b. Dacă (m,a)=1, (m,b)=1 ==> (m,a•b)=1 Dacă (a,b)’d, iar k є N* ==> (k•a,k•b)=k•d Demonstraţie: d=(a,b) ==> k,l є Z: d=k•a+l•b │:d ==> 1= Fie s un divizor comun al numerelor şi ==> s│ şi s│ ==> s│ şi s│ ==> s│ ==> s este un divizor natural al numerelor 2) (m,a)=1 ==> k,l є Z: 1=k•m+l•a │b ==> k•m•b+l•a•b=b ==> b m Q.E.D. m m Pentru a demonstra 3) o reformulăm sub forma: Fie p=prim şi p│a•b. Dacă p nu divide a atunci p│b Din 2) ==> p│a•b, p nu divide a ==> (p,a)=1 (p=prim) ==> p│b 4) (m,a)=1 ==> k,l є Z: 1=k•m+l•a (m,b)=1 ==> x,y є Z: 1=x•m+y•b ==> 1-km=l•a 1-xm=y•b ==>(1-k•m)(1-x•m)=l•y•a•b 1-(k+x)m+k•x•m2 =l•y•a•b 1=(k+x-k•xm)m+l•y•a•b Notăm k+x-kxm=k•1 l•y=l1 ==> k1m+l1a•b=1 ==> (m,a•b)=1 5) (a,b)=1 ==> x,y є Z: d=x•a+y•b �•k ==> x•k•a+y•k•b=k•d ==> (k•a,k•b)=k•d |
|||
| Referat oferit de www.ReferateOk.ro | |||
Varianta Printabila 
Free Download Referat PDF
Free Download Referat Word |
Home : Despre Noi : Contact : Parteneri |  |
