Re: [math-fun] More 4th grade math
At 06:26 AM 2/10/2014, Andy Latto wrote:
Do the people who say that 1 is a prime also say that 0 is a composite?
Yes, because gcd(0,n)=|n| for all rational integers n. http://en.wikipedia.org/wiki/Greatest_common_divisor
gcd(0,0) = 0 ??? I always thought a positive integer was prime iff it had exactly two positive integer divisors. On 2014-02-10 09:57, Henry Baker wrote:
At 06:26 AM 2/10/2014, Andy Latto wrote:
Do the people who say that 1 is a prime also say that 0 is a composite? Yes, because gcd(0,n)=|n| for all rational integers n.
http://en.wikipedia.org/wiki/Greatest_common_divisor
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Wikipedia has this to say about gcd(0,0) and lcm(0,0): It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. I don't have Mathematica, but Wolfram Alpha also gives 0 for these. Tom Henry Baker writes:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors.
Common Lisp & Maxima say gcd(0,0)=0.
And, as I recall, many early computers said n/0 = n. If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b). On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
Ok, what do you propose for gcd(0,0) ? At 09:20 AM 2/10/2014, Mike Speciner wrote:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
I propose to leave it undefined, like 0/0 or 0**0. On 2014-02-10 12:23, Henry Baker wrote:
Ok, what do you propose for gcd(0,0) ?
At 09:20 AM 2/10/2014, Mike Speciner wrote:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
What are the rules/axioms/theorems that you want to preserve, and which ones do you want to give up ? At 09:29 AM 2/10/2014, Mike Speciner wrote:
I propose to leave it undefined, like 0/0 or 0**0.
On 2014-02-10 12:23, Henry Baker wrote:
Ok, what do you propose for gcd(0,0) ?
At 09:20 AM 2/10/2014, Mike Speciner wrote:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
Well, I'm clearly giving up anything about gcd(0,0), so it's for all nonzero integers a and b... gcd(a,b) = gcd(a-b,b) gcd(a,b) = gcd(a, b%a) [Euclidean algorithm step] [%=remainder] gcd(a,b) = ua + bv for some integers u and v for all positive integers c, gcd(ac,bc) = c * gcd(a,b) lcm(a,b) * gcd(a,b) = |a*b| gcd(a,b) > 0 [so we can divide anything above by gcd(a,b), e.g., gcd(a/gcd(a,b),b/gcd(a,b)) = 1] What do you get and give up by defining gcd(0,0) = 0 ? I can see that for some algorithms, it's fine to define gcd(0,0)=0 rather than leave it undefined, just as it's fine to define n/0 = n in some cases, but you might sometimes want to throw an exception when you evaluate it so you don't naively wander off into a computation where you end up with garbage. On 2014-02-10 12:32, Henry Baker wrote:
What are the rules/axioms/theorems that you want to preserve, and which ones do you want to give up ?
At 09:29 AM 2/10/2014, Mike Speciner wrote:
I propose to leave it undefined, like 0/0 or 0**0.
On 2014-02-10 12:23, Henry Baker wrote:
Ok, what do you propose for gcd(0,0) ?
At 09:20 AM 2/10/2014, Mike Speciner wrote:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
* Mike Speciner <ms@alum.mit.edu> [Feb 10. 2014 19:01]:
I propose to leave it undefined, like 0/0 or 0**0.
0^0 = 1 as formerly "resolved" on math-fun, earning a warning of RCS :^)
[...]
I try to think of the factorization of integers as multi-sets of primes, with gcd being intersection and lcm being union. I am surprised this gives me absolutely nothing pertinent to this discussion. ... except when setting 0 = 0^1 * 2^oo * 3^oo * ... * prime(k)^oo * ... Wait, the new "prime" 0 kills it with the lcm. So 0 is a prime with the special property, that, um..., ach, forgettaboutit! A new kind of science! Extra sincerely, jj
The proper definition of prime, gcd, and lcm is in terms of ideals. It is only because Z is a PID that an ideal (n), the set of multiples of n, gets confused with the element n. But of course, we can't teach ring theory to 4th graders, at least not in the US public schools. An ideal A divides an ideal B if A contains B. In Z, if a|b then every multiple of b is a multiple of a. "To contain is to divide", quote from Harvey Cohn, Advanced Number Theory. The gcd of ideals is the smallest ideal containing their union. In Z, gcd((m),(n)) = (m,n). In general, gcd((a,b,...), (c,d,...)) = (a,b,c,d,...), which to me justifies the (m,n) notation. The lcm of ideals is their intersection, which is also an ideal. A product AB of ideals A and B is the smallest ideal containing all xy with x in A and y in B. The ideal (0) consists of the single element 0. In taking the gcd of a list of ideals, (0) can be omitted from the list. In Z, gcd((n),(0)) = (n), or gcd(n,0) = n. The gcd of the empty list is (0), since this is the smallest ideal containing the empty set. Thus gcd(0,0) = gcd() = 0. The lcm of any list of ideals containing (0) is (0). In Z, lcm(n,0) = lcm(0,0) = 0. The ideal (1) is the entire integral domain. The gcd of any list of ideals containing (1) is (1). In Z, gcd(n,1) = 1. Similarly, (1) can be omitted from any list in taking lcm, and lcm() = (1). A prime P is a maximal ideal. That is, P is a proper ideal of the entire integral domain R, but there is no ideal lying strictly between P and R. It is the "maximal" condition that denies primality to 1. Mike, I don't understand this: "If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b)." -- Gene
________________________________ From: Henry Baker <hbaker1@pipeline.com> To: ms@alum.mit.edu; math-fun <math-fun@mailman.xmission.com> Sent: Monday, February 10, 2014 9:23 AM Subject: Re: [math-fun] More 4th grade math
Ok, what do you propose for gcd(0,0) ?
At 09:20 AM 2/10/2014, Mike Speciner wrote:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
It's good that you don't understand that statement, because I was multitasking when I wrote it, and it's wrong. --ms On 2014-02-10 14:18, Eugene Salamin wrote:
Mike, I don't understand this: "If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b)."
-- Gene
________________________________ From: Henry Baker <hbaker1@pipeline.com> To: ms@alum.mit.edu; math-fun <math-fun@mailman.xmission.com> Sent: Monday, February 10, 2014 9:23 AM Subject: Re: [math-fun] More 4th grade math
Ok, what do you propose for gcd(0,0) ?
At 09:20 AM 2/10/2014, Mike Speciner wrote:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That's the counterexample for gcd(a,b) = gcd(a-b,b)? It works for a=0, for b=0, for a=b=0, and for a=b: gcd(0,b) = gcd(-b,b) = |b| gcd(a,0) = gcd(a-0,0) = |a| gcd(0,0) = gcd(0-0,0) = 0 gcd(a,a) = gcd(0,a) = |a| Seems to work. I don't see this as the same as defining n/0 to be n. Tom Mike Speciner writes:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
You're right. As Gene pointed out earlier, and I replied, I was wrong--there's no counterexample. On 2014-02-10 19:07, Tom Karzes wrote:
That's the counterexample for gcd(a,b) = gcd(a-b,b)? It works for a=0, for b=0, for a=b=0, and for a=b:
gcd(0,b) = gcd(-b,b) = |b| gcd(a,0) = gcd(a-0,0) = |a| gcd(0,0) = gcd(0-0,0) = 0 gcd(a,a) = gcd(0,a) = |a|
Seems to work. I don't see this as the same as defining n/0 to be n.
Tom
Mike Speciner writes:
And, as I recall, many early computers said n/0 = n.
If gcd(0,0) = 0, then it is not universally true that gcd(a,b)=gcd(a-b,b).
On 2014-02-10 11:06, Henry Baker wrote:
At 07:08 AM 2/10/2014, Mike Speciner wrote:
gcd(0,0) = 0 ???
I always thought a positive integer was prime iff it had exactly two positive integer divisors. Common Lisp & Maxima say gcd(0,0)=0.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Eugene Salamin -
Henry Baker -
Joerg Arndt -
Mike Speciner -
Tom Karzes