Re: [math-fun] "greatest", "least"

28 Nov 2013

      The greatest common divisor is *not* the *largest* element d such that
d|a and d|b. (That is meaningless in unordered Euclidean domains.)

Likewise for lowest common multiple.

So, in the integers, gcd(12,18) is 6 or -6, which are considered to
be the same thing for this purpose (since they are associates).
Similarly, in the Gaussians, gcd(5, 2+i) = 2+i, 2i-1, -2-i or -2i+1,
which are associates (differ by multiplication by a unit).

Sincerely,

Adam P. Goucher
...
----- Original Message -----
From: James Propp
Sent: 11/28/13 02:49 PM
To: math-fun
Subject: Re: [math-fun] "greatest", "least"
While we're discussing such matters, perhaps we should consider whether the
"lowest common denominator" of two or more fractions has been properly
defined.
Most math teachers will tell you that the lowest common denominator of the
fractions 5/12 and 11/18 is 36. But what about -36, which is lower? Or
-72, which is lower still?
Clearly the lowest common denominator of any set of fractions is minus
infinity.
And don't tell me that -72 is "higher" than -36, citing Joe Silverman or
some other deluded arithmetician; any Alaskan meteorologist can tell you
that -72 is much lower than -36.
Jim Propp
On Thursday, November 28, 2013, Bill Gosper <billgosper@gmail.com> wrote:
...
Bill Gosper wrote:
If your developers are leery of GCD[1,π]→0, I think I can muster
authoritative corroborators, if not corroborative literature.
Motivation: The gcd of two real quantities is the largest quantity
that goes into each a whole number of times.
[me:]
I'm unconvinced. In this context (multiplicative rather than
additive) 0 is *larger* than everything else, not *smaller*,
no?
[Bill:]
Well, we *are* looking for the "greatest".-) Do you propose a different
answer, or deny there is one?
...
I deny there is one, or at least that there is any number
that has a good claim.
Please name one.
...
...
...
And 0 emphatically doesn't "go into" anything "a whole
number of times".
...
...
Touché. New wording:
GCD(a,b):= the limit of the Euclidean process of iteratively
subtracting the smaller from the larger.
...
The *limit* of doing this for commensurable quantities is zero.
The gcd is the last thing you get immediately before 0.
n[755]:= NestList[
Simplify[{Max[#] - Min[#], Min[#]}] &, {GoldenRatio - 1/2, 1/√5}, 6]
Out[755]= {{-(1/2) + GoldenRatio, 1/√5}, {3/(2 √5), 1/√5}, {1/(2 √5),
1/√5},
{1/(2 √5), 1/(2 √5)}, {0, 1/(2 √5)}, {1/(2 √5), 0}, {1/(2 √5), 0}}
So GCD[GoldenRatio - 1/2, 1/√5] is 1/(2√5)
In[758]:= NestList[Simplify[{Max[#] - Min[#], Min[#]}] &, {69, 105}, 16]
Out[758]= {{69, 105}, {36, 69}, {33, 36}, {3, 33}, {30, 3}, {27,
3}, {24, 3}, {21, 3}, {18, 3}, {15, 3}, {12, 3}, {9, 3}, {6, 3}, {3,
3}, {0, 3}, {3, 0}, {3, 0}}
So GCD[69,105] is 3.
In[761]:= NestList[Simplify[{Max[#] - Min[#], Min[#]}] &, {1, π},
3 + 7 + 15 + 1]
Out[761]= {{1, π}, {-1 + π, 1}, {-2 + π, 1}, {-3 + π, 1}, {4 - π, -3 + π},
{7 - 2 π, -3 + π}, {10 - 3 π, -3 + π}, {13 - 4 π, -3 + π},
{16 - 5 π, -3 + π}, {19 - 6 π, -3 + π}, {22 - 7 π, -3 + π},
{-25 + 8 π, 22 - 7 π}, {-47 + 15 π, 22 - 7 π}, {-69 + 22 π, 22 - 7 π},
{-91 + 29 π, 22 - 7 π}, {-113 + 36 π, 22 - 7 π}, {-135 + 43 π, 22 - 7 π},
{-157 + 50 π, 22 - 7 π}, {-179 + 57 π, 22 - 7 π}, {-201 + 64 π, 22 - 7
π},
{-223 + 71 π, 22 - 7 π}, {-245 + 78 π, 22 - 7 π}, {-267 + 85 π, 22 - 7
π},
{-289 + 92 π, 22 - 7 π}, {-311 + 99 π, 22 - 7 π}, {-333 + 106 π, 22 - 7
π},
{355 - 113 π, -333 + 106 π}}
In[762]:= N[%]
Out[762]= {{1., 3.14159}, {2.14159, 1.}, {1.14159, 1.}, {0.141593,
1.}, {0.858407, 0.141593}, {0.716815, 0.141593}, {0.575222,
0.141593}, {0.433629, 0.141593}, {0.292037, 0.141593}, {0.150444,
0.141593}, {0.00885142, 0.141593}, {0.132741, 0.00885142}, {0.12389,
0.00885142}, {0.115038, 0.00885142}, {0.106187,
0.00885142}, {0.0973355, 0.00885142}, {0.0884841,
0.00885142}, {0.0796327, 0.00885142}, {0.0707813,
0.00885142}, {0.0619298, 0.00885142}, {0.0530784,
0.00885142}, {0.044227, 0.00885142}, {0.0353756,
0.00885142}, {0.0265241, 0.00885142}, {0.0176727,
0.00885142}, {0.00882128, 0.00885142}, {0.0000301444, 0.00882128}}
So GCD[1, π] is going to 0.
Gareth>I agree that gcd(1,pi) can be thought of as a certain sort of
...
limit of real numbers that tend to 0 -- but I don't think the
usual sort of limit is the right one, because the metric it
implicitly invokes isn't the right one.
--
g
What's the right one?
The smallest square you can make by dividing a rectangle into
squares by the greedy algorithm is GCD(length,width). What could
be more natural?
--rwg
_______________________________________________
math-fun mailing list
math-fun@mailman.xmission.com
http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________
math-fun mailing list
math-fun@mailman.xmission.com
http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Adam P. Goucher

tags

participants (1)