# Extending greatest common divisors across the rationals.

The purpose of this article is to examine one possible extension of greatest common divisor (or highest common factor) from elementary number properties. The article may be of interest to teachers and students of the Australian Curriculum: Mathematics, beginning with Years 7 and 8, as described in the content descriptions for Number and Algebra. The senior secondary curriculum makes no specific mention of greatest common divisor, but the article is nevertheless a good resource for revisiting with students at this level the concepts of greatest common divisor and lowest common multiple in greater depth, and with a view to critical thinking. Certain concepts and problems can be used even in post-secondary instruction. In particular, teachers may find it useful in designing projects for guided self-discovery or collaborative learning. The article is written as a hybrid: part guided discovery, and part exposition of interesting results and applications. Teachers who enjoy factorisation of positive integers and the concepts of divisor and multiple will hopefully find this content useful and meaningful in making connections of those concepts with fractional numbers. Sample problems and exercises are presented at the end of the article as self-tests and as vehicles for student investigations. Innovative teachers can also formulate their own conjectures and examples.The following word problem (e.g., Pirnot, 2007, p. 252, Problem 77) is typical of a collection of problems found in courses having a component unit in elementary number theory, especially with regard to number relationships among the positive integers.

Problem A: The Tiling Problem

What is the size of the largest possible square tile which can be used to cover the floor of a room 8 metres long and 6 metres wide, without altering or cutting any tiles?

This problem may be used as a simple application of greatest common divisor (GCD) of two positive integers. The greatest common divisor (highest common factor), or GCD, of two positive integers a and b is the largest positive integer that is a factor of both a and b (see Burton, 2002, p. 21). In this particular case, since the GCD of 8 and 6 is 2, we would be confident in giving an answer of a tile measuring 2 metres by 2 metres.

With closer examination of the problem, teachers and students might be tempted to ask further questions, such as the following.

* Question 1 (tile dimension): Must the dimension of the tile be given in whole numbers? For example, could a square tile with side length 2.5 metres work?

* Question 2 (room dimension): What if the dimensions of the room are not given in whole numbers? For example, suppose the room measured 8 metres long by 5.8 metres wide. Can we, and how do we, apply the concept of GCD in this case?

In the case of the tile dimension question with regard to Problem A, a tile of dimension 2.5 metres, for example, will not work because 8/2.5 is not a whole number, and we are not allowed to alter tiles. But are we sure that no other non-integer dimension works?

For the room dimension question, we can convert the dimensions of the room to 80 decimetres by 58 decimetres. Now we have positive integers again, and the GCD applies. But suppose we do not wish to make conversions, or suppose in some applications conversions are not easily seen or are not easily feasible? Can the problem still be solved?

On this note, we extend the domain of GCD from pairs of positive integers (the set [Z.sup.+] x [Z.sup.+]), to pairs of fractions or rational numbers (the set [Q.sup.+] x [Q.sup.+]). Here [Z.sup.+] and [Q.sup.+] denote the sets of positive integers and positive rational numbers, respectively. When we have accomplished this extension, word problems similar to Problem A involving GCD can be handled without number conversion or alteration. Below is a proposed definition for the GCD of two fractional numbers.

The greatest common rational divisor of two positive rational numbers x and y, written GCRD(x, y) is the largest positive rational number r such that both x/r and y/r are positive integers.

We use the abbreviation GCRD to distinguish the greatest common (rational) divisor of two positive rational numbers from the GCD, or greatest common divisor, of two positive integers. Also s|t (s rationally divides t) means that t/s is a positive integer with t and s rational but not necessarily integer. For example, 1/4 | 3/2 because the result of dividing 3/2 by 1/4 is the integer 6. On the other hand, 2/7 does not divide 3/5, written 2/7 | 3/5, because dividing 3/5 by 2/7 does not result in an integer.

Let us briefly return to Problem A Question 1 (room dimension). Notice that with the dimensions proposed in the question, 8 and 5.8 = 29/5, the fraction 1/5 rationally divides both 8 and 5.8, and so 1/5 metre is a plausible answer. But are there other rational divisors? Is 1/5 the greatest common rational divisor? What if the room dimensions change to 8.1 and 8 [1/3] metres?

