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

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 nct 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 nct 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 nct 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, presupunnd 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 nct 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 nct 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ămne de arătat unicitatea lui m.
Presupunem că există m1 N, astfel nct 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 lund produsul factorilor comuni din descompunerea canonică, cu exponenţii cei mai mici, iar c.m.m.m.c. se obţine lund 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 Bzout


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-ctul mpărţitii lui a la b
-q•b+a=r
mpărţim pe b la r si obţinem restul r1,q1-ctul mpărţirii lui b la r
continuăm pnă 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 Bzout

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