3 ms·

> We may assume that q is as small as possible (Estermann's key idea) Making the denominator as small as possible uses divisibility.

• fluxion 11y ago
  Not necessarily. Strictly mathematically a (non-negative) fraction q/p is just the equivalence class of all non-negative integer pairs (s, t), t != 0, such that 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.
  • brlewis 11y ago
    By the same reasoning, divisibility does not use divisibility. Instead of asking if x is divisible by y you create a set of all products of the form ny where n is an integer, then check to see if x is a member of that set. I don't buy it. qt = sp looks too much like x = ny to me.
• jfarmer 11y ago
  No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. 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). [1]: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
  • brlewis 11y ago
    alpha = p/q where p and q are positive integers. It's finding the set of all possible q that uses divisibility, not finding the least member of that set.