Dowód twierdzenia o dzieleniu z resztą

Question

Witam, 

od pewnego czasu próbuję przeprowadzić pewien dowód twierdzenia o dzieleniu z resztą, ale moje wysiłki spełzają na napisaniu kilku linijek kończących się sprzecznością. Chcę zaznaczyć, że nie chodzi mi o dowód dostępny na wikipedii i innych portalach. 

Oto problem:

Twierdzenie: Niech liczby a i b należą do całkowitych i b jest różne od zera. Wówczas istnieje dokładnie jedna para liczb całkowitych q,r taka że:

a = qb + r oraz 0 <= r < b

Dowód (pierwsza część b > 0 jest zrozumiała): Wykazujemy istnienie stosownej pary. Zakładamy, że b > 0 i definiujemy: q = [a / b] (cecha z ilorazu) oraz r = a - bq, wtedy:

q <= a / b < q + 1 zatem: qb <= a < qb + b co dalej daje: 0 <= a - qb < b czyli: 0 <= r < |b| (moduł z b).

Drugiej części nie wiem jak skutecznie przeprowadzić, choć należy podobno postąpić analogicznie: b < 0 i definiujemy:

q = - [a / |b|] oraz r = a - bq

Kwestię jednoznaczności uzyskanych wyników na tę chwilę sobie daruję.

Comments

Prosiłbym, aby korzystać z tagów bez znaku # - tak się przyjęło już na forum i lepiej używać właśnie takiej formy - prościej później odnaleźć dane pytanie po tagach.

Answer 1

Zróbmy to zadanie od początku i zastanówmy się krok po kroku o co chodzi. Twierdzenie mówi nam:

Dla dowolnych dwóch liczb a, b, takich że b =/= 0 istnieje tylko jedna para liczb q ,r takich że a=qb + r, przy czym |b| > r >= 0.

Mamy więc wykazać, że istnieje para takich liczb, ponadto że jest jedna jedyna. Ponieważ darujemy sobie kwestię jednoznaczności, to jej nie analizowałem. Zanim jednak przejdziemy do dowodu, to warto przytoczyć trzy nierówności związane z właściwościami cech. Oznaczmy cechę (podłogę) z liczby x za pomocą nawiasów kwadratowych, zaś cechę górną (sufit) za pomocą nawiasów okrągłych (nie doczekamy się na tym forum implementacji LaTeXa ;)). Zachodzą następujące relacje:

(1): [x] <= x < [x] + 1
(2): (x) - 1 < x <= (x)
(3): [x] <= x <= (x)

Cały dowód możemy podzielić na cztery przypadki. Pierwszy, najprostszy:

a >= 0 ^ b > 0

Wiemy że reszta ma być nieujemna, toteż:

a = qb + r
r = a - qb >= 0
a - qb >=0
a >= qb   / :b
a/b >= q

Wyrażenie a/b to nasz x, korzystając z (3) widzimy, że q musi być więc podłogą:

q = [a/b]

Wykorzystujemy więc (1):

q <= a/b < q + 1   / *b
qb <= a < qb + b   / - qb
0 <= a -qb < b
0 <= r < b

Pokazaliśmy więc, że jeśli a oraz b są dodatnie (lub a=0) oraz r jest nieujemne, to faktycznie r jest mniejsze od b. Ale to był tylko jeden przypadek. Rozważmy teraz drugą kombinację:

a >= 0 ^ b < 0

Analogicznie rozpoczynamy od zbadania wyrażenia q:

r >= 0
a - qb >= 0
a >= qb   / :b
a/b <= q

Ponieważ b jest ujemne, to nierówność zmienia znak i tym samym, korzystając z (3),  widzimy że q będzie sufitem:

q = (a/b)

Skoro tak, to tym razem korzystamy z (2), nie zaś z (1):

q - 1 < a/b <= q   / *b
qb - b > a >= qb   / -qb
-b > a - qb >= 0
-b > r >= 0    // ale b < 0, a więc -b = +b
|b| > r >= 0

Znów wykazaliśmy to samo. Postępując analogicznie można rozwiązać pozostałe dwa przypadki, tak więc twierdzenie będzie udowodnione dla każdej kombinacji a, b:

0 <= r < |b|

Pozostawiam to Tobie już jako ćwiczenie. Powodzenia!

Comments

nie doczekamy się na tym forum implementacji LaTeXa ;)

Owszem, przydałaby się, ale nie jest tak tragicznie, jak ci się wydaje. Wystarczy powklejać grafiki przedstawiające wyrażenia matematyczne wygenerowane przez LaTeXa w treść posta… Trzeba sobie jakoś radzić, co nie?

---

Jeśli grafiki nie zostaną usunięte w przyszłości z serwera, to powiedzmy, że jest to jakieś rozwiązanie :)