A Notation for the GCD and LCM Functions

E.E. McDonnell

IBM Corporation
1501 California Avenue
Palo Alto, CA 94304, USA

Abstract

This paper proposes a notation to be used for the greatest common divisor (gcd) and least common multiple (lcm) functions in APL. The notation proposed is that in use for the logical or and and functions: ∨ for gcd and ^ for lcm. For this reason, special attention is paid to the cases of gcd and lcm for the arguments 0 and 1 . Also, because we wish to define the functions for negative and complex rational values as well as for positive integers, we discuss the functions more generally than is the case in standard number theory texts, which usually restrict their discussions to positive integers. For this reason we give proofs of some of the basic theorems concerning gcd and lcm, written to insure that they are valid for the entire domain of values for which it is proposed the APL functions be defined. The discussion in this paper is couched in terms of integral arguments. The theoretical extension to rational arguments is an easy one, and it is assumed that the gcd and lcm functions, which depend on the residue function for their definitions, will be implemented for non-integral arguments, just as is the residue function, with all the practical difficulties which this entails.

In this paper, the terms “greatest” and “least” are taken to refer to magnitudes, and the terms “divisor” and “multiple” mean integer divisor and integer multiple.
 

0. Divisor and Multiple

If m=d×h , where h is an integer, then m is a multiple of d , and d is a divisor of m . If d=0 , h is not uniquely defined, but nonetheless 0 is a divisor of 0 .

A unit is a divisor of 1 . There are two real units, ¯1 and 1 , and four complex units: the two real units and the square root of negative one and its negative. Multiplication or division of a number by a unit does not produce a change in its magnitude, but will produce a change in its direction, if the unit is not 1 . Numbers which differ by unit multiples are associates. Every number but zero has associates. Every number is a divisor and multiple of itself (from the identity n=n×1) and associates are divisors and multiples of each other (if a is associated with b , then a=b×u for some unit u). Associates are equal in magnitude.
 

1. Zero as Divisor and Multiple

From the identity 0=a×0 we conclude that 1) the only multiple of zero is zero; 2) zero is a divisor only of zero, and no number but zero has zero as a divisor; 3) zero is the only number which is a multiple of every number; and 4) there is no unique quotient for 0÷0 .
 

2. Common Divisors and Division

Every number which is a divisor of each of two numbers is a common divisor of them. If d is a common divisor of h and k then the associates of d are also common divisors of h and k .

If c=a|b , then the common divisors of a and b are also common to c . For the definition of the residue function gives us c=b-a×⌊b÷a . If e is any common divisor of a and b , then b÷e and (a×⌊b÷a)÷e are integers, as is their difference, to be called v . Thus we can write c=e×v , showing that e is also a divisor of c . The proof shows that the expressions c=a+b and c=a-b may be substituted for c=a|b in the statement of the theorem, and the theorem will remain true: that the common divisors of a and b are also common divisors of c .

The common divisors of 0 and h are the divisors of h . This is easily seen using the algebra of sets. If i is the set of all numbers, these are the divisors of 0 . If d is the set of divisors of h , then d=i∩d .

A proof for the division theorem valid for complex numbers in general is given in [6]. The theorem states that if z and w are arbitrary numbers, with w≠0 , then there exists an integer q , and an r such that z=r+q×w, and (|r)<|w . The proof depends on the definition of the complex floor function, which provides that 1>|x-⌊x for all x . q is determined by ⌊z÷w , and r by w|z , and q and r are thus well-defined.

If there is a non-empty set of integers closed under addition and subtraction, then the set is either zero alone or consists of all multiples of some least non-zero element. In the first case, where the set consists only of zero, then 0+0 and 0-0 are in the set. In the second case, choose an element a≠0 . Then 0 is in the set, since 0=a-a . Now choose among the non-zero elements least in magnitude the element b . Then all multiples of b are in the set since it is closed under addition and subtraction. Conversely, all elements in the set are multiples of b , since if a is in the set, b|a is also in the set, since it is the difference of two elements in the set; but b|a is less than b in magnitude by the division theorem, and so must be zero; therefore a is a multiple of b . Clearly, the other least elements are associates of b .
 

3. Greatest Common Divisor

d is a greatest common divisor of h and k if it is a common divisor of h and k and is also a multiple of every other common divisor.

It can be shown that every two integers h and k have a gcd d such that d=(p×h)+q×k , where p and q are integers, and d=0 if and only if h=0 and k=0 .

