I thought I was familiar with the regular Euclidean algorithm, but I am having trouble understanding a step in this proof from my notes, I am looking for any clarification.
Theorem Let $a, b \in \mathbb{Z}$, $b \neq 0$, there exists integers $q, r$ such that $a = qb + r$ where $0 \le r \lt |b|$. And $q$ and $r$ are uniquely determined.
The proof only deals with the case $b \gt 0$, but it states:
Consider the set $S = \{a - bx: x \in \mathbb{Z}, a - bx \ge 0\}$. Then this set is non empty because if $a \gt 0$ we just take $x = 0$ and hence $a \in S$.
Here is where I am a bit confused, it then says, if $a \lt 0$ take $x = a$ and $a - bx = a(1 - b) \ge 0$ (because $b \gt 0$ and so $b \ge 1$) That is, $a(1-b) \in S$.
And then it continues, but I don't understand this last step. How does $b$ being greater than $0$ imply it is greater or equal to $1$? How do we know that? What if $b$ was $0 \lt b \lt 1$ then $a(1 - b)$ would not be in $S$ because $a \lt 0$.
Can anyone please help to explain? Thanks.
$b$ cannot be in the interval $(0,1)$. It is an integer
Because $a - xb \geq 0$, if $x = a$ and $a<0$, then $b$ must be $\geq 1$ in order for the subtraction $a - bx$ to be positive or zero. If $b$ was $0$ then since $a$ is negative it is less than $0$.