1.9. WELL ORDERING AND ARCHIMEDEAN PROPERTY 21

Theorem 1.9.7 Suppose x < y and y − x > 1. Then there exists an integer l ∈ Z, suchthat x < l < y. If x is an integer, there is no integer y satisfying x < y < x+ 1.

Proof: Let x be the smallest positive integer. Not surprisingly, x = 1 but this can beproved. If x < 1 then x2 < x contradicting the assertion that x is the smallest naturalnumber. Therefore, 1 is the smallest natural number. This shows there is no integer, y,satisfying x < y < x+ 1 since otherwise, you could subtract x and conclude 0 < y − x < 1for some integer y − x.

Now suppose y − x > 1 and let

S ≡ {w ∈ N : w ≥ y} .

The set S is nonempty by the Archimedean property. Let k be the smallest element of S.Therefore, k − 1 < y. Either k − 1 ≤ x or k − 1 > x. If k − 1 ≤ x, then

y − x ≤ y − (k − 1) =

≤0︷ ︸︸ ︷y − k + 1 ≤ 1

contrary to the assumption that y − x > 1. Therefore, x < k − 1 < y. Let l = k − 1. ■It is the next theorem which gives the density of the rational numbers. This means that

for any real number, there exists a rational number arbitrarily close to it.

Theorem 1.9.8 If x < y then there exists a rational number r such that x < r < y.

Proof: Let n ∈ N be large enough that

n (y − x) > 1.

Thus (y − x) added to itself n times is larger than 1. Therefore,

n (y − x) = ny + n (−x) = ny − nx > 1.

It follows from Theorem 1.9.7 there exists m ∈ Z such that

nx < m < ny

and so take r = m/n. ■

Definition 1.9.9 A set S ⊆ R is dense in R if whenever a < b, S ∩ (a, b) ̸= ∅.

Thus the above theorem says Q is “dense” in R.

Theorem 1.9.10 Suppose 0 < a and let b ≥ 0. Then there exists a unique integer p andreal number r such that 0 ≤ r < a and b = pa+ r.

Proof: Let S ≡ {n ∈ N : an > b} . By the Archimedean property this set is nonempty.Let p + 1 be the smallest element of S. Then pa ≤ b because p + 1 is the smallest in S.Therefore,

r ≡ b− pa ≥ 0.

If r ≥ a then b − pa ≥ a and so b ≥ (p+ 1) a contradicting p + 1 ∈ S. Therefore, r < a asdesired.

To verify uniqueness of p and r, suppose pi and ri, i = 1, 2, both work and r2 > r1. Thena little algebra shows

p1 − p2 =r2 − r1a

∈ (0, 1) .

Thus p1 − p2 is an integer between 0 and 1, contradicting Theorem 1.9.7. The case thatr1 > r2 cannot occur either by similar reasoning. Thus r1 = r2 and it follows that p1 = p2.■

This theorem is called the Euclidean algorithm when a and b are integers.