# help with division algorithm proof

I'm a very newbie, even if I studied some math at college... Now I'm trying to study "Contemporary Abstract Algebra", by J.A. Gallian but I'm already facing some difficulties trying to understand the proof of the very first theorem (0.1) about division algorithm.

The theorem says:

Let a and b be integers with $b > 0$. Then there exist unique integers q and r with the property that $a=bq + r$, where $0\le r\le b$

Trying to proof the existence part of the theorem, author writes:

Consider the set $S =\{a - bk | k\text{ is an integer and }a - bk\ge 0\}$. If $0\in S$, then $b$ divides $a$ and we may obtain the desired result with $q =\tfrac ab$ and $r = 0$. Now assume $0\notin S$. Since $S$ is nonempty [if $a > 0$ then $a - b\times0\in S$ and if $a < 0$ then $a - b(2a) = a(1 - 2b) \in S$; and $a\neq0$ since $0\notin S$]...

Ok, my question is: why author put $k = 2a$ when explain why S is non empty with $a < 0$? Where does this $k = 2a$ come from? Why can't be $k=a$, for example?

Thanks a lot

• You can take also $k=a$, but then if $b=1$ then $a-kb=0$ and you assumed that $0\not \in S$. Hence he took $k=2a$ in order to get a sharp inequality $a-bk>0$. – Ofir Schnabel Oct 26 '15 at 10:52
• I think that your $E$'s should be $\in$ (in LaTeX \in), is that correct? – Michael Burr Oct 26 '15 at 10:53
• Yes you're right, I'm sorry I'm still not so good at using it. – Huseyin78 Oct 26 '15 at 16:55

## 1 Answer

The author chose $k=2a$ because for the most obvious choice $k=a$ there is a problem: If $b=1$ then $a-b\times a=0$, which is not in $S$.

For $k=2a$ we have $a-b\times2a=a(1-2b)\in S$ because certainly $1-2b<0$. So this does show that $S$ is nonempty.