Least integer principle: Every non-empty set of positive integers has a least element.
Using this fact, define $r$ to be the least integer for which $j - qk > 0$ where $j, k \in \Bbb{Z}$ and $k > 0$. Prove $0 < r \leq k$.
Assume $r = k$. Then $j - qk = k$, but this is $j - k(q+1) = 0$. So $j - qk$ is positive if $k = r$.
Assume $k < r \leq mk$ where $m$ is the integer number that satisfies $j - mk \leq 0$. Then $j - qk = (m-1)k + r'$ where $r' \leq k$. Let $q + m - 1 = q'$. Then $j - kq' = r'$. But $j - kq' > 0$ still, so $r'$ must be the least integer and not $r$.
Assume $r < 0$. Then $j - qk < 0$, but that's impossible by our definition.
Thus $0 < r \leq k$. QED
Anything I could have made clearer?
$\endgroup$ 11 Answer
$\begingroup$Don 1) When you assumed $r=k$ There is no manipulation needed $j-qk$ is automatically $>0$ since $k>0$.
2) When you assumed $k<r\leq mk$, must it be so for $r$? Why can't $r>mk$ be?
I will write my approach only because I am confused by yours. Not saying you are wrong. I think we are learning from the same book.
First we define the set of integers ,$q$, that will give us $j-qk>0$ for some given $j,k(k>0)$. Let $S=\{q\in \mathbb{Z}| j-qk>0, k,j\in \mathbb{Z}, k>0\}$.
Then, let $\mathbb{L}=\{r\in \mathbb{Z}^+|j-qk=r, q\in \mathbb{S}, k,j\in \mathbb{Z}, k>0\}$//the set of all possible values for $r$.
We want to show that if $r\in\mathbb{L}$ is | $∀c\in \mathbb{L}$, $r\leq c$, then $0<r\leq k$.
Note that $k\in \mathbb{L}$ is possible, but not guaranteed. If $k$ had to be in $\mathbb{L}$, we would have been done since any integer $>k \in \mathbb{L}$ would not have been the least.
Let $G=\{b\in \mathbb{L}| b>k, k\in \mathbb{Z}, k>0\}$/the set of all possible values in L greater than k\. let $c$ be the least integer in G. Then, ∃ $q\in S$ |$j-qk=c$, $\Longrightarrow$ $j-qk>k$ $\Longrightarrow$ $(j-qk)-k>0$ $\Longrightarrow$ $j-(q-1)k>0$. Now let $c'=j-(q-1)k$, then $c'\in \mathbb{L}$ and $c'<c$.
So in the set $\mathbb{L}$ ∃ $c'<c$ (the smallest integer in L that is greater than k). So $c'\leq k$. So if r is the least integer in L, then $r\leq c'\leq k$. QED
$0<r$ is obvious if not given.
$\endgroup$ 2
