And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction).
It's finding the set of all possible q that uses divisibility, not finding the least member of that set.
qt = sp
As such we may make q as small as possible by finding a representative in the equivalence class where the numerator is smallest (using the well ordering principle of the of the natural numbers). You can identify this pair uniquely (when the fraction is not 0) by using divisibility but that isn't required here.
I don't buy it. qt = sp looks too much like x = ny to me.
Making the denominator as small as possible uses divisibility.