Teorema împărțirii cu rest

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În algebră, teorema împărțirii cu rest exprimă algoritmul procesului de împărțire între două numere la care se obține un rezultat întreg și un rest neîntreg. Enunțul teoremei este următorul:

Enunțul teoremei[modificare | modificare sursă]

Fie a (deîmpărțit) și b (împărțitor) două numere întregi, cu condiția ca b să fie nenul. Există și sunt unice numerele întregi q (câtul) și r (restul împărțirii), astfel încât să fie satisfăcute simultan condițiile:

  • a = b * q + r
  • 0 ≤ r < |b|, unde |b| reprezintă modulul (valoarea absolută) a lui b.

Demonstrație[modificare | modificare sursă]

Demonstrația teoremei conține două părți: prima, demonstrația existenței lui q și r, a doua, demonstrația unicității lui q și r.


Existența câtului și restului[modificare | modificare sursă]

Se consideră mulțimea

S = \left\{a - nd : n \in \mathbb{Z}\right\}.

Se poate demonstra că mulțimea S conține cel puțin un element întreg nenegativ. Sunt două cazuri care trebuie luate în considerare.

  • Dacă a este nenegativ, atunci se alege n = 0.
  • Dacă a este negativ, atunci se alege n = a.

În ambele cazuri, a - nd este nenegativ, de unde rezultă ca S conține întotdeauna cel puțin un întreg nenegativ. Se deduce că S conține un cel mai mic întreg nenegativ r. Prin definiție, r = a - nd pentru un anumit n. Fie q acest n. Atunci, ecuația devine a = qd + r.

Rămâne de demonstrat că 0 ≤ r < |d|. Prima inegalitate este adevărată ca urmare a alegerii lui r ca întreg nenegativ. Pentru a doua inegalitate (strictă), se presupune că r ≥ |d|. Pentru că d ≠ 0, r > 0, și d > 0 sau d < 0.

  • Dacă d > 0, atunci rd implică a-qdd. Ceea ce implică a-qd-d ≥0, implicând că a-(q+1)d ≥ 0. Deci, a-(q+1)d is in S și, deoarece a-(q+1)d=r-d cu d>0 știm a-(q+1)d<r, contrazice ipoteza că r a fost elementul cel mai mic întreg nenegativ al lui S.
  • Dacă d<0 atunci r ≥ -d implică a-qd ≥ -d. Aceasta implică a-qd+d ≥0, implicând că a-(q-1)d ≥ 0. Deci, a-(q-1)d este în S și, deoarece a-(q-1)d=r+d cu d<0 știm că a-(q-1)d<r, contrazice ipoteza că r a fost elementul cel mai mic întreg nenegativ al lui S.

În ambele cazuri, am demonstrat că r > 0 nu este cel mai mic întreg nenegativ al lui S, ceea ce este o contradicție, deci trebuie să avem r < |d|. Aceasta demonstrează complet existența lui q și r.

Unicitatea[modificare | modificare sursă]

Presupunem că există q, q' , r, r' cu 0 ≤ r, r' < |d| qstfel încât a = dq + r și a = dq' + r' . Putem considera, fără a reduce generalitatea demonstrației, qq' .

Scăzând cele două ecuații rezultă: d(q' - q) = (r - r' ).

Dacă d > 0, atunci r'r și r < dd+r' , deci (r-r' ) < d. Similar, dacă d < 0, atunci rr' și r' < -d ≤ -d+r, deci -(r- r' ) < -d. Combinând cele două ecuații |r- r' | < |d|.

Ecuația inițială implică: |d| divide |r- r' |; deci sau |d| ≤ |r- 'r' | sau |r- r' |=0. Deoarece am stabilit că |r-r' | < |d|, putem concluziona că prima variantă nu poate fi adevarată. Deci, r=r' .

Înlocuind în cele două ecuații inițiale rezultă dq = dq' și, deoarece d nu este 0, trebuie să avem q = q' ceea ce demonstrează unicitatea.