MHB Is the Set of Non-Negative Integers Formed by $a-dx$ Always Nonempty?

[MI5]

My question concerns proving the set of non-negative integers of the form $a-dx ~~(a, d, x \in \mathbb{Z}, d \ge 1)$ is nonempty. This is the proof from my book. If $a \ge 0$, then $a = a-d\cdot 0 \in S$. If $a < 0$, let $x = -y$ where $y$ is a positive integer. Since $d$ is positive, we have $a-dx = a+dy \in S$ for sufficiently large $y$. Thus $S$ is nonempty.

Could someone explain sentence that I've bolded? It's not clear to me.

 

[Deveno]

Um, simple form: x can be negative?

For example, if a = -1,000,000, and d = 2, it suffices to to take x < -500,000.

 

[MI5]

I think I understand now, thank you. Should it be $x \le -500,000$ though?

 

[Deveno]

If you only require that [math]a - dx[/math] be non-negative, sure, yep, you betcha.

 

[MI5]

Thank you. One more question. This is from the beginning of a proof of the division algorithm (as you probably recognised). The thing is, considering this particular set came out of a thin air. Do you know - or would you be able to give any motivation?

 

[Deveno]

I believe I can do that:

Suppose we are trying to establish a quotient and remainder for b divided by a. We might, naively try "guess and check":

Pick a positive number d, any number. Calculate ad, and subtract it from b, call this number "a remainder", r:

r = b - ad.

Now, is there "some possible best remainder"? One way to "optimize" this is to try to pick d so that r is as small as possible (for reasons that may become clearer much later in your mathematical life, it is also more practical to work with non-negative remainders).

So what is this set of "non-negative remainders"? Why, it's just the S we've been talking about! Why are we so concerned about S being non-empty?

So we can use THIS theorem:

(Well-ordering of the Natural Numbers}:

Any ​non-empty set of non-negative integers has a least element.

This allows us to say with confidence a "best" remainder EXISTS, even if we haven't yet done the arithmetic. This, in turn let's us find UNIQUE d,r for b divided by a: we pick d so that r is the least element of S. For example, if we want to find these when b = 57, a = 7:

57 - 7 = 50 (first choice of d = 1)
57 - 14 = 43 (second choice of d = 2). Well, 43 < 50, so we'll keep d = 2 for now, and keep plugging away.

57 - 21 = 36 (third choice of d = 3). Again, 36 < 43, so we have a new winner (for now).

57 - 28 = 29 (29 < 36)
57 - 35 = 22 (22 < 29)
57 - 42 = 15 (15 < 22)
57 - 49 = 8 (8 < 15)
57 - 56 = 1 (1 < 8)

57 - 63 = -6 (oops, we went too far, -6 is negative). So the unique values we seek are d = 8, and r = 1. If we have established beforehand (rigorously) the existence and uniqueness of d and r, we don't have to go any further, our search for d and r is done, we don't have to try any more possibilities (good thing, too, since there are SO MANY integers we might try).