We begin with the question: Is GCRD(x, y) well-defined for positive rational numbers x and y?

In other words, can two positive rational numbers have a common divisor? In that case, does a largest such divisor exist? To answer these questions, we first give a discovery-based argument for finding the GCRD of two positive rational numbers.

Consider the two positive rational numbers a/b and c/d with positive integers a, b, c and d. Clearly 1/bd is a common rational divisor of a/b and c/d. We would like to note that, unlike with integers, the set of common divisors of any two positive rational numbers is an infinite set, since 1/bdn is a common rational divisor of a and c/d. for any natural number n. To find the GCRD of a/b and c/d we start with the common rational divisor 1/bd and find the largest integer k such that k/bd is also a common divisor. This means we seek the largest integer k such that k/bd | a/b and k/bd | c/d, or equivalently k | ad and k | bc. Then by definition we have that k is the greatest common divisor of ad and bc. Thus, our candidate for the GCRD of a/b and c/d is [GCD (ad,bc)/bd]. For example, our candidate for the GCRD of 2/3 and 3/4 is [GCD (8,9)]/12 = 2. Indeed, [2/5]/[1/12] = 8 and [3/4]/[1/12] = 9, with GCD(8, 9) = 1. But does our answer change if the given fractions are not in lowest terms? For example, 2/3 may be alternately expressed as 4/6 and 3/4+ as 15/20. Is [GCD (4 x 20, 6 x 15)]/[6 x 20] still equal to 1/12? Direct calculation shows, "Yes!" Result 1 further below will explain why.

For Problem A, notice that we propose

GCRD(8,5.8) = GCRD ([8/1], [29/5]) = [GCD ([8 x 5], [1 x 29])]/[1 x 5] = [1/5]

One way of confirming this speculation is to indeed convert to decimetres and calculate GCD(80, 58) = 2 decimetres = 1/5 metre.

To now substantiate our choice for GCRD in general, we consider the function G defined by G(a, b, c, d) = [GCD(ad, bc)/bd] and establish a property of G. The numbers a, b, c, d are positive integers.

En route to a formulation for GCRD by means of the function G, think of a and b (likewise c and d) as the numerator and denominator, respectively, of a rational number. Result 1 below states that the function G gives identical output on pairs of equivalent fractions.

To verify this result, we use the fact that the GCD of positive integers is 'distributive': that is, for every positive integer m, GCD(m x a, m x b) = m x GCD(a, b), which can be shown directly from the definition of greatest common divisor of integers.

Result 1

G(a, b, c, d) = G(a', b', c', d') whenever a/b = a'/b' and c/d = c'/d'.

For suppose a/b = a'/b' and c/d = c'/d', where each variable represents a positive integer.

Then, ab' = a'b and cd = c'd. So:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The function G has been defined on quadruples of positive integers. Result 1 points out that if quadruples are considered as two 'pairs', then G is unchanged when those pairs represent equivalent fractions.

A formula for rational GCD

Result 1 now enables us to think of G as a 'well-defined' function on [Q.sup.+] x [Q.sup.+] (pairs of fractional numbers) as G ([a/b], [c/d]) = [GCD (ad,bc)/bd] With this context, we show G is the greatest common rational divisor of any two positive rational numbers.

Result 2

If a, b, c and d are positive integers, then GCRD(a/b, c/d) = [GCD (ad,bc)/bd].

We first show [GCD(ad,bc)/bd] is a common rational divisor of both a/b and c/d. Secondly, we show there is no larger common divisor.

Suppose a, b, c and d are positive integers. Then

(a/b)/(GCD (ad,bc)/bd) = [a/b] x [bd/GCD (ad, bc)] = ad/GCD (ad,bc)

which is an integer. Therefore (GCD (ad,bc/bd)/bd) | (a/b).

Similarly,

(c/d)/(GCD (ad,bc)/bd) = [c/d] x [bd/GCD (ad,bc)] = [bc/GCDv (ad,bc)]

