The integers are a Euclidean Domain

How to prove that the integers are a Euclidean Domain

To show that the integers are a Euclidean domain (or possess a Division Algorithm), finding one norm only to verify the conditions to be a Euclidean Domain is enough.

Proof that the integers are Euclidean Domain

Proof: Define the following norm:
N(x) = \lvert x \rvert,
where x \in \mathbb{Z}. We need to show that for any two elements a,b \in \mathbb{Z} with b\neq 0 there exists elements q and r in \mathbb{Z} such that
a = qb + r \quad \text{with} \quad r = 0 \quad \text{or} \quad N(r) < N(q).
We let a and b be nonzero elements and we will check two cases: b > 0 and b < 0.

For b > 0, let a \in [qb, (q + 1)b). Then a = qb + r where r \in [0, \lvert b \rvert) since r = a - qb < (q + 1)b - qb = b. Therefore, N(r) < N(b) = \lvert b \rvert or r = 0.

For b < 0, we take a \in [-qb, -(q + 1)b) since -b > 0. Then a = q\cdot (-b) + r where r = a + qb < -(q + 1)b - qb = -b. Obviously, since -b > 0, we have that \lvert r \rvert = N(r) < N(-b) = \lvert -b \rvert or r = 0.

We haven't included the case when the remainder is negative in all the above cases. The approach is similar to the above. Take the elements b > 0 and use the same properties we used there and r > 0 (note that we don't take this remainder to be negative!). Now let a = q'b + r', where q' = q + 1 and r' = r - b. Then r' < 0 since r \in [0, \lvert b \rvert). Now we can perform the rest as r - b \in (-b, b):

r - b < 0 &\iff r < b \\
&\iff r - b < b \\
&\iff r' < b \\
&\iff \lvert r' \rvert < \lvert b \rvert \\
&\iff N(r') < N(b),
which ends the proof by showing that the integers are indeed a Euclidean Domain. We could also prove everything with induction, but that is something that the reader can verify (but you can always leave a comment if you want know it).

Leave a Reply