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



Cele mai ok referate!
www.referateok.ro