also an integer, so that (GCD (ad,bc)/bd) | (c/d). So [GCD (ad,bc)/bd] is a common rational divisor of a/b and c/d. Now we show every common positive rational divisor of a/b and c/d is less than or equal to [GCD (ad,bc)/bd]. Assume e/f | a/b and e/f | c/d for some positive integers e and f. Then e/f x m = a/b and e/f x n = c/d for some integers m and n. Therefore, bem = af which implies be | af; thus, bde | adf. Likewise, den = cf implies bde | bcf. Hence, bde [less than or equal to] GCD(adf, bcf), or bde [less than or equal to] f x GCD(ad, bc), which gives e/f [less than or equal to] [GCD (ad,bc)/bd]. (In fact, e/f rationally divides [GCD (ad,bc)/bd] since bde divides GCD(adf, bcf) = f x GCD(ad, bc).) So we can now infer from the proof of Result 2 that every common rational divisor of x and y rationally divides GCRD(x, y).

For example, GCRD (4/15, 8/9) = [GCD (4 X 9, 15 X 9)/15 X 9] = 12/135 = 4/45, which means 4/45 is the largest rational number that is a 'factor' of both 4/15 and 8/9, as defined in the Introduction.

Note that by Result 1 our formula for GCRD does not require rational fractions to be in reduced form. Furthermore, this formula is a proper generalisation of GCD, readily seen when b = d = 1. In other words:

When m and n are positive integers, GCRD(m, n) = GCD(m, n).

For example, GCRD(4/1, 10/1) = [GCD(4, 10)/1] = GCD(4,10). Additionally, thoughtful consideration of the formula in Result 2 shows that:

When GCRD(x, y) is an integer, then both x and y are integers.

It is not difficult to show that (exercise!): GCRD (a/bg, c/dg) = 1 if g = GCRD (a/b, c/d).

In other words, when two rational numbers are divided by their GCRD, the resulting numbers are relatively prime integers. For example, dividing 4/15 and 8/9 by their GCRD = 4/45 results in

[[4/15]/[4/45]] = [4/15] x [45/4] = 3 and [[8/9]/[4/45]] = [8/9] x [45/4] = 10.

Revisiting Problem A and further illustrations

Let us now revisit Problem A, the Tiling Problem. For Question 1 on tile dimension, we have seen that 2.5 metres will not work. We can now also state that no other non-integer (or integer) larger than 2 is acceptable because GCRD(8, 6) = GCD(8, 6) = 2. There are, of course, smaller rational multiples of 2 which work, such as 2/3.

For Question 2 on room dimension, if we do not wish to make conversions, we have previously verified directly that

GCRD(8, 5.8) = GCRD(8/1, 29/5) = GCD([8 x 5, 29 x 1/5]) = 1/5 metre.

Let us try another problem from scratch.

Problem B: Cranberry Juice

A cellar contains barrels of cranberry juice of three different capacities: 25.2 litres, 36 litres, and 54.1 litres. The distributor wishes to package the juice in containers with an equal amount of juice in each one. What is the maximum capacity of such a container?

Answer

To answer this question, we may convert the measurements to decilitres, for example, or just directly compute:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the Cranberry Juice problem affords an opportunity for considering GCRD applied to three (or more) terms.

The conceptual 'twin' of GCD is least common multiple (lowest common multiple) or LCM. We recall that the LCM of two whole numbers a and b is the smallest positive integer having both a and b as factors (see Burton, 2002, p. 30.) For example, LCM(12, 18) = 36. The entire development of GCRD can be repeated with minimal effort to give birth to its twin LCRM, or least common rational multiple. With (arguably) no surprise, LCRM (a/b, c/d) = [LCM (ad,bc)/bd].

Problem C: Travelling Vice-President

The vice-president of a corporation travels to Atlanta every 18 days for one day. The manager of one of the branches of this corporation travels to Atlanta every 24 days, also for one day. If both persons are in Atlanta today, in how many more days will they be in Atlanta again on the same day?

Answer

LCM(18, 24) = LCRM(18, 24) = 72 days.

Problem D: Lighthouse Beacon

The beacon of one lighthouse passes a certain point every 12.3 seconds; another passes the same location every 18.2 seconds. If at this moment the two beacons simultaneously flash on this location, in how many seconds will they do so again?

Answer

LCRM(12.3, 18.2) = LCRM (123/10, 91/5) = [LCM(123 x 5,10 x 9)/50] = [111.93/5] = 2238.6 seconds.

A higher-level application of GCRD

An unexpected application of GCRD is another proof of the irrationality of [square root of (2)]. This fact comes as a corollary to the following theorem.

Result 3

If n and k are positive integers and the kth root of n is rational then the kth root of n is an integer.

Suppose the kth root of n is a positive rational number for some positive integers k and n. Since [kth root of (n)] is a positive rational number, there exist relatively prime integers a and b such that [kth root of (n)] = a/b, or equivalently n = [(a/b).sup.k] = [a.sup.k]/[b.sup.k], with GCD([a.sup.k], [b.sup.k]) = 1. Clearly GCD(1, n) = 1. But we also have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, 1 = 1/[b.sup.k], or [b.sup.k] = 1 which implies b = 1. Hence, n = [a.sup.k], or [kth root of (n)] = a, which is an integer.

A statement equivalent to Result 3 is that if the kth root of n is not an integer, then it is irrational. For example, the real number [square root of (2)] is irrational.

Closing remarks

With no necessity for factorisation, recursive algorithms can be used to compute the GCD of two positive integers. Consequently, by Result 2, these algorithms can also be used to calculate GCRD. An alternative definition for GCRD can be formulated by means of factorisation and use of non-positive integer exponents. For example, GCRD (4/15, 8/9) = 4/45 can also be realised by the prime 'factorisations' 4/15 = [2.sup.2] x [3.sup.-1] x [5.sup.-1] and 8/9 = [2.sup.3] X [3.sup.-2] x [5.sup.0], so that their greatest common 'divisor' is [2.sup.2] x [3.sup.-2] x [5.sup.-1].

Problems for teachers and students

1. Show by example and then by proof that LCRM (a/b, c/d) = [LCM (ad,bc)/bd]. Hint: Use the fact that for integers x and y, GCD(x, y) x LCM(x, y) = xy.

2. Find the GCRD of each pair or triple.

(a) 3/7, 6/5

(b) 14/11, 2.8

(c) 1.7, 0.23

(d) 2/9, 3.14, 22/7

3. Fill in the blanks with distinct non-integer rational numbers, if possible.

(a) GCRD (_, _) = 3

(b) GCRD (_, _) = 2/5 _ [not equal to] 2/5

(c) GCRD (3/2, _) = 4

4. Let a, b, c, d, e and f be positive integers. Prove the following:

[For part (a), refer to the discussion in A formula for rational GCD.]

(a) GCRD (a/bg, c/dg) =1 if g = GCRD (a/b, c/d)

(b) GCRD ([e/f] x [a/b], [e/f] x [c/d]) = [e/f] x GCRD (a/b, c/d)

(c) GCRD (a/b, [a/b] + [c/d]) = GCRD (a/b, c/d)

5. Marcia is making bracelets of three varieties: ones with 4.5 mm beads, ones with 5.5 mm beads, and ones with 6.2 mm beads. What is the shortest bracelet length so that all three varieties are the same length?

6. Derive a formula for the GCRD of a triple consisting of two positive integers m and n and one positive rational a/b; in other words GCRD (m, n, a/b) =?

References

Burton, D. M. (2002). Elementary number theory (5th ed.). New York, NY: McGraw-Hill.

Pirnot, T. L. (2007). Mathematics all around (3rd ed.). Boston, MA: Pearson Addison-Wesley.

Grant Boudreaux & Scott Beslin

Nicholls State University, Louisiana, USA

<gb5udreaux@its.nicholls.edu>

<sc5tt.beslin@nich5lls.edu>

Printer friendly Cite/link Email Feedback | |

Author: | Boudreaux, Grant; Beslin, Scott |
---|---|

Publication: | Australian Senior Mathematics Journal |

Article Type: | Report |

Geographic Code: | 8AUST |

Date: | Jul 1, 2013 |

Words: | 3063 |

Previous Article: | Modelling transformations of quadratic functions: a proposal of inductive inquiry. |

Next Article: | Problem set 12. |

Topics: |