In the first case, where h and k are not both zero, we see that for any two numbers of the form (p1×h)+q1×k and (p2×h)+q2×k , their sum ((p1+p2)×h)+(q1+q2)×k and difference ((p1-p2)xh)+(q1-q2)×k are also of that form. Therefore the set of all such linear combinations is closed under addition and subtraction, and thus contains 0 and a non-zero element d least in magnitude. d is a divisor of each element of the set. However h and k are both elements of the set (since h=(1×h)+0×k and k=(0×h)+1×k) and thus both have d as a divisor. For some integers p and q , d=(p×h)+q×k , and thus the common divisors of h and k are common divisors of d . Hence d is a greatest common divisor, for it is the greatest of the divisors of itself.

If h and k are both 0 , we know that every number is a common divisor of 0 and 0 . We know also that the only multiple of every number is 0 . Clearly, 0=(p×0)+q×0 for every p and q , and thus the gcd of 0 and 0 is 0 .
 

4. The Euclidean Algorithm

For the purpose of defining a function, it is necessary to be able to specify one of the associated greatest common divisors as the greatest common divisor. This is accomplished by the Euclidean algorithm, as interpreted using the definition of the residue function current in APL. The residue function, in turn, is assumed to be using the definition of the complex floor function given in reference [6].

A version of the algorithm similar to one given in [4] is as follows: to compute the greatest common divisor of h and k , assign the values h and k to v , forming a two-element vector. If the first element of v is zero, the algorithm terminates with the second element the result. If the first element of v is not zero, form a new first element by the process v←(|/2↑v),v . This new element is thus the residue of the former second element, using the former first element as the modulus. The process will terminate if h and k are integers (real or complex), since the successive prefixed residues form a sequence of integers decreasing in magnitude, and thus the sequence is finite and ends in zero. The process will also terminate if h and k are rational (real or complex), but the argument is not as straightforward.

When the algorithm described above terminates, the second element of v is the greatest common divisor of h and k . This is so because each overlapping pair of elements shares the same set of common divisors. Since v[1]=0 , the common divisors of v[1] and v[2] are the divisors of v[2] . So the divisors of v[2] are the common divisors of the elements of v , and in particular of the original elements of v , namely h and k . The greatest divisor of v[2] is of course v[2] , so the greatest common divisor of h and k (and of all the elements of v) is v[2] .

One is not ordinarily interested in the intermediate values developed in the course of executing the algorithm. Iterative versions of the algorithm which do not maintain the intermediate residues are given in [3] and [4]. A recursively defined function is given below:

      d←h gcd k
      d←k
      →(0=h)/0
      d←(h|k) gcd h

In a computer implementation of this function for rationals on a system like the IBM System 370, where non-terminating decimals are approximated by finite hexadecimals, the comparison 0=h should be replaced by a comparison of the magnitude of h with some relatively small positive number epsilon , in the form epsilon>|h .
 

5. A Notation for the GCD Function

The behavior of the gcd function with zero arguments has been discussed. It is evident that 0 is a left-right identity element for the function. If we tabulate the result of using all pairs of logical arguments with the function, we note that the gcd function is identical with the logical or function, denoted by ∨ :

      a   b   a gcd b
      0   0      0
      0   1      1
      1   0      1
      1   1      1

We adopt the ∨ notation forthwith to denote the gcd function. As is customary in APL, the gcd of a vector of numbers v may be found using reduction: ∨/v .
 

6. Least Common Multiple

Every number which is a multiple of each of two numbers is a common multiple of them. If m is a common multiple of h and k , then the associates of m are also common multiples of h and k . Among the common multiples of two numbers, other than zero, one set of associates is less than any other set of associates. This set is called the least common multiples of h and k , and any member of this set is a least common multiple of h and k .

Before investigating the lcm function, we must demonstrate several things. First we show that multiplication distributes over gcd, that is, ((m×h)∨m×k)=m×h∨k . If we multiply the vector v of the Euclidean algorithm (which contains a series of residues to the left of the original pair of arguments) by m , it is immediate that ((m×h)∨m×k)=m×h∨k .

If 1=h∨k , then h and k are said to be relatively prime. Now we have to show that, if we let d←h∨k , and set h1←h÷d , and k1←k÷d , then h1 and k1 are relatively prime. The following listing gives four equal expressions:

      d
      h∨k
      (d×h1)∨d×k1
      d×h1∨k1

and in particular the first and last expressions are equal, so that h1∨k1 must equal one, and therefore h1 and k1 are relatively prime.

Now we are in a position to show that a least common multiple of two numbers h and k is given by (h×k)÷h∨k , and is 0 if and only if 0=h×k .

In the first case, where h and k are not both zero, we make the following assignments:

      d←h∨k
      h1←h÷d
      k1←k÷d

Any multiple of h has the form p×h and thus equals p×h1×d . For p×h to be divisible by k , the factor p×h1 must be divisible by k1 . Because 1=h1∨k1 , this is possible only when p is divisible by k1 , so that p=q×k1 . Any common multiple m of h and k is thus given by any of the equivalent forms:

      m
      p×h
      q×k1×h
      q×k1×h1×d
      q×h1×k1×d
      q×h1×k
      q×(h÷d)×k
      q×(h×k)÷d
      q×(h×k)÷h∨k

It is clear that a least common multiple is obtained when q is equal to one. Therefore a least common multiple of h and k is given by (h×k)÷h∨k . The value so determined will be called the least common multiple.

In the second case, when either h or k (but not both) is equal to zero, the result must be zero, since the only multiple of 0 is 0 . The formula (h×k)÷h∨k evaluates to 0 for both these cases. When h and k are both 0 , the formula becomes (0×0)÷0∨0 , or 0÷0 , an indeterminate form. Since the only multiple of 0 is 0 , this suggests that the value of 0÷0 in APL should be 0 (not 1 as is currently the case).

For integral values n the function 1∨n gives the result 1 . Thus 1 is a left identity for the lcm function, that is, k=(1×k)÷1∨k for all integer k . It is not a right identity, since any unit as a left argument of lcm is a left identity element. Thus (¯1×1)÷¯1∨1 evaluates to ¯1÷¯1 or 1 .
 

7. A Notation for the LCM Function

We have discussed the behavior of the lcm function with 0 arguments, and have seen that 1 is a left identity element. If we tabulate the results of all pairs of logical arguments, we note that the lcm function is identical to the logical and function, denoted by ^ :

      a   b   a lcm b
      0   0      0
      0   1      0
      1   0      0
      1   1      1

We adopt the ^ notation forthwith to denote the lcm function. As is customary in APL, the lcm of a vector of numbers v may be found using reduction: ^/v .
 

8. Some Properties of the GCD and LCM Functions

For positive integer arguments, ∨ and ∧ are commutative and associative functions. For integers in general, or arbitrary rational arguments, neither of these is the case, as we saw with lcm and the arguments ¯1 and 1 . This arises from the fact that the residue function, which is central to both the gcd and the lcm function, is defined to be affected by the signum, or more generally, by the direction of the left argument. Thus (-h)∨k and (-h)∧k are different in general from h∨k and h∧k ; the difference lies in that the results of the two different forms will be associates. If we identify associates, then we can say that gcd and lcm are commutative and associative functions, for complex rational arguments in general. The gcd and lcm functions are replete with identities. A handful are given below.

h∨k
h∧k
h∨k∨l
h∧k∧l
m×h∧k
m×h∨k
(h^k)÷d
(h∨k)÷d
(h∧k)∨l
(h∨k)∧l
h
h
h
h
∨/(h^k),(h^l),k∨l

k∨h
k^h
(h∨k)∨l
(h^k)^l
(m×h)^m×k
(m×h)∨m×k
(h÷d)^k÷d
(h÷d)∨k÷d
(h∨l)^k∨l
(h^l)∨k^l
h^h∨k
h∨h^k
h∨h
h^h
^/(h∨k),(h∨l),k∨l

The two columns of formulas are to be understood to be connected with the relation “is associated with”, in general, and with the relation “is equal to” if the arguments are restricted to positive rationals and zero.
 

9. Conclusion

The basic idea for the notation was arrived at from a study of the properties of the functions. Subsequently, it was found that Greub, in [2] used essentially the same notation for the gcd and lcm of polynomials. Birkhoff and MacLane, in [1], use the same symbols, but interchanged. The duality between the functions, as evidenced by the identities given above, permits this when the field of discourse is restricted to the two functions. Iverson, in [5], suggested the similarly shaped symbols and to denote gcd and lcm, respectively. The most common usage in number theory texts are parentheses (h,k) for gcd and brackets [h,k] for lcm. These can not be employed in a consistent system of notation because of other conflicting uses of parentheses and brackets and, more strongly, because in APL we wish to denote a scalar dyadic function by a single symbol infixed between its arguments. Extending the domain of the ∨ and ^ symbols accomplishes this with no additions to the notation.
 

Acknowledgement

Don Orth of the IBM Philadelphia Scientific Center reviewed the manuscript and made many helpful suggestions.
 

References

Bibliography

Note: The principal work consulted was the paper by MacDuffee, which investigated the properties of the gcd and lcm functions for zero arguments. The texts used for more conventional material were Vinogradov (especially), Ore, and the referenced work by Birkhoff and MacLane.