GCD of rationals

Question

Disclaimer: I'm an engineer, not a mathematician

Somebody claimed that $\gcd$ only is applicable for integers, but it seems I'm perfectly able to apply it to rationals also:

$$ \gcd\left(\frac{13}{6}, \frac{3}{4} \right) = \frac{1}{12} $$

I can do this for a number of cases on sight, but I need a method. I tried Euclid's algorithm, but I'm not sure about the end condition: a remainder of 0 doesn't seem to work here.

So I tried the following:

$$\gcd\left(\frac{a}{b}, \frac{c}{d} \right) = \frac{\gcd(a\cdot d, c \cdot b)}{b \cdot d}$$

This seems to work, but I'm just following my intuition, and I would like to know if this is a valid equation, maybe the correct method. (It is in any case consistent with $\gcd$ over the natural numbers.)

I'm not a mathematician, so please type slowly :-)

Answer 1

In the ancient Greek sense, if we have two quantities $x$ and $y$, then the quantity $z$ is a common measure of $x$ and $y$ if each of $x$ and $y$ is an integer multiple of $z$. The quantities involved were not thought of as numbers, but of course they were what we think of as positive. So for example the diagonal of a square, and the diagonal of a square whose sides are $50\%$ bigger, have a common measure. But some pairs of quantities are incommensurable, like the side and diagonal of a square.

Any two rationals, unless they are both $0$, have a greatest common measure. You are therefore perfectly correct. The two rationals also have a least number that they both measure. So if you had further argued that two rationals, not both $0$, have a least positive common multiple, you would also be right.

Your calculation method is also correct. One brings the two rationals to a common denominator $q$, say as $\frac{x}{q}$ and $\frac{y}{q}$. Then the $\gcd$ is $\frac{\gcd(x,y)}{q}$. You chose the common denominator $q=bd$. Any common denominator will do, and will produce the same $\gcd$.

Most of the standard theorems about $\gcd$ and lcm for integers extend in a straightforward way to results about the $\gcd$ and lcm for rationals. For example, a mild variant of what we nowadays call the Euclidean algorithm will compute the $\gcd$ of two positive rationals. Actually, this variant is the original Euclidean algorithm!

Remark: A number of programs, including Mathematica, accept rationals as inputs to their $\gcd$ function. The same appears to be true of WolframAlpha, which has the great advantage of being freely accessible. One way, perhaps, to (sort of) settle the argument in your favour is to type $\gcd(3/7, 12/22)$ into Alpha. It will, probably, return $\frac{3}{77}$ (it did when I used it). With other rationals, test first, Alpha is not bug-free.

Answer 2

Euclid's algorithm (originally formulated using repeated subtractions rather than divisions) can be applied to any pair of comparable quantities (two lengths, two masses, two frequencies): just keep subtracting the smaller of a pair from the larger and then replace the larger one by the difference found; stop when the difference becomes $0$, returning the smaller (which is now also the larger) retained quantity as GCD. Although I haven't actually read Euclid, I would be surprised if the original formulation wasn't actually in terms of geometric lengths, given that Greek mathematicians were more at ease with geometry than with numbers. The only caveat is that with lengths it is not an algorithm in the sense that it is guaranteed to terminate; two lengths are by definition "commensurable" if the procedure does terminate, and it then returns the largest unit of length for which both intitial lengths are integer multiples. One can easily show (without using any arithmetic) that the procedure does indeed never terminate (because one gets back to the original ratio of lengths, but at a smaller scale) when starting with the lengths of a side and a chord of a regular pentagon (giving the golden ratio) or for a side and a diagonal of a square (ratio $1:\sqrt2$); this is a nice exercise in geometry.

$\qquad$

Now if you apply this to rational numbers, you see there is no problem, since they can be compared, subtracted, and any pair of them is necessarily commensurable (one over the product of the denominators gives common measure, though not necessarily the largest one). Bringing both rational numbers to this common denominator, one sees that the formula you guessed is indeed the correct one. If you have prime factorizations of $a,b,c,d$ available, you can also find the $\gcd(\frac ab,\frac cd)$ by taking every prime number $p$ to a power that is the minimum of the valuations of $p$ in $\frac ab$ and in $\frac cd$, where the valuation in $\frac ab$ is its multiplicity in $a$ minus its multiplicity in $b$ (a possibly negative integer). However your formula combined with Euclid's algorithm for integers (or directly Euclid's algorithm for rational numbers) is a more efficient method of computing.

Added in reply to comment by @Michael Hardy: When I say that the Greek mathematicians were more at ease with geometry than with numbers, I did not mean to say the did not know about numbers, but that they would prefer stating and treating a statement about numbers in geometric terms, quite opposite to our modern tendency to translate geometric problems into numerical terms. A case in point is Euclid's proof of what we would formulate as the infiniteness of the set of prime numbers (he never uses terms "finite" or "infinite", and I don't think these notions were even used at the time, but that is not my point here). I think most people would agree this is a purely number theoretic statement with absolutely no geometric content, yet Euclid states and proves it geometrically (essentially by constructing a least common multiple of a given (finite) set of prime multiples of a given unit length). And for this reason of geometric preference I think it is probably historically inaccurate to use the term "Euclidean algorithm" for a procedure restricted to the case of a pair of positive integers (and therefore assured to terminate) rather than a pair of lengths (which could fail to terminate); however I'll repeat my ignorance of the precise sources here.

Added later Thank you @Robert Isreal for the reference to the translation of Elements. So Euclid operates in his description of his algorithm, in Book VII Propositions 2,3, on numbers, which are integer multiples some unit veiled in mystery ("that by virtue of which each of the things that exist is called one"). Yet the language suggests that numbers are thought of as lengths; if not, why denote individual numbers by $AB$, $CD$, talk about one number measuring another, etc.? Moreover, in book X, Proposition 2 one finds the same procedure, but with numbers replaced by "magnitudes", treated exactly like numbers are (also denoted $AB$ etc.) but with the difference that they need not have a common measure. So rather than the relatively prime/relatively composite distinction, one has a (rather different) commensurable/incommensurable distinction for magnitudes. And in the incommensurable case, during the procedure "that which is left never measures the one before it", implying that the procedure never terminates. Maybe I haven't looked well enough, but it would seem that Euclid isn't very strong in proving the existence of incommensurable magnitudes. The example given (the same one I gave above) doesn't seem to be Euclid's, and Book X, Proposition 10, apart from being non genuine, fails to prove the existence of (integer) ratios that are not the ratio of two square numbers. For instance he does not show (at least not at that proposition) why $1:2$ cannot also be the ratio of two square numbers, even though the proof would be easy.

Answer 3

Yes, your formula yields the unique extension of $\rm\:gcd\:$ from integers to rationals (fractions), presuming the natural extension of the divisibility relation from integers to rationals, i.e. for rationals $\rm\:r,s,\:$ we define $\rm\:r\:$ divides $\rm\:s,\:$ if $\rm\ s/r\:$ is an integer, $ $ in symbols $\rm\:r\:|\:s\:$ $\!\iff\!$ $\rm\:s/r\in\mathbb Z.\: $
[Such divisibility relations induced by subrings are discussed further here]

Essentially your formula for the gcd of rationals works by scaling the gcd arguments by a factor that yields a known gcd (of integers), then performing the inverse scaling back to rationals.

Even in more general number systems (integral domains), where gcds need not always exist, this scaling method still works to compute gcds from the value of a known scaled gcd, namely

$\rm{\bf Lemma}\ \ \ gcd(a,b)\ =\ gcd(ac,bc)/c\ \ \ if \ \ \ gcd(ac,bc)\ $ exists $\rm\quad$

Therefore $\rm\ \ gcd(a,b)\, c = gcd(ac,bc) \ \ \ \ \ if\ \ \ \ gcd(ac,bc)\ $ exists $\quad$ [GCD Distributive Law]

The reverse direction fails, i.e. $\rm\:gcd(a,b)\:$ exists does not generally imply that $\rm\:gcd(ac,bc)\:$ exists. $\ $ For a counterexample see my post here, which includes further discussion and references.

More generally, as proved here, we have these dual formulas for reduced fractions

$$\rm\ gcd\left(\frac{a}b,\frac{c}d\right) = \frac{gcd(a,c)}{lcm(b,d)}\ \ \ if\ \ \ \gcd(a,b) = 1 = \gcd(c,d)$$

$$\rm\ lcm\left(\frac{a}b,\frac{c}d\right) = \frac{lcm(a,c)}{gcd(b,d)}\ \ \ if\ \ \ \gcd(a,b) = 1 = \gcd(c,d)$$

See this answer for the $k$-ary inductive extension of the above gcd formula.

Some of these ideas date to Euclid, who computed the greatest common measure of line segments, by anthyphairesis (continually subtract the smaller from the larger), i.e. the subtractive form of the Euclidean algorithm. The above methods work much more generally since they do not require the existence of a Euclidean (division) algorithm but, rather, only the existence of (certain) gcds.

Answer 4

It is not very efficient, but gcd of two rational numbers can be calculated by a function that goes in a loop, each time replacing the larger of the two numbers by their difference.

gcd(a,b):
if a==b return a
if a > b return gcd(a-b,b)
else return gcd(a, b-a)