# GCD of rationals

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 :-)

• @WillieWong - Why did you remove the [GCD] tag? Because it's a new one? But it is about GCD, and the [GCD] tag may help people who're looking for information. Commented May 29, 2012 at 11:25
• the gcd tag is too specific and too broad at the same time (it is about a particular operation which has interpretation in many different levels/specialties of mathematics). And any question about gcd will have the phrase "gcd" or "greatest common denominator" in the question body, which can be easily found using the search function. Commented May 29, 2012 at 11:44
• To illustrate: math.stackexchange.com/search?q=gcd returns over 1000 questions about greatest common denominators in different contexts. It is much more useful to use the tags to help specify in which context your question about gcd is asked. Commented May 29, 2012 at 11:46
• Since you are an engineer: Think about the numbers as representing some quantities. Divide your unit in smaller units so that both quantities become integers. Apply the gcd, and then switch back to the original unit....This is exactly what Greek's understanding mentioned in Andre's answer means.... Commented May 31, 2012 at 8:27
• See here for a strikingly simple proof of the irrationality of $\,\sqrt{2}\,$ using gcds of rationals. Commented Feb 28, 2015 at 17:05

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.

• Thanks for the Wolfram Alpha reference too. Interesting site, though I guess you guys would use Mathematica. Also gives additional information like series representation and prime factorization. I took the liberty of adding a link to it. Commented May 31, 2012 at 7:56
• I use maxima which is free, cross-platform, and returns $\gcd(3/7,12/22)=3/77$ as expected. Commented Mar 5, 2016 at 18:30

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.

• Right: The Greeks didn't think of A mod B; they thought of "the line segment left over when you start with a line segment of length A and subtract as many line segments of length B as possible".
– Dan
Commented May 29, 2012 at 14:09
• "Greek mathematicians were more at ease with geometry than with numbers" isn't a very precise statement of the matter to say the least. Numbers, i.e. 2,3,4,5,6,... were something Euclid was quite comfortable with; he used the word "arithmoi" frequently. The Greeks had no concept at all of what we now call "real numbers". That's not just "discomfort" with them. They had a concept of congruence of line segments; they had a concept of laying a specified number of segments end to end; the had a concept of the ratio of two lengths being the same as.... Commented May 29, 2012 at 17:48
• ....another ratio of two lengths even when the ratios were of incommensuable pairs of segments, etc. They could multiply two lengths and get an area. But you couldn't say the area was greater than or less than or equal to any particular length: these were not real numbers. Commented May 29, 2012 at 17:49
• Euclid presents his algorithm in Propositions 1 and 2 of Book VII of the Elements, see aleph0.clarku.edu/~djoyce/java/elements/bookVII/bookVII.html Commented May 30, 2012 at 7:51
• He is talking about numbers here, not lengths. He needs two propositions, one for the case of relatively prime numbers and one for the greatest common measure of two numbers that are not relatively prime, because for the Greeks $1$ was not a "number". Commented May 30, 2012 at 7:54

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.

• I don't follow- $\mathbb Q$ is a field. What is the meaning of $gcd(x,y)$ where $x,y$ are members of a field ? Commented May 30, 2012 at 4:10
• @Kuashik As mentioned in the first paragraph, divisibility is w.r.t. to a specified subdomain Z of "integers". In an integral domain, $\rm\:d = gcd(a,b)\:$ is a greatest common divisor of $\rm\:a,b\:$ if it is a common divisor $\rm\:d\:|\:a,b\:$ that is (divisibly) greatest, i.e. divisible by every common divisor, i.e. $\rm\: c\:|\:a,b\Rightarrow c\:|\:d.\:$ Said more universally $\rm\:c\:|\:a,b\iff c\:|\:gcd(a,b),\:$ analogous to $\rm\:c\le a,b\iff c\le min(a,b).\:$ See here for more on such universal definitions of GCD and LCM. Commented May 30, 2012 at 4:31
• @ Bill Dubuque: There should be a sense of ordering in a Integral Domain otherwise no one can say which one is greater among $x,y$ where $x,y$ are members of an Integral Domain. In a field except additive identity (usually we say $0$) "everyone divisible by everyone". So in that sense, I can say $gcd(\frac{13}{2},\frac{3}{4})=100$ or $1000$.... I have doubt that's why I am asking don't get angry Commented May 30, 2012 at 4:47
• @Kuashik The (partial) order is that given by divisibility, as I said. This is the standard definition of gcd in a general integral domain. It specializes to the well-known definition in $\mathbb Z$ (or any Euclidean domain). Again, the divisibility relation used in $\mathbb Q$ is the natural extension of integer divisibility - see the first paragraph of my answer. Commented May 30, 2012 at 4:53
• @ Bill Dubuque: Yes, any Integral domain $R$ has natural partial order (antisymmetric, antireflexive, transitive) say $x\leq y\iff \exists$ non unit $c\in R$ such that $y=cx$. Then one can talk about chain and one can talk about $gcd(x,y)$ where $x,y\in R$ Commented May 30, 2012 at 5:19

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)