Question

Prove the Euclid Division Lemma.

Answer 1

EUCLID’S DIVISION LEMMA AND G.C.D.
Here I give proofs of Euclid’s Division Lemma, and the existence and uniqueness
of g.c.d.(a, b), and the existence of integers x and y such that
g.c.d(a, b) = ax + by.
These are the proofs which I gave in class. These proofs differ from those given in
the book.
All arguments are based on the following proposition.
Proposition 1. Every non-empty bounded below set of integers contains a unique
minimal element.
This proposition looks obvious, and we take it for granted. In fact, this propo-
sition is equivalent to the principle of mathematical induction, and one can easily
prove it by an inductive argument.
Note, however, that this obvious proposition becomes false if one speaks about
rational numbers instead of reals. Indeed, the set Q+ = {x ∈ Q | x > 0} of
positive rational numbers does not contain a minimal element. Indeed, no element
is minimal because for every x ∈ Q+, also x/2 ∈ Q+, and, since x/2 < x, no x can
be the minimal element of Q+.
We start with Euclid’s Division Lemma (Theorem 2-1 from the textbook).
Theorem. For any positive integer k and integer j, there exist unique integers q
and r such that
0 ≤ r < k
and
j = qk + r
Proof. We start with the uniqueness clause. Assume that we have two presentations
j = qk + r = q
0
k + r
0
with with integers q and q
0
, and both 0 ≤ r, r0 < k. Thus
r − r
0 = (q
0 − q)k.
Note that, since 0 ≤ r < k and 0 ≤ r
0 < k, we have that
|r − r
0
| < k.
We thus have that
k > |r − r
0
| = |q
0 − q|k ≥ k,
and this would lead us to an absurd conclusion k > k unless
r − r
0
| = |q
0 − q| = 0,
which proves the uniqueness.
We now address the existence. Consider the set
S = {j − xk |x ∈ Z, j − xk ≥ 0}

Answer 2

Answer:

Step-by-step explanation: