2 ms·

As I learned recently, there is actually a good reason why gcd(a, b) is often abbreviated as (a, b). Roughly speaking, in ring theory, an ideal I is some subset

As I learned recently, there is actually a good reason why gcd(a, b) is often abbreviated as (a, b). Roughly speaking, in ring theory, an ideal I is some subset of a ring (which you can think of as a number system, sorta) for which ai is in I (if a is any element of the ring and i is in I). Given any element x, we can generate an ideal from x by just taking every other y in the ring and computing yx - if every yx is in the ideal, then multiplying by some other z to get zyx is the same as just having (zy)x ,which is just a different multiple of x. This ideal - the ideal generated by x - is written as (x); if it's generated by multiple elements, it's written as (x1, x2, ...). If you consider the ring of the integers, then the ideals are multiples of some integer. For instance, the multiples of three are an ideal, because multiplying a multiple of three by any integer yields a multiple of three (so if you multiply the set of multiples of three by any integer, you just get back something that's in the ideal). The final point is this: the ideal generated by two integers is actually just the set of multiples of their gcd. Therefore, if a and b are integers, (a, b) is the set of multiples of their gcd - just like (3) is the set of multiples of three. This is why the gcd is often written in this way. The cool thing is that this works in rings in general, not just integers. You can extend the concepts of gcd, primality, divisibility, etc to rings in general, and operate on things besides just integers, such as matrices, polynomials, or rotations of a cube. For more info: http://en.wikipedia.org/wiki/Ring_theory http://en.wikipedia.org/wiki/Ideal_(ring_theory)

tel 13y ago
This is a great counterexample to those that decry mathematical notation. Ambiguity may not be introduced for raw efficiency, but instead to indicate powerf techniques through punning.
- vog 13y ago
  The same holds not just for math symbols but also for math names. Many things have similar/same names because there is a deep mathematical connection that justifies the conflation.
  - ErsatzVerkehr 13y ago
    And just as often the names are totally arbitrary.
vog 13y ago
> You can extend the concepts of gcd, primality, divisibility, etc to rings in general Thats true, but you have a "real" GCD only in special types of rings (principal ideal domains). In other rings, you only have Ideals as rough generalization of GCDs. > Therefore, if a and b are integers, (a, b) is the set of multiples of their gcd - just like (3) is the set of multiples of three. To make this more clear, in the notation of Ideals, you can write this: (15,6) = (3) That is, the Ideal generated by 15 and 6 is same as the Ideal generated by 3. And for nonnegative integers, this essentially means the same as saying that 3 is the GCD of 15 and 6: gcd(15,6) = 3 There is still some "unclean" step involved here (that is, identifying numbers by their principal ideal, i.e. treating 3 and (3) as if these were equal), but I think this justifies the notation nevertheless.
- PieSquared 13y ago
  You're is exactly right. To add to what you were saying and expand a little bit: A principal ideal domain is a ring in which every ideal is generated by only one element, so whenever we see (a, b), we know there is some element c such that (a, b) = (c). I think this is what vog meant by having a "real" GCD - only in a principal ideal domain is your gcd unique. Without uniqueness, we can still define a greatest common divisor such that if gcd(a, b) = g, we know that there is nothing we can multiply by g to get a divisor of both a and b; that is, there's no extra factor we can add to g in order to get another factor of both a and b. That is enough to call g a GCD - but it's not necessarily unique! It turns out that in rings which aren't principal ideal domains, you can have more than one GCD! It's bizarre to think exactly what "greatest" means in this context, but you can also just think of it as "can't add any more factor while still dividing both a and b". Ring theory is fun! (And practical, sometimes - you can describe some algorithms very elegantly via embedding the things you're working with in unusual rings.) More info, with some examples and counterexamples: https://en.wikipedia.org/wiki/Principal_ideal_domain

tel 13y ago

This is a great counterexample to those that decry mathematical notation. Ambiguity may not be introduced for raw efficiency, but instead to indicate powerf techniques through punning.

vog 13y ago
The same holds not just for math symbols but also for math names. Many things have similar/same names because there is a deep mathematical connection that justifies the conflation.
- ErsatzVerkehr 13y ago
  And just as often the names are totally arbitrary.

vog 13y ago

> You can extend the concepts of gcd, primality, divisibility, etc to rings in general Thats true, but you have a "real" GCD only in special types of rings (principal ideal domains). In other rings, you only have Ideals as rough generalization of GCDs. > Therefore, if a and b are integers, (a, b) is the set of multiples of their gcd - just like (3) is the set of multiples of three. To make this more clear, in the notation of Ideals, you can write this: (15,6) = (3) That is, the Ideal generated by 15 and 6 is same as the Ideal generated by 3. And for nonnegative integers, this essentially means the same as saying that 3 is the GCD of 15 and 6: gcd(15,6) = 3 There is still some "unclean" step involved here (that is, identifying numbers by their principal ideal, i.e. treating 3 and (3) as if these were equal), but I think this justifies the notation nevertheless.

PieSquared 13y ago
You're is exactly right. To add to what you were saying and expand a little bit: A principal ideal domain is a ring in which every ideal is generated by only one element, so whenever we see (a, b), we know there is some element c such that (a, b) = (c). I think this is what vog meant by having a "real" GCD - only in a principal ideal domain is your gcd unique. Without uniqueness, we can still define a greatest common divisor such that if gcd(a, b) = g, we know that there is nothing we can multiply by g to get a divisor of both a and b; that is, there's no extra factor we can add to g in order to get another factor of both a and b. That is enough to call g a GCD - but it's not necessarily unique! It turns out that in rings which aren't principal ideal domains, you can have more than one GCD! It's bizarre to think exactly what "greatest" means in this context, but you can also just think of it as "can't add any more factor while still dividing both a and b". Ring theory is fun! (And practical, sometimes - you can describe some algorithms very elegantly via embedding the things you're working with in unusual rings.) More info, with some examples and counterexamples: https://en.wikipedia.org/wiki/Principal_ideal_domain