Teorema împărțirii cu rest

De la Wikipedia, enciclopedia liberă
Jump to navigation Jump to search

Î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[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
  • r<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

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.

Bibliografie[modificare | modificare sursă]

  • Fraleigh, John B. (), A First Course in Abstract Algebra (ed. 5th), Addison-Wesley, ISBN 978-0-201-53467-2 
  • Rotman, Joseph J. (), A First Course in Abstract Algebra with Applications (ed. 3rd), Prentice-Hall, ISBN 978-0-13-186267-8