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 |  |
