referat, referate , referat romana, referat istorie, referat geografie, referat fizica, referat engleza, referat chimie, referat franceza, referat biologie
 
Informatica Educatie Fizica Mecanica Spaniola
Arte Plastice Romana Religie Psihologie
Medicina Matematica Marketing Istorie
Astronomie Germana Geografie Franceza
Fizica Filozofie Engleza Economie
Drept Diverse Chimie Biologie
 

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

Varianta Printabila 


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ă 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<m. Să presupunem acum că r0. 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 mm’, oricare ar fi               m’   Ma,b, obţinem că mr, 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
Home : Despre Noi : Contact : Parteneri  
Horoscop
Copyright(c) 2008 - 2012 Referate Ok
referate, referat, referate romana, referate istorie, referate franceza, referat romana, referate engleza, fizica