Teorema împărțirii cu rest
 | Acest articol sau această secțiune are bibliografia incompletă sau inexistentă. Puteți contribui prin adăugarea de referințe în vederea susținerii bibliografice a afirmațiilor pe care le conține. |
Î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:
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 r ≥ d implică a-qd ≥ d. 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, q ≤ q' .
Scăzând cele două ecuații rezultă: d(q' - q) = (r - r' ).
Dacă d > 0, atunci r' ≤ r și r < d ≤ d+r' , deci (r-r' ) < d. Similar, dacă d < 0, atunci r ≤ r' ș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