Be forewarned - the following is a pedagogical presentation of really simple stuff and you might not be interested.
Since I posed the question, let me provide one such definition.
Assume both $m$ and $b$ are in $\mathbb{N}$ with $b > 0$.
We can assert the following for $\mathbb{N}$:
Archimedean Property: The set $\mathcal {Q_b}^m\;$ :$\,\{q^`$ with $m \ge q^`b\}$ is a finite interval $[0,\; q]$.
Definition: The set $\mathcal {Q_b}^m$ is called "division of $m$ by $b$".
Definition: The largest number $q$ in $\mathcal {Q_b}^m$ is called "the quotient of division of $m$ by $b$".
Proposition 2: $r = m - qb$ is in $\mathbb{N}$ and must also be less than $b$.
Proof: Totally obvious.
Definition: The number $r$ is called "the remainder of division of $m$ by $b$".
Theorem: If $m = q^{'}b + r^{'}$ with $r^{'} < b$, then $q^{'}=q$ and $r^{'}=r$.
Proof: It easy to show that $q^{'}$ is the maximum number in $\mathcal {Q_b}^m$ since $q^{'} + 1$ does not work.
QED
For completeness:
$m$ is called the dividend and $b$ is called the divisor.
There is a variation of the Euclidean algorithm which is "subtractive". In some interpretations, it is what the original algorithm of Euclid was intended to be. The key point is what does it mean for one number to "measure" another? It could mean to repeatedly subtract the smaller number from the larger number. This seems essentially equivalent to your definition. They both do not use division. In Euclid the algorithm was used for "quantities" first and there is no definition of "division" for these. Thus, it indicates that division was not intended for numbers as well.