In the proof of Euclid's Division Lemma,what is the point of having an AP that extends in both ways?

Question

In the picture I have attached you can see that they(whoever is prooving this) are forming an AP with b as the common difference and extending the AP `both sides i.e. negative and positive.Since we are only dividing, because its Euclids division lemma why do we need to add b to a.What is the point of doing that?

Answer 1

The common case of arithmetic progressions is that we start with a positive number and then add positive multiples of the common difference to form an increasing sequence of numbers. If the common difference was negative, and the sequence was decreasing, then this is equivalent to extending the original arithmetic progression in reverse by adding negative multiples of the original positive common difference. In other words, reversing the order of an arithmetic progression is just another arithmetic progression with common difference the negative of the original common difference.

In the case of Euclid's Division Lemma, we are given an initial number $\, a\,$ and we want to subtract multiples of $\, b>0\,$ from it until we get a number less then $\,b.\,$ This is a finite decreasing arithmetic progression, but it can be interpreted as extending an increasing arithmetic progression starting from $\, a\,$ and extending it as mentioned in the previous paragraph.

Answer 2

The OP had trouble following the proof, but why even look at the proof when the statement of the theorem is incorrect (see comments). Not only that, since the math is not being typeset, the author has to put quotes around variables in the text to avoid confusion. Gosh, you could go to wikipedia to see this stuff with the math properly formatted.

But the OP is correct - it is only necessary to start with $a$ and then start subtracting $b$.

Let us look at the example of $a$ = $58$ and $b = 9$. In the book they use long division, but we can also understand division as being repeated subtraction.

$58, 49, 40, 31, 22, 13, 4, -5 \quad \text{STOP - NEGATIVE}$
$0,\;\, 1,\;\, 2,\;\, 3,\;\, 4,\;\; 5,\;\, 6\,\;\,\,\text{**********************}$

So when we subtract $9$ from $58$ six times, the remainder is $4$. So,

$$ 58 - 9-9-9-9-9-9 = 4$$

or

$$ 58 = 9+9+9+9+9+9 + 4$$

or

$$ 58 = 9\times(1+1+1+1+1+1) + 4$$

or

$$ 58 = 9\times6 + 4$$

So with $a = 58$ and $b = 9$, then

If $q \ge 0$ and $0 \le r \lt 9$ and $58 = 9\times q + r$, then it must follow that $q = 6$ and $r = 4$.