Lemma 1: abs(a/b) ≤ 1 if and only if abs(a) ≤ abs(b)
Proof:
Case I: a,b are both positive
(1) Assume abs(a/b) ≤ 1
(2) a/b ≤ 1
(3) a ≤ b
(4) abs(a) ≤ abs(b)
(5) Assume abs(a) ≤ abs(b)
(6) a ≤ b
(7) a/b ≤ 1
(8) abs(a/b) ≤ 1
Case II: a,b are both negative
(1) Assume abs(a/b) ≤ 1
(2) a/b ≤ 1
(3) -a ≤ -b [since -b is positive]
(4) abs(a) ≤ abs(b)
(5) Assume abs(a) ≤ abs(b)
(6) -a ≤ -b
(7) a/b ≤ 1 [since -b is positive]
(8) abs(a/b) ≤ 1
Case III: Only b is negative
(1) Assume abs(a/b) ≤ 1
(2) -(a/b) ≤ 1
(3) (a/b) ≤ -1
(4) a ≤ -b [since b is negative and -b is positive]
(5) abs(a) ≤ abs(b) [ since abs(b) = -b ]
(6) Assume abs(a) ≤ abs(b)
(7) a ≤ -b
(8) a/b ≥ -1 [since b is negative]
(9) -(a/b) ≤ 1
(10) abs(a/b) ≤ 1
Case IV: Only a is negative
(1) Assume abs(a/b) ≤ 1
(2) -(a/b) ≤ 1
(3) -a ≤ b [since b is positive]
(4) abs(a) ≤ abs(b) [since abs(a) = -a and abs(b) = b]
(5) Assume abs(a) ≤ abs(b)
(6) -a ≤ b
(7) -a/b ≤ 1
(8) abs(a/b) ≤ 1
QED
Corollary 1.1: abs(a) is greater than abs(b) if and only if abs(a/b) greater than 1
Proof:
(1) Assume that abs(a) is greater than abs(b)
(2) Assume that abs(a/b) is not greater than 1
(3) Then abs(a/b) ≤ 1
(4) Then abs(a) ≤ abs(b) [From Lemma 1 above]
(5) But this contradicts step #1 so we reject our assumption in step #2.
(6) Assume that abs(a/b) is greater than 1.
(7) Assume that abs(a) is not greater than abs(b)
(8) Then abs(a) ≤ abs(b)
(9) Then abs(a/b) ≤ 1 [From Lemma 1 above]
(10) But this contradicts step #6 so we reject our assumption in step #7.
QED
Lemma 2:
if a,b,q are integers such that abs(a/b - q) is less than 1
Then:
There exists an integer c such that abs(a/b - c) is less than (1/2)
Proof:
(1) Assume abs(a/b - q) is greater than (1/2) [Otherwise, set c = q and we are done]
(2) if (a/b - q) is less than -1/2, then [a/b - (q-1)] is less than 1/2 and [a/b - (q-1)] is greater than 0
(3) if (a/b - q) is greater than 1/2, then [a/b - (q+1)] is greater than -1/2 and [a/b - (q+1)] is less than 0
QED
Corollary 2.1:
Let a,b be integers
if abs(a) ≤ abs(b)
Then:
There exists an integer c such that abs(a/b - c) is less than (1/2)
Proof:
(1) Assume abs(a) ≤ abs(b)
(2) Then abs(a/b) ≤ 1. [See Lemma 1 above]
(3) If (a/b) = 0, then c = 0 and the conclusion follows.
(4) if (a/b) ≥ -1, then abs(a/b + 1) is less than 1.
(5) if (a/b) ≤ 1, then abs(a/b - 1) is greater than -1.
(6) So, the conclusion follows from Lemma 2 above.
QED
1 comment :
In Case III: Only b is negative, (3) should be a/b ≥ -1 instead of a/b ≤ -1
Post a Comment