Proof the quotient and remainder exists in $\mathbb{Z}^+$. If $a$ and $b$ are positive integers, prove that there exists an integer $q$ called 
the quotient and an integer $r$ called the remainder such that $a = q b + r$ and
$0 \leq r &lt; b$.

I've seen proofs for this problem and I have been given a solution using induction but I've half thought of a proof that seems much simpler but I'm not sure if it is correct.

There are 3 cases, case 1 and 2 are simple so I'll only half prove case 3.

Case 1: $a=b$ 

Case 2: $a &lt; b$

Case 3: $b&lt;a$. Then there exists an integer $q=gcd(a,b)$. This step worries me since we use the above theorem to calculate the $gcd$ but I don't think the above theorem says anything about its existence. So even without the theorem above we can be sure of its existence. Therefore we can let $r=a-gcd(a,b)b$. So if I could prove $0\leq r &lt; b$ would the proof be correct?
Hint: prove the statement by induction on $a$.

The case $a=0$ is easy. Suppose the statement holds for $a$ and try it for $a+1$. By inductive hypothesis
$$
a=bq+r
$$
with $0\le r&lt;b$. Then $a+1=bq+(r+1)$, but $r+1$ might fail to be less than $b$: when?
Alternately, given $a,b &gt; 0$, you can consider the set $S = \{a - bq : q \in \mathbb{Z}, a - bq \geq 0\}$. This set is nonempty, and thus has a least element by the Well-Ordering Principle. Call this least element $r$.

It is now very easy to prove that $r$ satisfies the desired inequality (otherwise, it wouldn't be the least element in $S$) and this gives you your unique $q,r$. $\diamondsuit$