News for hackers. Stuff that matters.
Re:Math Bite: Irrationality of √m (1999) by brlewis on Wednesday December 23, 2015 @11:29AM (#10784040)
> We may assume that q is as small as possible (Estermann's key idea)

Making the denominator as small as possible uses divisibility.

Re:Math Bite: Irrationality of √m (1999) by jfarmer on Thursday December 24, 2015 @11:47PM (#10790446)
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

Re:Math Bite: Irrationality of √m (1999) by brlewis on Monday December 28, 2015 @02:37PM (#10802895)
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.

Re:Math Bite: Irrationality of √m (1999) by fluxion on Wednesday December 23, 2015 @01:30PM (#10784774)
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.

Re:Math Bite: Irrationality of √m (1999) by brlewis on Wednesday December 23, 2015 @03:54PM (#10785575)
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.